在水平直线上有 $n$ 个点，从左到右依次编号为 $1$ 到 $n$。 第 $i$ 个点与第 $(i+1)$ 个点之间的距离为 $a_i$。 对于每个从 $1$ 到 $n$ 的整数 $k$，你需要从给定的点中恰好选择 $k$ 个不同的点，使得所选点对之间的距离之和最大。

输入格式

输入包含多组测试数据。第一行包含一个正整数 $T$，表示测试数据的组数，其中 $T \le 1000$。 对于每组测试数据，第一行包含一个整数 $n$，表示点的数量，其中 $2 \le n \le 10^5$。 第二行包含 $(n-1)$ 个正整数 $a_1, a_2, \dots, a_{n-1}$，其中 $1 \le a_i \le 10^4$。 保证所有测试数据中 $n$ 的总和不超过 $10^6$。

输出格式

对于每组测试数据，输出一行，包含 $n$ 个整数，其中第 $i$ 个整数表示 $k=i$ 时的最大距离之和。每两个相邻数字之间应恰好输出一个空格，且行末不应有任何多余的空格。

样例

输入格式 1

1
5
2 3 1 4

输出格式 1

0 10 20 34 48

说明

下图描述了样例测试数据。

对于 $k=2$ 的情况，唯一的最佳选择是选择最左侧和最右侧的点；而对于 $k=3$ 的情况，一种可能的最佳选择是包含中间的任意一个额外点。