월드 오브 큐브

상근이는 세계 최고의 인기 게임 월드 오브 큐브를 만드는 게임 회사에 취직한다.

게임은 박스 형태의 물체 안에서 진행된다. (박스를 수학적으로 말하면 직육면체) 게임에서 이 박스 안을 홀이라고 부른다. 홀 안에 있는 플레이어에게는 초점 N개가 주어진다. 플레이어는 중심이 초점 중 하나이고, 축에 평행한 정육면체를 N개 만들어야 한다.

게임의 목표는 N개의 정육면체를 이용해서 홀을 가득 채우는 것이다. 정육면체는 겹쳐도 되고, 홀의 경계를 넘어가도 된다. 하지만, 정육면체는 모두 같은 크기를 가져야 한다.

초점이 주어졌을 때, 홀을 가득 채우는 방법 중, 정육면체의 변의 길이가 가장 작은 것을 구하는 프로그램을 작성하시오.

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 초점의 개수 N과 홀의 크기 X, Y, Z가 주어진다. (1 ≤ N ≤ 50, 1 ≤ X,Y,Z ≤ 109) 홀의 한 꼭짓점은 원점 (0,0,0)에 있고, 반대편 꼭짓점은 (X,Y,Z) 이다.

다음 N개 줄에는 초점의 좌표 x, y, z가 주어진다. (0 ≤ x ≤ X, 0 ≤ y ≤ Y, 0 ≤ z ≤ Z)

입력의 마지막 줄에는 0이 네 개 주어진다.

각 테스트 케이스에 대해서, 다음을 출력한다.

k. D

k는 테스트 케이스의 번호이고, D는 게임의 목표를 달성하는 정육면체의 변의 길이이다. D는 정수이다.