A15562 | Two Groups

You are given an array $a$ consisting of $n$ integers. You want to distribute these $n$ integers into two groups $s_1$ and $s_2$ (groups can be empty) so that the following conditions are satisfied:

- For each $i$ $(1 \leq i \leq n)$ , $a_i$ goes into exactly one group.
- The value $|sum(s_1)| - |sum(s_2)|$ is the maximum possible among all such ways to distribute the integers.Here $sum(s_1)$ denotes the sum of the numbers in the group $s_1$ , and $sum(s_2)$ denotes the sum of the numbers in the group $s_2$ .

Determine the maximum possible value of $|sum(s_1)| - |sum(s_2)|$ .

The input consists of multiple test cases. The first line contains a single integer $t$ $(1 \leq t \leq 2 \cdot 10^4)$ — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $n$ $(1 \leq n \leq 10^5)$ — the length of the array $a$ .

The second line of each test case contains $n$ integers $a_1,a_2 \ldots a_n$ $(-10^9 \leq a_i \leq 10^9)$ — elements of the array $a$ .

It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot 10^5$ .

For each test case, output a single integer — the maximum possible value of $|sum(s_1)| - |sum(s_2)|$ .