Mahmoud and Ehab와 또 다른 배열 구성 과제

Mahmoud에게는 n개의 정수로 이루어진 배열 a가 있다. 그는 Ehab에게 다음 조건을 만족하는 길이가 같은 또 다른 배열 b을 찾아 달라고 했다.

• b은 a보다 사전순으로 크거나 같다.
• bi ≥ 2.
• b은 쌍마다 서로소이다. 즉, 모든 1 ≤ i < j ≤ n에 대해 bi과 bj는 서로소이다. 다시 말해, GCD(bi, bj) = 1이다. 여기서 GCD(w, z)는 w와 z의 최대공약수이다.

Ehab는 특별한 배열을 선택하고 싶으므로, 가능한 모든 배열 중 사전순으로 가장 작은 배열을 원한다. 이 배열을 구할 수 있는가?

어떤 인덱스 i가 존재하여 xi > yi이고 모든 1 ≤ j < i에 대해 xj = yj이면 배열 x는 배열 y보다 사전순으로 크다. 모든 1 ≤ i ≤ n에 대해 xi = yi이면 배열 x와 배열 y는 같다.

첫째 줄에 a와 b의 원소 개수를 나타내는 정수 n (1 ≤ n ≤ 105)가 주어진다.

둘째 줄에 a의 원소인 n개의 정수 a1, a2, ..., an (2 ≤ ai ≤ 105)이 주어진다.

공백으로 구분된 n개의 정수를 출력하며, 그중 i-th는 bi를 나타낸다.

두 번째 예제에서는 배열이 이미 쌍마다 서로소이므로 그대로 출력했다.