Problem name: AmaX In 3D

Problem ID: 19001

Problem setter: Fechete Dan Ionut

Problem input: standard input

Problem output: standard output

Background:

Last year at the same contest my brother came up with the problem AmaX and I had to "encrease it's ugliness"

Problem:

You are given a box .We shall consider that one of the corners lays in the point with the coordinates (0,0,0);You are also given the coordinates of the oposite corner of the box. Next we consider D holes in the box represented by D spheres. You have to find the cube with the biggest volume that is complete(it doesn't intersect with any hole,it doesn't contain one and the coordinates of the cubes corners are integers);

Input data:

The first line of the input file contains three integers X Y Z the coordinates of the oposite corner The second line contais an integer D the number of spheres The next D lines contain four integers xi,yi,zi,ri the coordinate of the center of the i-th sphere an it's radius

Output data:

The only line of the output file should contain V the volume of the biggest cube

Example:

input:

6 6 6
4
1 1 3 1
6 3 3 1
3 4 3 1
4 1 3 1

output:

8

Restrictions:

• 1<=X,Y,Z<=50
• 0<=D<=50
• 0<=xi<=X
• 0<=yi<=Y
• 0<=zi<=Z
• 0<=ri<=max(X,Y,Z)
• X*Y*Z*D<3000000
• Time limit: 2 seconds
• Output limit: 1 MB
• Data limit: 2 MB
• Stack limit: 1 MB