Calculating the Union Volume of Cube-Covered Space from SERCOI-308 Satellites

SERCOI (Space-Earth Resource Cover-Observe Institute) has developed a new satellite, SERCOI-308, which can monitor a specific cubic volume in a 3D space. The satellite is positioned at the center of its coverage cube.

A satellite is described by a quadruple \( (x, y, z, r) \), where \((x,y,z)\) is the center of the cube and \(r\) is the distance from the center to each face (i.e. half the length of the side). Thus, the side length of the cube is \(2r\) and its volume is \((2r)^3\). In a network of satellites, the coverage regions (cubes) may overlap. Your task is to compute the total volume covered by a given set of satellites, counting overlapping regions only once.

Note: The cubes are axis-aligned with the coordinate axes.

inputFormat

The input begins with an integer \(N\) (the number of satellites). Each of the next \(N\) lines contains four space-separated numbers \(x\), \(y\), \(z\), and \(r\), describing one satellite. All values are given in a consistent unit.

outputFormat

Output a single number representing the total volume covered by the satellites.

sample

1
0 0 0 1

8