For a number denote as maximal such that is divisible by . For example, , . Let , for example, , .
Consider array of integer numbers. Fenwick tree for this array is the array such that
So
,
,
,
,
,
,
…
For example, the Fenwick tree for the array is the array .
Let us call an array self-fenwick if it coincides with its Fenwick tree. For example, the array above is not self-fenwick, but the array is self-fenwick.
You are given an array . You are allowed to change values of some elements without changing their order to get a new array which must be self-fenwick. Find the way to do it by changing as few elements as possible.
输入格式
The first line of the input file contains ― the number of elements in the array (). The second line contains integer numbers ― the elements of the array. The elements do not exceed by their absolute values.
输出格式
Output numbers ― the elements of the array . If there are several solutions, output any one.