2706. Fenwick Tree

单点时限: 5.0 sec

内存限制: 256 MB

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.

样例

Input
6
3 -1 4 1 -5 9
Output
0 -1 1 1 0 9

9 人解决,20 人已尝试。

12 份提交通过,共有 85 份提交。

7.4 EMB 奖励。

创建: 11 年,2 月前.

修改: 2 年前.

最后提交: 4 月前.

来源: NEERC 2008

题目标签