Cube Union Volume

Given N cubes whose edges are parallel to the coordinate axes, compute the union volume of these cubes. Each cube is represented by a quadruple \((x,y,z,r)\), where \(x\), \(y\), \(z\) are the coordinates of the cube's center, and \(r\) is the half-length of its side (i.e. the distance from the center to any face).

A cube represented by \((x,y,z,r)\) covers the region \[ [x-r, x+r] \times [y-r, y+r] \times [z-r, z+r]. \] Calculate the total volume covered by these cubes (i.e. the volume of the union of all cubes). Note that cubes may overlap.

Input constraints: The first line contains an integer \(N\), the number of cubes. Each of the following \(N\) lines contains four integers \(x\), \(y\), \(z\), and \(r\), separated by spaces.

Hint: One possible method is to use a sweep-line (or sweep-plane) technique. For instance, one may discretize the \(x\) dimension and for each slab compute the union area in the \(y\)-\(z\) plane by coordinate compression and area calculation.

inputFormat

The first line contains an integer \(N\) \((1 \le N)\). Each of the next \(N\) lines contains four integers: \(x\), \(y\), \(z\), and \(r\), where the cube extends from \(x-r\) to \(x+r\) in the \(x\) direction (and similarly in the \(y\) and \(z\) directions).

It is guaranteed that all numbers are integers.

outputFormat

Output a single integer, the union volume of the given cubes.

sample

1
0 0 0 1

8