У Махмуда есть массив 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 целых чисел, разделённых пробелами, i-е из которых равно bi.
Примечание
Заметьте, что во втором примере все числа в массиве уже попарно взаимнопросты, поэтому мы и выводим его.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
2 3 5 4 13
|
2 3 5 7 11
|
|
2
|
3
10 3 7
|
10 3 7
|