3576번 - 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], \dots , a[n]$ of integer numbers. Fenwick tree for this array is the array $b[1], b[2], \dots , b[n]$ such that $$b[i] = \sum_{j=i-l(i)+1}^{i}{a[j]}\text{.}$$

So

$$\begin{align*}& 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], \\ & \ldots \end{align*}$$

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.