#P959D. Mahmoud and Ehab and another array construction task

    ID: 4212 Type: RemoteJudge 3000ms 256MiB Tried: 0 Accepted: 0 Difficulty: (None) Uploaded By: Tags>constructive algorithmsgreedymathnumber theory*1900

Mahmoud and Ehab and another array construction task

No submission language available for this problem.

Description

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.
  • bi ≥ 2.
  • b is pairwise coprime: for every 1 ≤ i < j ≤ n, bi and bj are coprime, i. e. GCD(bi, bj) = 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 xi > yi and xj = yj for all 1 ≤ j < i. An array x is equal to an array y if xi = yi for all 1 ≤ i ≤ n.

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

The second line contains n integers a1, a2, ..., an (2 ≤ ai ≤ 105), the elements of a.

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

Input

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

The second line contains n integers a1, a2, ..., an (2 ≤ ai ≤ 105), the elements of a.

Output

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

Samples

5
2 3 5 4 13

2 3 5 7 11
3
10 3 7

10 3 7

Note

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