CF2057H Coffee Break

T-Generation 的课程十分漫长。在一天中，必须安排时间来分析训练和专题比赛，讲解新内容，并在可能的情况下，举行一个小型研讨会。因此，课间休息时学生们会去喝咖啡或聊天。 走廊上总共有 $n+2$ 台咖啡机，依次排列。咖啡机编号从 $0$ 到 $n+1$，当休息开始时，第 $i$ 台咖啡机周围聚集了 $a_i$ 名学生。 由于学生们说话声太大，老师需要进行一个重要的通知。因此，他们希望将尽可能多的学生聚集到某一台咖啡机周围。不过，老师们懒得亲自去召集学生，想出了一种巧妙的方法： - 随时可以选择房间 $i$（$1 \le i \le n$）并关闭那里的灯； - 如果该房间有 $x$ 名学生，关灯后，$\lfloor \frac{1}{2} x \rfloor$ 名学生会去左边的房间 $(i-1)$，另外 $\lfloor \frac{1}{2} x \rfloor$ 名学生会去右边的房间 $(i+1)$； - 如果 $x$ 是奇数，则有一名学生留在原位； - 随后再次打开房间 $i$ 的灯。 老师们尚未决定最终要在何处聚集学生，因此需要计算，对于每个 $i$ 从 $1$ 到 $n$，在第 $i$ 台咖啡机周围最多能聚集多少名学生。 老师们可以任意顺序、任意次数选择关灯，可以在同一个房间多次操作。 需要注意的是，$a_0$ 和 $a_{n+1}$ 的值对结果没有影响，因此不需要考虑这两个值。

第一行输入一个整数 $t$（$1 \le t \le 10\,000$），表示测试用例的数量。 每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 10^6$）。 接下来一行是 $n$ 个整数 $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$ 台咖啡机周围的学生人数最大化，只需要保持现状。 - 为了让第 $2$ 台咖啡机周围的学生人数最大化，只需在第 $1$ 个房间关一次灯。 **本翻译由 AI 自动生成**