← 返回题目列表

Codeforces · 453/B

B. 小马驹和和谐宝箱

中文机器翻译题面 查看原题

暮光公主前往塞拉斯蒂娅和露娜的古老城堡研究和谐元素的宝箱。

正整数 bi 的序列是和谐的,当且仅当该序列的每两个元素的最大公约数等于 1。根据一本古书,宝箱的钥匙是和谐序列 bi ,它最小化了以下表达式:

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

给你序列ai,帮助暮光公主找到钥匙。

输入

第一行包含一个整数 n (1 ≤ n ≤ 100) — 序列 a 和 b 的元素数量。下一行包含 n 个整数 a1, a2, ..., an (1 ≤ ai ≤ 30)。

输出

输出最小化上述总和的密钥 — 序列 bi 。如果有多个最优序列,则可以输出其中任意一个。

示例

输入 #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