Fenwick Tree
Fenwick tree is a data structure effectively supporting prefix sum queries.
For a number t denote as h(t) maximal k such that t is divisible by 2^k. For example, h(24) = 3, h(5) = 0. Let l(t) = 2^{h(t)}, for example, l(24) = 8, l(5) = 1.
Consider array a[1], a[2], ..., a[n] of integer numbers. Fenwick tree for this array is the array b[1], b[2], ..., b[n] such that
.
So
b[1] = a[1],
b[2] = a[1] + a[2],
b[3] = a[3],
b[4] = a[1] + a[2] + a[3] + a[4],
b[5] = a[5],
b[6] = a[5] + a[6],
...
For example, the Fenwick tree for the array
a = (3, -1, 4, 1,-5, 9)
is the array
b = (3, 2, 4, 7,-5, 4).
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 a = (0,-1, 1, 1, 0, 9) is self-fenwick.
You are given an array a. You are allowed to change values of some elements without changing their order to get a new array a' which must be self-fenwick. Find the way to do it by changing as few elements as possible.
Input
The first line of the input file contains n — the number of elements in the array (1 ≤ n ≤ 100000). The second line contains n integer numbers — the elements of the array. The elements do not exceed 10^9 by their absolute values.
Output
Output n numbers — the elements of the array a'. If there are several solutions, output any one.