Rương Hài Hòa

Một dãy số nguyên dương $b_1,b_2,\dots ,b_n$ được gọi là hài hòa nếu ước chung lớn nhất của mọi cặp phần tử trong dãy đều bằng $1$ (tức là $gcd(b_i,b_j)=1$ với mọi $i\ne j$).

Cho dãy số nguyên dương $a_1,a_2,\dots ,a_n$. Hãy tìm một dãy hài hòa $b_1,b_2,\dots ,b_n$ sao cho tổng

$$\sum _{i=1}^n|a_i-b_i|$$

là nhỏ nhất.

Dữ liệu vào

• Dòng đầu chứa số nguyên $n$ — số phần tử của dãy.
• 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 dương $b_1,b_2,\dots ,b_n$ — dãy hài hòa làm tổng nói trên nhỏ nhất. Nếu có nhiều dãy tối ưu, in ra dãy bất kỳ.

Ràng buộc

• $1\le n\le 100$
• $1\le a_i\le 30$

Ví dụ