题目描述

对于如下问题：

• 给定长度为 $n$ 的数列 $a_1, \ldots, a_n$（其中 $a_i$ 可能为负数）以及一个正整数 $m$。
• 你需要选择不超过 $m$ 个数列 $a$ 的下标区间 $[l_j, r_j]$，且确保它们互不相交。
• 你需要最大化选择的区间中的元素之和的总和，即最大化 $\sum_j \sum_{i = l_j}^{r_j} a_i$。

考虑该贪心算法（并不正确）：

• 重复如下过程 $m$ 次：
• 在所有与当前已选择的区间不相交的区间（包括空区间）中，选择一个元素之和最大的区间。
  • 如果有多个元素之和最大的区间，从中任意选择一个。
  • 注：若选择了空区间，等价于中止过程，即选择的区间数量不超过 $m$ 个。
• 将如上过程中选择的所有非空区间中的元素之和作为答案。

现给定 $n$ 和数列 $a_1, \ldots, a_n$，对于每个 $m \in [1, n]$，请求出该算法可能得到的答案（即区间和的总和）的最大值和最小值。

输入格式

本题输入包含多组数据。

第一行，一个正整数 $T$，表示数据组数。对于每组数据：

• 第一行，一个正整数 $n$。
• 第二行，$n$ 个整数 $a_1, \ldots, a_n$。

输出格式

对于每组数据：

• 第一行，$n$ 个整数，第 $i$ 个整数表示当 $m = i$ 时，该算法能够得到的答案的最大值；
• 第二行，$n$ 个整数，第 $i$ 个整数表示当 $m = i$ 时，该算法能够得到的答案的最小值。

5
5
1 -1 1 -1 1
5
2 -2 2 -1 2
6
3 1 -4 1 -5 9 
13
1 1 -4 5 -1 -4 1 9 1 9 -8 1 0
16
1 -8 2 -7 3 -6 4 -5 5 -4 4 -3 3 -2 2 -1

1 2 3 3 3
1 1 1 1 1
3 5 5 5 5
3 3 3 3 3
9 13 14 14 14 14
9 13 14 14 14 14
20 25 27 28 28 28 28 28 28 28 28 28 28
20 22 23 23 23 23 23 23 23 23 23 23 23
5 9 13 16 19 21 23 24 24 24 24 24 24 24 24 24
5 9 12 14 15 15 15 15 15 15 15 15 15 15 15 15

提示

【样例解释】

对于第一组数据，

• 一种取到最大值的方案为，依次选择区间 $[1,1],[3,3],[5,5],\varnothing, \varnothing$；
• 一种取到最小值的方案为，依次选择区间 $[1,5],\varnothing,\varnothing,\varnothing,\varnothing$。

对于第二组数据，

• 一种取到最大值的方案为，依次选择区间 $[3,5],[1,1],\varnothing,\varnothing,\varnothing$；
• 一种取到最小值的方案为，依次选择区间 $[1,5],\varnothing,\varnothing,\varnothing,\varnothing$。

需要注意：在第一次更新时，无法选择区间 $[1,1],[1,3],[3,3]$ 等，因为它们不满足区间和在所有 $S$ 中的区间内最大（即 $= 3$）。在任意一次更新时，都无法选择区间 $[2,2]$，因为其区间和为 $-2$，而 $-2 < 0$（即空区间的区间和）。

对于第三组数据，只有唯一的选择方案，即依次选择区间 $[6,6],[1,2],[4,4],\varnothing,\varnothing,\varnothing$。

【数据范围】

本题采用捆绑测试。

对于 $100 \%$ 的数据，$1 \le T \le 10^4$，$1 \le n \le 10^5$，$\sum n \le 5 \times 10^{5}$，$|a_i| \le 10^9$。