A. Две группы
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дан массив $$$a$$$, состоящий из $$$n$$$ целых чисел. Вы хотите распределить эти $$$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)| - |sum(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)| - |sum(s_2)|$$$.

Пример
Входные данные
4
2
10 -10
4
-2 -1 11 0
3
2 3 2
5
-9 2 0 0 -4
Выходные данные
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$$$.