Fenwick Tree#6233

Fenwick Tree

3 seconds

256 megabytes

Very easy

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}$ 2^k. For example, $h (24) = 3$ h(24) = 3, $h (5) = 0$ h(5) = 0. Let $l (t) = 2^{h (t)}$ l(t) = 2^{h(t)}, for example, $l (24) = 8$ l(24) = 8, $l (5) = 1$ l(5) = 1.

Consider array $a_{1}$ a_1, $a_{2}$ a_2, ..., $a_{n}$ a_n of integer numbers. Fenwick tree for this array is the array $b_{1}$ b_1, $b_{2}$ b_2, ..., $b_{n}$ b_n such that

So

$b_{1} = a_{1}$ b_1 = a_1,
$b_{2} = a_{1} + a_{2}$ b_2 = a_1 + a_2,
$b_{3} = a_{3}$ b_3 = a_3,
$b_{4} = a_{1} + a_{2} + a_{3} + a_{4}$ b_4 = a_1 + a_2 + a_3 + a_4,
$b_{5} = a_{5}$ b_5 = a_5,
$b_{6} = a_{5} + a_{6}$ b_6 = a_5 + a_6,
...

For example, the Fenwick tree for the array

$a = (3, - 1, 4, 1, - 5, 9)$ a = (3, -1, 4, 1,-5, 9)

is the array

$b = (3, 2, 4, 7, - 5, 4)$ 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)$ 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^{'}$ a' which must be self-fenwick. Find the way to do it by changing as few elements as possible.

Input

The first line of the input file contains $n$ — the number of elements in the array ( $1 \leq n \leq 100000$ 1 \le n \le 100000). The second line contains $n$ integer numbers — the elements of the array. The elements do not exceed $1 0^{9}$ 10^9 by their absolute values.

Output

Output $n$ numbers — the elements of the array $a^{'}$ a'. If there are several solutions, output any one.

Examples

Example 1

Loading

2^{k}

h (24) = 3

h (5) = 0

l (t) = 2^{h (t)}

l (24) = 8

l (5) = 1

a_{1}

a_{2}

a_{n}

b_{1}

b_{2}

b_{n}

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}

a = (3, - 1, 4, 1, - 5, 9)

b = (3, 2, 4, 7, - 5, 4)

a = (0, - 1, 1, 1, 0, 9)

a^{'}

1 \leq n \leq 100000

1 0^{9}

a^{'}