Chitanda 拥有一个包含 $n$ 个整数的序列 $a_1, a_2, \dots, a_n$，她想和 Skywalkert 玩一个游戏。

首先，Chitanda 会选择一个参数 $k$，并移除 $a_{k+1}, a_{k+2}, \dots, a_n$。这样序列 $a$ 中就恰好剩下 $k$ 个整数。

然后，Skywalkert 可以从 $a$ 中选择一个子序列并将其移除。假设选出的子序列为 $a_{p_1}, a_{p_2}, \dots, a_{p_m}$。他必须确保 $p_1 < p_2 < \dots < p_m$ 且 $a_{p_1} \le a_{p_2} \le \dots \le a_{p_m}$。

Skywalkert 最多可以进行上述操作 5 次。他的得分为这不超过 5 次操作中选出的所有整数之和。

对于 Chitanda 选择的每一个可能的参数 $k$，请编写一个程序来帮助 Skywalkert 计算他能达到的最大得分。

输入格式

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

每个测试用例的第一行包含一个整数 $n$ ($1 \le n \le 100\,000$)，表示序列的长度。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$)，表示该序列。

保证所有测试用例中 $n$ 的总和不超过 $500\,000$。

输出格式

对于每个测试用例，输出一行，包含 $n$ 个整数 $s_1, s_2, \dots, s_n$，其中 $s_i$ 表示当 $k = i$ 时 Skywalkert 能达到的最大得分。

样例

输入 1

1
8
8 7 6 5 1 3 2 4

输出 1

8 15 21 26 27 30 30 34