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.


-----Input-----

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

The second line contains n integers a_1, a_2, ..., a_{n} (2 ≤ a_{i} ≤ 10^5), the elements of a.


-----Output-----

Output n space-separated integers, the i-th of them representing b_{i}.


-----Examples-----
Input
5
2 3 5 4 13

Output
2 3 5 7 11 
Input
3
10 3 7

Output
10 3 7 


-----Note-----

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

Difficulty: interview

Starter code:

Solutions:
import sys
import math

def sieve(n):
    prime_factors = [[] for i in range(n+1)]
    tmp = [True] * (n+1)
    tmp[0] = tmp[1] = False
    for i in range(2, n+1):
        if tmp[i]:
            for k in range(i, n+1, i):
                tmp[k] = False
                prime_factors[k].append(i)
    return prime_factors

n = int(sys.stdin.readline().strip())
a = list(map(int, sys.stdin.readline().strip().split(' ')))
b = []
forbidden_factors = set({})
prime_factors = sieve(2000005)
is_greater = False
min_available = 2

for ai in a:
    factors = prime_factors[ai]
    if not is_greater:
        curr = ai
        ok = True
        for f in factors:
            if f in forbidden_factors:
                ok = False
                break
        if ok:
            for f in factors:
                forbidden_factors.add(f)
        else:
            is_greater = True
            ok = False
            while not ok:
                curr += 1
                ok = True
                factors = prime_factors[curr]
                for f in factors:
                    if f in forbidden_factors:
                        ok = False
                        break
            for f in factors:
                forbidden_factors.add(f) 
    else:
        curr = min_available
        ok = True
        factors = prime_factors[curr]
        for f in factors:
            if f in forbidden_factors:
                ok = False
                break
        while not ok:
            curr += 1
            ok = True
            factors = prime_factors[curr]
            for f in factors:
                if f in forbidden_factors:
                    ok = False
                    break
        min_available = curr
        for f in factors:
            forbidden_factors.add(f)
    b.append(str(curr))
print(" ".join(b))


# -*- coding: UTF-8 -*-

MAX_NUM = 2000000

prime_str = ('2      3      5      7     11     13     17     19     23     29 '
        +   '31     37     41     43     47     53     59     61     67     71 '
        +   '73     79     83     89     97    101    103    107    109    113 '
        +  '127    131    137    139    149    151    157    163    167    173 '
        +  '179    181    191    193    197    199    211    223    227    229 '
        +  '233    239    241    251    257    263    269    271    277    281 '
        +  '283    293    307    311    313    317 '
)
prime_list = [int(p) for p in prime_str.split()]
used = [False] * MAX_NUM

n = int(input())
a = list(map(int, input().split()))


def record(x):
    t = []
    for p in prime_list:
        if x % p == 0:
            while x % p == 0:
                x = x // p
            t.append(p)
            if x == 1:
                break
    if x != 1:
        t.append(x)

    for ti in t:
        for i in range(ti, MAX_NUM, ti):
            used[i] = True


b = []
for ai in a:
    if not used[ai]:
        b.append(ai)
        record(ai)
    else:
        tmp = ai + 1
        while used[tmp]:
            tmp += 1
        b.append(tmp)
        record(tmp)
        break

tmp = 2
while len(b) < len(a):
    while used[tmp]:
        tmp += 1
    b.append(tmp)
    record(tmp)

print(' '.join(str(x) for x in b))


MAX_NUM = 2000000

prime_str = ('2      3      5      7     11     13     17     19     23     29 '
        +   '31     37     41     43     47     53     59     61     67     71 '
        +   '73     79     83     89     97    101    103    107    109    113 '
        +  '127    131    137    139    149    151    157    163    167    173 '
        +  '179    181    191    193    197    199    211    223    227    229 '
        +  '233    239    241    251    257    263    269    271    277    281 '
        +  '283    293    307    311    313    317 '
)
prime_list = [int(p) for p in prime_str.split()]
used = [False] * MAX_NUM

n = int(input())
a = list(map(int, input().split()))

def record(x):
    t = []
    for p in prime_list:
        if x % p == 0:
            while x % p == 0:
                x = x // p
            t.append(p)
            if x == 1:
                break
    if x != 1:
        t.append(x)

    for ti in t:
        for i in range(ti, MAX_NUM, ti):
            used[i] = True

b = []
for ai in a:
    if not used[ai]:
        b.append(ai)
        record(ai)
    else:
        temp = ai + 1
        while used[temp]:
            temp += 1
        b.append(temp)
        record(temp)
        break

temp = 2
while len(b) < len(a):
    while used[temp]:
        temp += 1
    b.append(temp)
    record(temp)

print(' '.join(str(x) for x in b))


N = 2*(10**6)
i = 2
p = [0 for i in range(N)]
while(i*i <= N):
	if(p[i] == 0):
		for j in range(i*i,N,i):
			p[j] = 1
	i += 1
a = []
for i in range(2,N):
	if(p[i] == 0):
		a.append(i)
n = int(input())
l = list(map(int,input().split()))
d = dict()
ans = []
for i in range(n):
	v = []
	y = l[i]
	j = 2
	f = 1
	while(j*j <= l[i]):
		if(l[i]%j == 0):
			if(j in d):
				f = 0
				break
			v.append(j)
			while(l[i]%j == 0):
				l[i] /= j
		j += 1
	if(l[i] > 1):
		if(l[i] in d):
			f = 0
		v.append(l[i])
	if(f == 1):
		ans.append(y)
		for x in v:
			d[x] = 1
	else:
		for x in range(y,N):
			j = 2
			f = 1
			l[i] = x
			while(j*j <= l[i]):
				if(l[i]%j == 0):
					if(j in d):
						f = 0
						break
					while(l[i]%j == 0):
						l[i] /= j
				j += 1
			if(l[i] > 1):
				if(l[i] in d):
					f = 0
			if(f == 1):
				ans.append(x)
				break
		break
j = 2
x = ans[-1]
while(j*j <= x):
	if(x%j == 0):
		d[j] = 1
		while(x%j == 0):
			x /= j
	j += 1
if(x > 1):
	d[x] = 1
sz = len(ans)
for i in a:
	if(sz == n):
		break
	if(i not in d):
		ans.append(i)
		sz += 1
for i in ans:
	print(i,end = " ")
print()