Partition the List of Integers

You are given an array of integers. Your task is to partition the array into two subsets (S_1) and (S_2) such that the absolute difference between their sums, (|\sum_{a\in S_1}a - \sum_{b\in S_2}b|), is minimized. Then, output two integers: the smaller sum first and the larger sum second. Note that the array might be empty or contain only a single element. This problem is NP-hard and the input size is guaranteed to be small.

inputFormat

The input is read from standard input (stdin). The first line contains an integer (T) denoting the number of test cases. Each test case begins with an integer (n) which is the number of elements in the list. The following line contains (n) space-separated integers. If (n = 0), the next line will be empty.

outputFormat

For each test case, output a single line containing two space-separated integers: the sum of the subset with the smaller sum and the sum of the subset with the larger sum.## sample

2
5
1 2 3 4 5
1
10

7 8
0 10