Our company is shipping cargo with total weight s. The shipping company prepared two ships. Both have a maximum capacity of s∕2. Unfortunatelly our cargo is already packed into n containers of various weights. We are not able to open the containers, so we need to decide which containers should go on which ship.
That sounds as a hard problem (especially to computer scientists). Luckily, our insurance policy makes it possible to skip shipping one container.
Problem specification
You are given n positive integers with sum s. Erase at most one of them, and split the remaining ones into two groups. The sum of numbers in each group must not exceed s∕2.
Input specification
The first line of the input file contains an integer t specifying the number of test cases. Each test case is preceded by a blank line.
Each test case consists of two lines. The first line contains the number n of containers. The second line contains n positive integers: the weights of containers. The containers are labeled 1 through n in the order in which they appear in the input.
In the easy data set all test cases have n ≤ 20. In the hard data set we have n ≤ 15000.
Output specification
For each test case output two lines. Each line should describe the cargo of one ship. The first number in the line must be the number of containers in the ship’s cargo. The rest of the line should contain the labels of all containers carried by the ship, in any order. Any valid solution will be accepted.
Example
First test case:
We have four containers with weights 10, 20, 30, and 71. Therefore s = 10 + 20 + 30 + 71 = 131,
and each ship will carry at most 131∕2 = 65.5. In the solution described above we put container
#1 on the first ship, containers #2 and #3 on the second ship, and we throw away container #4.
(Another valid solution is to put the first three containers on the same ship and to leave the other ship
empty.)
Second test case:
Note that we are not required to throw away one of the containers. Sometimes we may be able to
ship all of them. (But of course, there are other valid solutions that only ship three of the four
containers.)