题意简述
你的工作是制造书架。现在你需要测试书架的牢固程度。
测试的方式如下：一个一个在书架上任意层放上铁球。如果第 $i$ 层书架上的铁球数量 $x$ 超过了该层书架的负载上限，那么第 $i$ 层书架就会被破坏。有 $\left\lfloor\dfrac{x}{2}\right\rfloor$ 个铁球会掉到第 $j$ 层书架上，满足 $j$ 是 $j>i$ 且第 $j$ 层书架还未被破坏的最小的 $j$；剩下的所有球会掉在地上。如果第 $j$ 层书架此时超过了负荷，那么它也会立即被破坏。
现在已知第 $i$ 层书架的负载上限为 $a_i$，即当 $\boldsymbol{x\geq a_i}$ 时它会被立即破坏。你希望尽快下班，所以你想求出对于 $k=1\sim n$，破坏前 $k$ 层书架最少需要放置多少个铁球。
输入格式
本题有多组测试数据。
第一行输入两个整数 $sid,T$，表示测试点编号和数据组数。样例中 $sid = 0$。
对于每组测试数据：
第一行输入一个整数 $n$，表示序列的长度。
第二行输入 $n$ 个整数，第 $i$ 个整数表示 $a_i$。
输出格式
对于每组测试数据，输出一行 $n$ 个整数，第 $k$ 个整数表示破坏前 $k$ 层最少需要放置的铁球数量。
样例输入 1
0 2
3
8 1 2
5
10 3 3 8 4样例输出 1
8 8 8
10 10 11 17 17对于第一组数据，破坏前 $3$ 层的最优方案为在第一层放置 $8$ 个铁球，第一层会被立即破坏，且 $4$ 个铁球落在第二层，第二层随即被破坏， 并有 $2$ 个铁球落在第 $3$ 层，第 $3$ 层同样被破坏。
对于第二组数据，破坏前 $5$ 层的最优方案为在第二层放置 $3$ 个铁球，然后在第三层放置 $2$ 个铁球，接着在第 $1$ 层放置 $10$ 个铁球，最后在第 $4$ 层放置 $2$ 个铁球，所以一共需要放置 $3+2+10+2=17$ 个铁球，通过简单模拟可以发现这种放置方法满足条件。
样例输入 / 输出 2
见选手目录下的 ex_book2.in / ex_book2.ans。
该样例满足测试点 $1$ 的限制。
样例输入 / 输出 3
见选手目录下的 ex_book3.in / ex_book3.ans。
该样例满足测试点 $2\sim 3$ 的限制。
样例输入 / 输出 4
见选手目录下的 ex_book4.in / ex_book4.ans。
该样例满足测试点 $4$ 的限制。
样例输入 / 输出 5
见选手目录下的 ex_book5.in / ex_book5.ans。
该样例满足测试点 $5\sim 7$ 的限制。
样例输入 / 输出 6
见选手目录下的 ex_book6.in / ex_book6.ans。
该样例满足测试点 $8\sim 10$ 的限制。
数据范围与约定
| 测试点编号 | $n\leq $ | $a_i\leq$ |
|---|---|---|
| $1$ | $3$ | $5$ |
| $2\sim 3$ | $10$ | $150$ |
| $4$ | $70$ | $2$ |
| $5\sim 7$ | $30$ | $30$ |
| $8\sim 10$ | $70$ | $150$ |
对于所有数据，保证 $1\leq n\leq 70,1\leq a_i\leq 150,1\leq T\leq 5$。