2706. Fenwick Tree

单点时限: 5.0 sec

内存限制: 256 MB

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

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.

输入格式

The first line of the input file contains $n$ ― the number of elements in the array ($1 \le n \le 100~000$). The second line contains $n$ integer numbers ― the elements of the array. The elements do not exceed $10^9$ by their absolute values.

输出格式

Output $n$ numbers ― the elements of the array $a’$. 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 年,9 月前.

修改: 2 年,7 月前.

最后提交: 10 月,2 周前.

来源: NEERC 2008

题目标签