（Fenwick Tree）

题目描述

芬威克树是一种能够高效支持前缀和查询的数据结构。

对于正整数 $t$，记 $h(t)$ 为满足 $2^k\mid t$ 的最大非负整数 $k$。例如：

• $h(24)=3$；
• $h(5)=0$。

令

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

例如 $l(24)=8$，$l(5)=1$。

给定一个长度为 $n$ 的整数数组

$$a[1],a[2],\ldots,a[n],$$

它的芬威克树定义为数组

$$b[1],b[2],\ldots,b[n],$$

其中

$$b[i]=\sum_{j=i-l(i)+1}^{i}a[j].$$

因此：

$$\begin{aligned} 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],\\ &\ \vdots \end{aligned}$$

例如，数组

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

对应的芬威克树为

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

如果一个数组与它自己的芬威克树完全相同，则称它为一个自芬威克数组。

例如，上面的数组不是自芬威克数组，而

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

是自芬威克数组。

现在给定一个数组 $a$。你可以修改其中若干个元素的值，但不能改变元素的顺序。你需要得到一个新的自芬威克数组 $a'$，并使被修改的元素个数尽可能少。

请输出任意一种最优方案。

输入格式

第一行包含一个整数 $n$，表示数组长度。

第二行包含 $n$ 个整数，表示数组 $a$。

输出格式

输出 $n$ 个整数，表示得到的自芬威克数组 $a'$。

如果存在多种最优方案，输出任意一种即可。

样例

输入

6
3 -1 4 1 -5 9

输出

0 -1 1 1 0 9

数据范围

• $1\le n\le 100000$；
• $|a_i|\le 10^9$。