题目描述

在一条水平直线上有 $n$ 个点，从左至右依次标号为 $1$ 到 $n$。

第 $i$ 个点与第 $(i + 1)$ 个点之间的距离为 $a_i$。

对于每个从 $1$ 到 $n$ 的整数 $k$，你需要恰好选择 $k$ 个不同的给定点，使得所有被选中点对之间的距离之和最大。

输入格式

输入包含多组测试数据，第一行包含一个正整数 $T$，表示测试数据组数，最多可达 $1000$。

对于每组测试数据，第一行包含一个整数 $n$，表示点的数量，满足 $2 \leq n \leq 10^5$。

第二行包含 $(n - 1)$ 个正整数 $a_1, a_2, \cdots, a_{n - 1}$，满足 $1 \leq a_i \leq 10^4$。

我们保证所有测试数据中 $n$ 的总和不超过 $10^6$。

输出格式

对于每组测试数据，输出一行包含 $n$ 个整数，其中第 $i$ 个整数表示当 $k = i$ 时的最大距离之和。你应在相邻两个整数之间恰好输出一个空格，并避免该行出现任何末尾空格。

1
5
2 3 1 4

0 10 20 34 48

提示

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

:::align{center} :::

对于 $k = 2$，唯一的最优选择应选取最左侧与最右侧的点；而对于 $k = 3$，一种可能的最优选择可额外包含中间的任意一点。

翻译由 DeepSeek V4 Pro 完成