Putata 和 Budada 正在组织一场游戏，有 $n$ 名玩家围成一圈。玩家编号从 $0$ 到 $n - 1$，第 $i$ 位玩家与第 $((i - 1) \pmod n)$ 位和第 $((i + 1) \pmod n)$ 位玩家相邻。初始时，第 $i$ 位玩家拥有 $a_i$ 的存款，存款为整数。

在游戏的每一轮中，会发生以下情况：Putata 和 Budada 会选择一名之前未被选择过的玩家 $x$，玩家 $x$ 会将其存款的一半（向下取整）分给他的其中一名相邻玩家。注意，每位玩家只能分享一次存款。

设 $f(i)$ 为第 $i$ 位玩家在经过若干轮（可能为零轮）游戏后，可能拥有的最大存款数。请计算对于每个 $0 \le i < n$ 的 $f(i)$。注意，不同 $i$ 的答案是独立计算的。

输入格式

输入包含多个测试用例。第一行包含一个整数 $T$ ($1 \le T \le 5 \cdot 10^5$)，表示测试用例的数量。

对于每个测试用例，第一行包含一个整数 $n$ ($1 \le n \le 5 \cdot 10^5$)，表示玩家人数。 第二行包含 $n$ 个整数，第 $i$ 个整数 $a_i$ ($0 \le a_i \le 10^9$) 表示第 $i$ 位玩家的初始存款。

保证所有测试用例的 $n$ 之和不超过 $5 \cdot 10^5$。

输出格式

对于每个测试用例，输出一行 $n$ 个整数，表示 $f(0), f(1), \dots, f(n - 1)$。

样例

样例输入 1

3
5
2 1 4 3 5
5
2 1 3 1 2
1
1000000000
1
10
8 15 18 15 13 4 14 4 17 5

样例输出 1

6 5 7 8 8
4 4 5 4 4
1000000000
30 37 41 39 34 27 29 26 31 27