ACPC10F - World of cubes

no tags 

You’ve been assigned the task of programming a new video game called the World of Cubes. The game is played inside a box-shaped object (mathematically speaking: a rectangular cuboid) which we’ll call the hall. Within the hall, the player is assigned N positions, called focal points.
The player must build N cubes, all parallel to the axes, and each is centered around one of the focal points. The mission is for the N cubes to completely fill the hall. It is acceptable for the cubes to overlap and even to extend beyond the hall. The only restriction is that all the cubes must be of equal side-length. And we would like you to compute the minimum such length.

Input

Your program will be tested on one or more test cases. Each test case is specified using N +1 lines.
The first line specifies four integers: (1 ≤ N ≤ 50) is the number of cubes and (1 ≤ X, Y, Z ≤ 109 ) are the dimensions of the hall. One corner of the hall is at the origin (0, 0, 0), with the opposing corner at (X, Y, Z).
N lines follow, each specifying the coordinate of a focal point using three integers: (0 ≤ x ≤ X), (0 ≤ y ≤ Y ), and (0 ≤ z ≤ Z).
The last test case is followed by a line containing four zeros.

Output

For each test case, print the following line:
k. D
Where k is the test case number (starting at one,) and D is an integer which is the smallest length of the cube edges so that the N cubes would completely fill the hall.

Example

Input:
2 4 4 8
2 2 2
2 2 6
2 4 4 8
2 2 2
2 2 5
0 0 0 0

Output:
1. 4
2. 6


Added by:Omar ElAzazy
Date:2010-11-30
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:ACPC 2010