CF959D.Mahmoud and Ehab and another array construction task

Mahmoud has an array a consisting of n integers. He asked Ehab to find another array b of the same length such that:

• b is lexicographically greater than or equal to a.
• b__i ≥ 2.
• b is pairwise coprime: for every 1 ≤ i < j ≤ n, b__i and b__j are coprime, i. e. GCD(b__i, b__j) = 1, where GCD(w, z) is the greatest common divisor of w and z.

Ehab wants to choose a special array so he wants the lexicographically minimal array between all the variants. Can you find it?

An array x is lexicographically greater than an array y if there exists an index i such than x__i > y__i and x__j = y__j for all 1 ≤ j < i. An array x is equal to an array y if x__i = y__i for all 1 ≤ i ≤ n.

马哈茂德有一个由 $ n $ 个整数组成的数组 $ a $。他请埃哈卜构造另一个长度相同的数组 $ b $，满足以下条件：

• $ b $ 的字典序大于等于 $ a $；
• 对所有 $ i $，有 $ b_i \geq 2 $；
• $ b $ 中的元素两两互质：即对任意 $ 1 \leq i < j \leq n $，均有 $ \gcd(b_i,,b_j) = 1 $，其中 $ \gcd(w,,z) $ 表示 $ w $ 与 $ z $ 的最大公约数。

埃哈卜希望选出一个“特殊”的数组，因此他想要在所有满足条件的数组中，找出字典序最小的那个。你能找到它吗？

数组 $ x $ 的字典序大于数组 $ y $，当且仅当存在某个下标 $ i $，使得 $ x_i > y_i $，且对所有 $ 1 \leq j < i $ 均有 $ x_j = y_j $。
数组 $ x $ 等于数组 $ y $，当且仅当对所有 $ 1 \leq i \leq n $，均有 $ x_i = y_i $。

The first line contains an integer n (1 ≤ n ≤ 105), the number of elements in a and b.

The second line contains n integers _a_1, _a_2, ..., a__n (2 ≤ a__i ≤ 105), the elements of a.

第一行包含一个整数 $n$（$1 \leq n \leq 10^5$），表示数组 $a$ 和 $b$ 的元素个数。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$2 \leq a_i \leq 10^5$），表示数组 $a$ 的元素。

Output n space-separated integers, the i-th of them representing b__i.

输出 n 个空格分隔的整数，其中第 i 个整数表示 b__i。

Note that in the second sample, the array is already pairwise coprime so we printed it.

注意，在第二个样例中，该数组已经是两两互质的，因此我们直接输出了它。