Programming Problem #38
"Cube Intersections"

The problem is simple: find the volume of the intersection of one or more cubes.

The input consists of one or more sets of cubes. Each set consists of a line containing a nonnegative integer N, representing the number of cubes in the set, followed by N lines describing the cubes in the set. A zero value of N signals the end of the input. Each cube description contains four nonnegative integers x, y, z, and d, separated by spaces. The corner of the cube closest to the origin is at (x, y, z), and its height, width, and depth are d. The values of x, y, and z will not exceed 1,000,000, and d will not exceed 100. The edges of all cubes are parallel to the axes. For each set of cubes output a single line containing the volume of the intersection of the cubes.

Input must be read from the file "prob38.in", and output must be written to the file "prob38.out". All output to the screen will be ignored.

Example Input

<BOF>
2
0 0 0 10
9 1 1 5
3
0 0 0 10
9 1 1 5
8 2 2 3
0
<EOF>

Example Output

25
9

A version of this problem originally appeared in the 1993 ACM Mid-Central Regionals