Taco: Minimum Difference Partition

Given an array of integers, you are required to split the array into two groups such that the absolute difference between the sums of the two groups, i.e. (|\sum_{i \in G_1} a_i - \sum_{j \in G_2} a_j|), is minimized. Every element must belong to exactly one group.

For example, given the array [1, 6, 5, 11], one acceptable partition is Group 1: [11] and Group 2: [1, 6, 5] since (|11 - (1+6+5)| = 1) is minimal. Solve the problem by outputting the two groups on separate lines for each test case.

inputFormat

The first line contains an integer (T) representing the number of test cases. Each test case consists of two lines. The first line contains an integer (n), the number of elements in the array. The second line contains (n) space-separated integers.

outputFormat

For each test case, output two lines. The first line lists the elements of the first group and the second line lists the elements of the second group. The partition should minimize the absolute difference (|\sum_{i \in G_1} a_i - \sum_{j \in G_2} a_j|).## sample

3
4
1 6 5 11
3
10 20 15
5
2 4 7 8 10

11
1 6 5
20
10 15
4 10
2 7 8