给定一个由 $$$n$$$ 整数组成的数组 $$$a$$$。您希望将这些 $$$n$$$ 整数分配到两个组 $$$s_1$$$ 和 $$$s_2$$$(组可以为空),以便满足以下条件:
- 对于每个 $$$i$$$ $$$(1 \leq i \leq n)$$$,$$$a_i$$$ 恰好属于一组。
- 值 $$$|sum(s_1)| - |sum(s_2)|$$$ 是所有此类分配整数的方式中可能的最大值。这里 $$$sum(s_1)$$$ 表示组 $$$s_1$$$ 中的数字之和,$$$sum(s_2)$$$ 表示组 $$$s_2$$$ 中的数字之和。
确定 $$$|sum(s_1)| 的最大可能值- |总和(s_2)|$$$。
输入
输入由多个测试用例组成。第一行包含一个整数 $$$t$$$ $$$(1 \leq t \leq 2 \cdot 10^4)$$$ — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ $$$(1 \leq n \leq 10^5)$$$ — 数组 $$$a$$$ 的长度。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1,a_2 \ldots a_n$$$ $$$(-10^9 \leq a_i \leq 10^9)$$$ — 数组 $$$a$$$ 的元素。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2\cdot 10^5$$$。
输出
对于每个测试用例,输出一个整数 - $$$|sum(s_1)| 的最大可能值- |总和(s_2)|$$$。
示例
输入 #1
4 2 10 -10 4 -2 -1 11 0 3 2 3 2 5 -9 2 0 0 -4
输出 #1
0 8 7 11
注意
在第一个测试用例中,我们可以分布为 $$$s_1 = \{10\}$$$, $$$s_2 = \{-10\}$$$。那么该值将是 $$$|10| - |-10| = 0$$$。
在第二个测试用例中,我们可以分布为 $$$s_1 = \{0, 11, -1\}$$$, $$$s_2 = \{-2\}$$$。那么该值将是 $$$|0 + 11 - 1| - |-2| = 10 - 2 = 8$$$。
在第三个测试用例中,我们可以分布为 $$$s_1 = \{2, 3, 2\}$$$, $$$s_2 = \{\}$$$。那么该值将是 $$$|2 + 3 + 2| - |0| = 7$$$。
在第四个测试用例中,我们可以分布为 $$$s_1 = \{-9, -4, 0\}$$$, $$$s_2 = \{2, 0\}$$$。那么该值将是 $$$|-9 - 4 + 0| - |2 + 0| = 13 - 2 = 11$$$。