← 返回题目列表

Codeforces · 2057/H

H. 茶歇

中文机器翻译题面 查看原题

T 一代的课程很长。一天之内,你需要有时间分析培训和主题竞赛,用新材料进行讲座,如果可能的话,还举办一个小型研讨会。因此,有休息时间,学生们可以去喝咖啡、互相聊天。

沿着长长的走廊,依次排列的房间内共有 $$$n+2$$$ 咖啡机。咖啡机的编号从$$$0$$$到$$$n+1$$$,休息一开始,就有$$$a_i$$$学生聚集在第$$$i$$$咖啡机周围。

学生们互相说话太大声,老师需要宣布一个非常重要的消息。因此,他们希望将最大数量的学生聚集在一台咖啡机周围。老师们懒得在走廊里跑来跑去聚集学生,所以他们想出了一个更复杂的方法来操纵他们:

- 老师可以随时选择房间 $$$i$$$ ($$$1 \le i \le n$$$) 并关闭那里的灯;
- 如果该房间里有$$$x$$$学生,则关灯后,$$$\lfloor \frac12 x \rfloor$$$学生将前往$$$(i-1)$$$房间,而$$$\lfloor \frac12 x \rfloor$$$其他学生将前往$$$(i+1)$$$房间。
- 如果 $$$x$$$ 为奇数,则一名学生仍留在同一个房间。
- 之后,$$$i$$$ 房间的灯重新打开。

教师尚未决定将学生聚集在哪里,因此对于从 $$$1$$$ 到 $$$n$$$ 的每个 $$$i$$$,您应该确定可以聚集在第 $$$i$$$ 咖啡机周围的最大学生人数是多少。

教师可以自行决定以任何顺序关闭任何房间的灯,甚至可以多次关闭同一房间的灯。

请注意,$$$a_0$$$ 和 $$$a_{n+1}$$$ 的值不会影响问题的答案,因此不会将它们的值提供给您。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10\,000$$$) — 测试用例的数量。

在每个测试用例的第一行,有一个整数$$$n$$$ ($$$1 \le n \le 10^6$$$)。

在每个测试用例的第二行中,有整数 $$$a_1, \ldots, a_n$$$ ($$$0 \le a_i \le 10^9$$$) - 咖啡机周围编号为 $$$1, 2, \ldots, n$$$ 的学生人数。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$10^6$$$。

输出

对于每个测试用例,输出 $$$n$$$ 整数 $$$b_1, \ldots, b_n$$$,其中 $$$b_i$$$ 是咖啡机编号 $$$i$$$ 周围可以容纳的最大学生人数。

示例

输入 #1

3
2
8 0
5
2 2 2 2 2
5
0 0 9 0 0

输出 #1

8 4 
4 5 4 5 4 
4 6 9 6 4

注意

我们来分析第一个测试用例:

- 为了最大限度地增加使用 $$$1$$$-st 咖啡机的学生数量,所需要做的就是什么都不做。
- 为了最大限度地增加第 $$$2$$$-nd 咖啡机旁的学生数量,关闭第 $$$1$$$-st 房间的灯一次就足够了。