택배 상하차 Output Only Compilation commands

3차원 세상에서 운영되는 나나택배에는 오늘도 많은 택배 물건들이 들어오고 있습니다. 물류비를 절약하기 위해, 나나는 고정된 크기의 트럭만을 운용합니다. 각 트럭 내에는 물건을 보관할 수 있는 30 × 30 × 30 크기의 정육면체 형태의 공간이 있습니다. 이 공간은 3차원 좌표계로 표현할 수 있으며, 공간의 한 꼭짓점은 원점이며, 정육면체의 변 중 세 개는 각각 x축, y축, z축과 겹치며 좌표가 증가하는 방향으로 놓여 있습니다. 각 택배 박스는 직육면체 모양으로, 트럭 내의 공간에 넣을 때 공간의 벽면에 평행하기만 하다면 원하는 대로 회전하여 넣을 수 있습니다. 모든 택배 박스들의 부피의 합은 항상 30 × 30 × 30 = 27, 000입니다.

만약 박스들을 트럭 내의 공간 안에 쌓는 것이 쉽지 않을 경우, 공간의 크기를 각 방향(x축, y축, z축)으로 최대 1만큼 늘리는 것이 허용됩니다. 단 부피를 늘리는 데에는 비용이 들기 때문에, 크기를 한 방향에 대해서 1 늘릴 때마다 점수는 로 감소합니다.

입력 형식

첫째 줄에 테스트 케이스의 수 T = 25가 주어집니다.

각 테스트 케이스의 첫 줄에는 택배 상자의 개수 N이 주어집니다. 다음 N개의 줄에는 박스들의 정보가 주어지는데, 이 중 i (1 ≤ i ≤ N)번째 줄에는 i번째 택배 상자의 크기를 나타내는 30 이하의 자연수 X_i, Y_i, Z_i가 공백을 사이로 두고 주어집니다.

출력 형식

각 테스트 케이스에 대해, 첫 번째 줄에는 트럭 내 택배 수납 공간의 크기를 나타내는 30 이상 31 이하의 자연수 세 개 TX, TY, TZ를 공백을 사이로 두고 출력합니다. 단, 조건에 맞는 답을 찾지 못한 경우에는 한 줄에 "-1 -1 -1"만을 출력하고 이 테스트 케이스의 출력을 중단합니다.

만약 조건에 맞는 답을 찾았다면, N개의 줄을 출력해야 하는데, 이 중 i (1 ≤ i ≤ n)번째 줄에는 6개의 정수 sx_i, sy_i, sz_i, fx_i, fy_i, fz_i (0 ≤ sx_i < fx_i ≤ TX, 0 ≤ sy_i < fy_i ≤ TY, 0 ≤ sz_i < fz_i ≤ TZ) 를 출력합니다. 이는 i번째 택배 박스가 차지하는 직육면체 공간의 상반된 위치에 놓인 두 꼭짓점을 나타냅니다. 임의의 두 택배 박스가 차지하는 공간은 서로 닿을 수 있지만 겹치면 안 됩니다. 출력하는 택배 박스의 순서는 입력받는 순서와 일치해야 합니다.

채점 방식

각 테스트 케이스에 대해 아래와 같이 점수가 부여됩니다.

제출 방법

여기에 주어진 입력 파일을 내려받습니다. 이 입력 파일에 대한 출력 파일을 제출하면 됩니다. 파일을 압축해서 제출하시려면, 출력 파일명을 B.out로 두신 후 압축하셔야 합니다.

예제

<tr><td><samp>3<br>4<br>15 15 30<br>15 15 30<br>15 30 15<br>30 15 15<br>1<br>30 30 30<br>8<br>29 29 29<br>29 29 1<br>29 29 1<br>29 29 1<br>1 1 29<br>1 1 29<br>1 1 29<br>1 1 1</samp></td><td><samp>30 30 30<br>0 0 0 15 30 15<br>15 0 0 30 30 15<br>15 0 15 30 30 30<br>0 0 15 15 0 30<br>-1 -1 -1<br>31 30 30<br>0 0 0 29 29 29<br>29 0 0 30 1 29<br>0 29 0 1 30 29<br>0 0 29 29 29 30<br>30 0 0 31 1 29<br>30 1 0 31 2 29<br>30 2 0 31 3 29<br>30 3 0 31 4 1</samp></td></tr></tbody>

입력 예시	출력 예시

각 테스트 케이스에 대해 4, 0, 1점을 받아서 총 점수는 5점입니다.