Problem name: AmaX In 3D

Problem ID: 19001

Problem setter: Fechete Dan Ionut

Problem input: standard input

Problem output: standard output


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


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



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