Description

Recently, Mr. A has been doing special training on data structures to prepare for the NOI Qualifier team selection. During the training, he encountered the classic problem “Union Area of Rectangles”: given $N$ rectangles whose sides are parallel (perpendicular) to the coordinate axes, find the total area covered by these rectangles. Mr. A built a segment tree along the $y$-axis and then used a sweep line along the $x$-axis to compute it, easily getting AC, with time complexity $O(N\log N)$.

To further strengthen the training, Mr. A extended the problem to three-dimensional space: given $N$ cubes whose edges are parallel (perpendicular) to the coordinate axes, find the total volume covered by these cubes. To simplify the problem, assume all cubes are axis-aligned regular cubes. Use a quadruple $(x, y, z, r)$ to represent a cube, where $x, y, z$ are the coordinates of the cube’s center, and $r$ is the distance from the center to each face of the cube (i.e. half of the cube’s side length).

This time Mr. A got stuck, so he asks you—the future gold medalist—to help him.

Input Format

The first line contains a positive integer $N$.

The next $N$ lines each contain four integers $x, y, z, r$.

Output Format

Output the total covered volume.

3
0 0 0 3
1 -1 0 1
19 3 5 6

1944

Hint

Constraints: $N \leq 100, -1000 \leq x,y,z \leq 1000, r \leq 200$.

Translated by ChatGPT 5