시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 512 MB 2 2 2 100.000%

문제

Bob has 12 sticks of lengths l1, l2, . . . , l12. He wants to use some sticks to form triangles as many as possible. Each triangle can be built by three different sticks la, lb, lc such that la + lb > lc, la + lc > lb and lb + lc > la. 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 l1, l2, . . . , l12.

출력

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.

제한

  • 1 ≤ T ≤ 6000
  • 1 ≤ l1, l2, . . . , l12 ≤ 109

예제 입력 1

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

예제 출력 1

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