Little Pony and Harmony Chest

题意翻译

### 题目背景 紫悦正在宇宙公主和月亮的城堡里研究和谐之元的宝箱。 ### 题目描述 对于一个正整数序列 $b_i$,当且仅当它的任意两个元素都互质时,这个序列 $b_i$ 才是和谐的。据古书记载,宝箱的钥匙是能让以下表达式的值最小的和谐序列 $b_i$: $$ \sum_{i=1}^n|a_i-b_i| $$ 现在紫悦已经得到了序列 $a_i$,你能帮助紫悦找到开启宝箱的钥匙吗? ### 输入格式: 第一行包含一个正整数 $n(1 \le n \le 100)$,表示 $a$、$b$ 序列的长度。 第二行包含一串长度为 $n$ 的整数 $a_1, a_2,\dots, a_n (1 \le  a_i\le 30)$。 ### 输出格式: 输出一行 $n$ 个整数,表示满足条件的 $b_i$ 序列。 Translated by @[Rockdu](https://www.luogu.com.cn/user/39907),reformed by @[Rainy_chen](https://www.luogu.com.cn/user/74020)。

题目描述

Princess Twilight went to Celestia and Luna's old castle to research the chest from the Elements of Harmony. ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF453B/8ef25b8d7e467d01f853452542bae72c04218a5c.png)A sequence of positive integers $ b_{i} $ is harmony if and only if for every two elements of the sequence their greatest common divisor equals 1. According to an ancient book, the key of the chest is a harmony sequence $ b_{i} $ which minimizes the following expression: ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF453B/97bad96a3a07ca00d2975bfabd2fb8b2f2ff6370.png)You are given sequence $ a_{i} $ , help Princess Twilight to find the key.

输入输出格式

输入格式


The first line contains an integer $ n $ ( $ 1<=n<=100 $ ) — the number of elements of the sequences $ a $ and $ b $ . The next line contains $ n $ integers $ a_{1},a_{2},...,a_{n} $ ( $ 1<=a_{i}<=30 $ ).

输出格式


Output the key — sequence $ b_{i} $ that minimizes the sum described above. If there are multiple optimal sequences, you can output any of them.

输入输出样例

输入样例 #1

5
1 1 1 1 1

输出样例 #1

1 1 1 1 1 

输入样例 #2

5
1 6 4 2 8

输出样例 #2

1 5 3 1 8