11040: CF453 - B. Little Pony and Harmony Chest
[Creator : ]
Description
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:
$\sum_{i=1}^{n}|a_i-b_i|$
You are given sequence ai, help Princess Twilight to find the key.
$\sum_{i=1}^{n}|a_i-b_i|$
You are given sequence ai, help Princess Twilight to find the key.
Input
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)$.
The next line contains $n$ integers $a_1,a_2, ...,a_n\ (1 ≤a_i≤ 30)$.
Output
Output the key — sequence $b_i$ that minimizes the sum described above. If there are multiple optimal sequences, you can output any of them.
Sample 1 Input
5
1 1 1 1 1
Sample 1 Output
1 1 1 1 1
Sample 2 Input
5
1 6 4 2 8
Sample 2 Output
1 5 4 1 9
Sample 3 Input
10
16 3 16 10 12 5 14 14 15 27
Sample 3 Output
16 1 17 9 7 5 11 13 19 29
10
8 7 11 5 17 24 28 18 7 8
8 1 11 5 17 23 29 19 7 9
Sample 4 Input
10
22 17 28 14 14 26 20 28 21 27
Sample 4 Output
23 16 29 11 13 25 17 31 19 27
HINT
Alrogithm
状压DP