310465: CF1838A. Blackboard List

A. Blackboard Listtime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

Two integers were written on a blackboard. After that, the following step was carried out $n-2$ times:

• Select any two integers on the board, and write the absolute value of their difference on the board.

After this process was complete, the list of $n$ integers was shuffled. You are given the final list. Recover one of the initial two numbers. You do not need to recover the other one.

You are guaranteed that the input can be generated using the above process.

Input

The first line of the input contains a single integer $t$ ($1 \le t \le 100$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($3 \le n \le 100$) — the size of the final list.

The next line of each test case contains $n$ integers $a_1, a_2, \ldots a_n$ ($-10^9 \le a_i \le 10^9$) — the shuffled list of numbers written on the blackboard.

It is guaranteed that the input was generated using the process described above.

Output

For each test case, output a single integer $x$ — one of the two initial numbers on the blackboard.

If there are multiple solutions, print any of them.

ExampleInput

9
3
9 2 7
3
15 -4 11
4
-9 1 11 -10
5
3 0 0 0 3
7
8 16 8 0 8 16 8
4
0 0 0 0
10
27 1 24 28 2 -1 26 25 28 27
6
600000000 800000000 0 -200000000 1000000000 800000000
3
0 -1000000000 1000000000

Output

9
11
-9
3
8
0
-1
600000000
0

Note

For the first test case, $a$ can be produced by starting with either $9$ and $2$, and then writing down $|9-2|=7$, or starting with $9$ and $7$ and writing down $|9-7|=2$. So $2$, $7$, and $9$ are all valid answers, because they all appear in at least one valid pair.

For the second test case, we can show that the two initial numbers must have been $-4$ and $11$.

For the fourth test case, the starting numbers could have been either $3$ and $3$, or $3$ and $0$, so $3$ and $0$ are both valid answers.

For the fifth test case, we can show that the starting numbers were $8$ and $16$.

题目大意：
一个黑板上最初有两个整数。接着进行了n-2次以下操作：选择黑板上的任意两个整数，并写下它们绝对值差的整数。在此过程结束后，n个整数的列表被随机打乱。你需要根据给定的最终列表恢复出最初两个整数中的一个。保证输入可以通过上述过程生成。

输入数据格式：
第一行包含一个整数t（1≤t≤100），表示测试用例的数量。接下来是每个测试用例的描述。
每个测试用例的第一行包含一个整数n（3≤n≤100），表示最终列表的大小。
下一行包含n个整数a1, a2, …, an（-10^9≤ai≤10^9），表示黑板上写下的被打乱的数字列表。

输出数据格式：
对于每个测试用例，输出一个整数x，表示黑板上最初两个整数中的一个。
如果有多个解，输出其中任意一个。

示例：
输入
```
9
3
9 2 7
3
15 -4 11
4
-9 1 11 -10
5
3 0 0 0 3
7
8 16 8 0 8 16 8
4
0 0 0 0
10
27 1 24 28 2 -1 26 25 28 27
6
600000000 800000000 0 -200000000 1000000000 800000000
3
0 -1000000000 1000000000
```
输出
```
9
11
-9
3
8
0
-1
600000000
0
```

注意：
- 对于第一个测试用例，可以通过选择9和2开始，然后写下|9-2|=7，或者选择9和7开始，然后写下|9-7|=2。所以2、7和9都是有效答案，因为它们都至少出现在一个有效数对中。
- 对于第二个测试用例，可以证明最初两个数必须是-4和11。
- 对于第四个测试用例，起始数可以是3和3，或者3和0，所以3和0都是有效答案。
- 对于第五个测试用例，可以证明起始数是8和16。题目大意： 一个黑板上最初有两个整数。接着进行了n-2次以下操作：选择黑板上的任意两个整数，并写下它们绝对值差的整数。在此过程结束后，n个整数的列表被随机打乱。你需要根据给定的最终列表恢复出最初两个整数中的一个。保证输入可以通过上述过程生成。 输入数据格式： 第一行包含一个整数t（1≤t≤100），表示测试用例的数量。接下来是每个测试用例的描述。 每个测试用例的第一行包含一个整数n（3≤n≤100），表示最终列表的大小。 下一行包含n个整数a1, a2, …, an（-10^9≤ai≤10^9），表示黑板上写下的被打乱的数字列表。 输出数据格式： 对于每个测试用例，输出一个整数x，表示黑板上最初两个整数中的一个。 如果有多个解，输出其中任意一个。 示例： 输入 ``` 9 3 9 2 7 3 15 -4 11 4 -9 1 11 -10 5 3 0 0 0 3 7 8 16 8 0 8 16 8 4 0 0 0 0 10 27 1 24 28 2 -1 26 25 28 27 6 600000000 800000000 0 -200000000 1000000000 800000000 3 0 -1000000000 1000000000 ``` 输出 ``` 9 11 -9 3 8 0 -1 600000000 0 ``` 注意： - 对于第一个测试用例，可以通过选择9和2开始，然后写下|9-2|=7，或者选择9和7开始，然后写下|9-7|=2。所以2、7和9都是有效答案，因为它们都至少出现在一个有效数对中。 - 对于第二个测试用例，可以证明最初两个数必须是-4和11。 - 对于第四个测试用例，起始数可以是3和3，或者3和0，所以3和0都是有效答案。 - 对于第五个测试用例，可以证明起始数是8和16。