Dãy nguyên tố cùng nhau nhỏ nhất theo thứ tự từ điển

Cho một dãy $a$ gồm $n$ số nguyên. Hãy tìm một dãy $b$ cũng gồm $n$ số nguyên thoả mãn đồng thời các điều kiện sau:

• $b$ lớn hơn hoặc bằng $a$ theo thứ tự từ điển.
• $b_i\ge 2$ với mọi $i$.
• $b$ đôi một nguyên tố cùng nhau: với mọi $1\le i<j\le n$ thì $gcd(b_i,b_j)=1$.

Trong tất cả các dãy $b$ thoả mãn, hãy in ra dãy nhỏ nhất theo thứ tự từ điển.

Dãy $x$ lớn hơn dãy $y$ theo thứ tự từ điển nếu tồn tại chỉ số $i$ sao cho $x_i>y_i$ và $x_j=y_j$ với mọi $1\le j<i$.

Dữ liệu vào

• Dòng đầu chứa số nguyên $n$.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$.

Dữ liệu ra

In ra $n$ số nguyên $b_1,b_2,\dots ,b_n$ cách nhau bởi dấu cách — dãy thoả mãn nhỏ nhất theo thứ tự từ điển.

Ràng buộc

• $1\le n\le {10}^5$
• $2\le a_i\le {10}^5$

Ví dụ