D. Махмуд, Эхаб и еще одна игра про построение массива
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Махмуда есть массив a, состоящий из n целых чисел. Он попросил Эхаба найти такой массив b такой же длины, что:

  • b лексикографически больше или равен a.
  • bi ≥ 2.
  • Все числа в b попарно взаимно просты: для любых 1 ≤ i < j ≤ n, bi и bj взаимнопросты, то есть GCD(bi, bj) = 1, где GCD(w, z) — наибольший общий делитель чисел w и z.

Эхаб хочет выбрать особый массив, поэтому среди всех возможных вариантов он хочет выбрать лексикографически минимальный массив. Можете ли вы его найти?

Массив x лексикографически больше, чем массив y, если существует индекс i такой, что xi > yi и xj = yj для всех 1 ≤ j < i. Массив x равен массиву y, если xi = yi для всех 1 ≤ i ≤ n.

Входные данные

Первая строка содержит одно целое число n (1 ≤ n ≤ 105) — число элементов в массивах a и b.

Вторая строка содержит n целых чисел a1, a2, ..., an (2 ≤ ai ≤ 105) — элементы a.

Выходные данные

Выведите n целых чисел, разделённых пробелами, i-е из которых равно bi.

Примеры
Входные данные
5
2 3 5 4 13
Выходные данные
2 3 5 7 11
Входные данные
3
10 3 7
Выходные данные
10 3 7
Примечание

Заметьте, что во втором примере все числа в массиве уже попарно взаимнопросты, поэтому мы и выводим его.