Problem

Description

Princess Twilight went to Celestia and Luna’s old castle to research the chest from the Elements of Harmony.

A sequence of positive integers is harmony if and only if for every two elements of the sequence their greatest common divisor equals . According to an ancient book, the key of the chest is a harmony sequence bi which minimizes the following expression:

You are given sequence , help Princess Twilight to find the key.

Input

The first line contains an integer — the number of elements of the sequences and . The next line contains integers .

Output

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

Input #1

Output #1

Input #2

Output #2