Alice 和 Bob 正在矩阵上玩游戏,该矩阵由 $$$2$$$ 行和 $$$m$$$ 列组成。 $$$j$$$ 列第 $$$i$$$ 行的单元格中包含 $$$a_{i, j}$$$ 硬币。
最初,Alice 和 Bob 都站在牢房 $$$(1, 1)$$$ 中。他们将执行一系列移动以到达单元格 $$$(2, m)$$$。
可能的动作是:
- 向右移动 — 从某个单元格 $$$(x, y)$$$ 到 $$$(x, y + 1)$$$;
- 向下移动 — 从某个单元格 $$$(x, y)$$$ 到 $$$(x + 1, y)$$$。
首先,Alice 进行所有动作,直到达到 $$$(2, m)$$$。她收集她访问的所有单元格(包括起始单元格)中的硬币。
当爱丽丝完成时,鲍勃开始他的旅程。他还执行了到达 $$$(2, m)$$$ 的动作,并收集了他访问过的所有单元格中的硬币,但爱丽丝没有。
游戏的得分是鲍勃收集的硬币总数。
Alice 想要最小化分数。鲍勃想要最大化分数。如果双方都发挥最佳状态,比赛的比分会是多少?
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。
然后是 $$$t$$$ 测试用例的描述。
测试用例的第一行包含一个整数 $$$m$$$ ($$$1 \le m \le 10^5$$$) — 矩阵的列数。
接下来的 $$$2$$$ 行中的第 $$$i$$$ 行包含 $$$m$$$ 整数 $$$a_{i,1}, a_{i,2}, \dots, a_{i,m}$$$ ($$$1 \le a_{i,j} \le 10^4$$$) — 单元格中的硬币数量矩阵第 $$$j$$$ 列中的 $$$i$$$ 行。
所有测试用例的 $$$m$$$ 总和不超过 $$$10^5$$$。
输出
对于每个测试用例,打印一个整数——如果两个玩家都发挥最佳的情况下的游戏得分。
示例
输入 #1
3 3 1 3 7 3 5 1 3 1 3 9 3 5 1 1 4 7
输出 #1
7 8 0
注意
测试用例的路径如下图所示。 Alice 的路径用红色表示,Bob 的路径用蓝色表示。