409646: GYM103652 K Sticks

Bob has $$$12$$$ sticks of lengths $$$l_1, l_2, \ldots, l_{12}$$$. He wants to use some sticks to form triangles as many as possible. Each triangle can be built by three different sticks $$$l_a, l_b, l_c$$$ such that $$$l_a + l_b > l_c$$$, $$$l_a + l_c > l_b$$$ and $$$l_b + l_c > l_a$$$. If each stick can be used for at most one triangle, how many triangles can he build at most? Also, could you please find a way to build them all?

The input contains several test cases. The first line contains an integer $$$T$$$ indicating the number of test cases. The following describes all test cases. For each test case:

The only line contains twelve integers $$$l_1, l_2, \ldots, l_{12}$$$.

• $$$1 \leq T \leq 6000$$$
• $$$1 \leq l_1, l_2, \ldots, l_{12} \leq 10^9$$$

For each test case, firstly output a line containing "Case #x: m" (without quotes), where x is the test case number starting from $$$1$$$, and m is the maximum number of triangles that can be built.

Then, output m lines, each line of which contains three integers, representing three side lengths of a triangle.

If there are many optimal solutions, please output any of them. Note that every stick for each test case can be used at most once, and every two adjacent integers in a line of the output should be separated by one space.

5
1 2 1 3 1 4 1 5 1 6 1 7
1 2 3 4 5 6 7 8 9 10 11 12
1 2 3 5 8 13 21 34 55 89 144 233
2 3 6 15 27 59 72 83 121 159 201 234
2 2 4 8 16 32 64 128 256 512 1024 1281

Case #1: 4
1 1 1
4 3 2
1 1 1
6 7 5
Case #2: 3
6 5 4
10 12 11
9 8 7
Case #3: 0
Case #4: 2
83 121 72
234 159 201
Case #5: 1
1024 1281 512