Fenwick Tree

문제

Fenwick tree is a data structure effectively supporting prefix sum queries.

For a number $tt$ denote as $h(t)h(t)$ maximal $kk$ such that $tt$ is divisible by $2^{k}2^k$. For example, $h(24)=3h(24)\; =\; 3$, $h(5)=0h(5)\; =\; 0$. Let $l(t)=2^{h(t)}l(t)\; =\; 2^\{h(t)\}$, for example, $l(24)=8,l(5)=1l(24)\; =\; 8,\; l(5)\; =\; 1$.

Consider array $a[1],a[2],\dots ,a[n]a[1],\; a[2],\; \backslash dots\; ,\; a[n]$ of integer numbers. Fenwick tree for this array is the array $b[1],b[2],\dots ,b[n]b[1],\; b[2],\; \backslash dots\; ,\; b[n]$ such that $$b[i]=\sum _{j=i-l(i)+1}^{i}a[j]\text{.}b[i]\; =\; \backslash sum\_\{j=i-l(i)+1\}^\{i\}\{a[j]\}\backslash text\{.\}$$

So

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)\text{.}

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.

입력

The first line of the input file contains n — the number of elements in the array (1 ≤ n ≤ 100 000). The second line contains n integer numbers — the elements of the array. The elements do not exceed 10⁹ by their absolute values.

출력

Output n numbers — the elements of the array a′. If there are several solutions, output any one.

6
3 -1 4 1 -5 9

0 -1 1 1 0 9