← 返回题目列表

Codeforces · 959/D

D. Mahmoud 和 Ehab 以及另一个阵列构建任务

中文机器翻译题面 查看原题

Mahmoud 有一个由 n 个整数组成的数组 a。他要求 Ehab 找到另一个长度相同的数组 b,这样:

- b 按字典顺序大于或等于 a。
- bi ≥ 2。
- b 是成对互质:对于每个 1 ≤ i < j ≤ n,bi 和 bj 是互质 i。 e. GCD(bi, bj) = 1,其中GCD(w, z)是w和z的最大公约数。

Ehab 想要选择一个特殊的数组,因此他想要所有变体之间按字典顺序排列的最小数组。你能找到吗?

如果存在索引 i,例如 xi > yi 且 xj = yj(对于所有 1 ≤ j < i),则数组 x 按字典顺序大于数组 y。如果 xi = yi 对于所有 1 ≤ i ≤ n,则数组 x 等于数组 y。

输入

第一行包含一个整数 n (1 ≤ n ≤ 105),即 a 和 b 中元素的数量。

第二行包含n个整数a1, a2, ..., an (2 ≤ ai ≤ 105),即a的元素。

输出

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

示例

输入 #1

5
2 3 5 4 13

输出 #1

2 3 5 7 11

输入 #2

3
10 3 7

输出 #2

10 3 7

注意

请注意,在第二个示例中,数组已经是成对互质的,因此我们将其打印出来。