Processing math: 100%

Problem F. Fenwick Tree

Author:ACM ICPC 2008-2009, NEERC, Northern Subregional Contest   Time limit:3 sec
Input file:fenwick.in   Memory limit:256 Mb
Output file:fenwick.out  

Statement

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 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]=ij=il(i)+1a[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.

Input file format

The first line of the input file contains n — the number of elements in the array. The second line contains n integer numbers — the elements of the array.

Output file format

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

Constraints

1n100000.

The elements of the input array do not exceed 109 by their absolute values.

Sample tests

No. Input file (fenwick.in) Output file (fenwick.out)
1
6
3 -1 4 1 -5 9
0 -1 1 1 0 9

0.042s 0.006s 13