2706. Fenwick Tree

单点时限: 5.0 sec

内存限制: 256 MB

For a number t denote as h(t) maximal k such that t is divisible by 2k. For example, h(24)=3, h(5)=0. Let l(t)=2h(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
b[i]=j=il(i)+1ia[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 (1n100 000). The second line contains n integer numbers ― the elements of the array. The elements do not exceed 109 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 奖励。

创建: 16 年,5 月前.

修改: 7 年,2 月前.

最后提交: 5 年,6 月前.

来源: NEERC 2008

题目标签