## Problem A. Fenwick Tree ≡

• problems
 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, a, …, a[n] of integer numbers. Fenwick tree for this array is the array b, b, …, b[n] such that

b[i] = ij = i − l(i) + 1a[j].

So

b = a,

b = a + a,

b = a,

b = a + a + a + a,

b = a,

b = a + a,

...

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

1 ≤ n ≤ 100000.

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.081s 0.011s 13