World of Cube

Time limit1sMemory limit128 MB

Summary

Given N foci in a box, find the smallest common edge length of axis-aligned cubes centered at the foci whose union covers the whole box.

Level: Medium7 of 10
Topics: Binary search, Geometry, Brute force, Implementation
Solved: No attempts yet

Problem

There is a rectangular box in 3D space, which we call the hall. Inside the hall you are given $N$ points called foci.

For each focus you place one axis-aligned cube centered at that focus, for a total of $N$ cubes. All $N$ cubes must have the same edge length. Cubes may overlap one another, and they may extend outside the hall.

The goal is to cover the entire hall with the union of these $N$ cubes, leaving no gap.

Given the foci, write a program that finds the smallest edge length of the cubes for which the hall can be completely covered.

Input

The input consists of several test cases.

The first line of each test case contains the number of foci $N$ and the hall's dimensions $X$ , $Y$ , $Z$ , separated by spaces. ( $1 \le N \le 50$ , $1 \le X, Y, Z \le 10^9$ ) One corner of the hall is the origin $(0, 0, 0)$ and the opposite corner is $(X, Y, Z)$ .

Each of the next $N$ lines contains the coordinates $x$ , $y$ , $z$ of a focus. ( $0 \le x \le X$ , $0 \le y \le Y$ , $0 \le z \le Z$ )

The last line of the input contains four zeros and must not be processed.

Output

For each test case, print one line in the following format.

k. D

Here $k$ is the test case number (starting from 1) and $D$ is the smallest cube edge length that covers the whole hall. $D$ is always an integer.

Examples3

Example 1

Input

Expected output

1. 4
2. 6

Example 2
Input
```
1 2 2 2
1 1 1
0 0 0 0
```
Expected output
```
1. 2
```
Example 3
Input
```
1 2 2 2
0 0 0
0 0 0 0
```
Expected output
```
1. 4
```