370.一步最优

对于如下问题：

• 给定长度为 $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$ 时，该算法能够得到的答案的最小值。

对于 $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$。