Problem F
Rocks on a Plane

Dr. Andrew Carmen Morgan, the world’s leading expert on African rocks, has traveled to the Angolan Central Museum (ACM) to see the newest collection of rocks that have been discovered. After inspecting them all, he is very interested in researching these rocks more, and after receiving the museum’s permission, has decided to take the rocks back to the United States. After the rock transporter inspects the rocks that Dr. Morgan wants to take back to the US, he informs Dr. Morgan that they will need to put the rocks onto two separate planes as the rocks are too heavy to place on one. Dr. Morgan is interested in devising an algorithm to determine which rocks to put in each plane such that weight of the total weight of the rocks in each plane is as close to equal as possible, and the number of rocks in each plane does not differ by more than 1. You can assume that the rocks weigh between $1$ and $450$ pounds, and there are no more than 100 rocks.

Input

The first line consists of the number of test cases, $T$, where $T \leq 20$. Each test case begins with an integer $N$, the number of rocks ($ 1 \leq N \leq 80$). The next $N$ lines consist of an integer $W$, the weight of the corresponding rock ($1 \leq W \leq 300$).

Output

For each test case, on the same line, output the total weight of the rocks in each plane, separated with a space, with the lightest weight first, and the heaviest weight second. If they both weight the same weight, it does not matter which one you output first.

1
4
100
200
300
170

370 400