Problem Description

Given the positions of $n$ cuboids in three-dimensional space, determine how many pairs of cuboids overlap with each other. (If they intersect at only a single point, it is also counted.)

Input Format

The first line contains an integer $n$, representing the number of cuboids.

The next $n$ lines each contain six integers. The first three numbers are the coordinates of the lower-left-bottom vertex of the cuboid, and the last three numbers are the coordinates of the upper-right-top vertex of the cuboid.

Output Format

Output one integer on a single line, representing the number of overlapping cuboid pairs.

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

2

3
15 10 10 15 20 20
10 15 10 20 15 20
10 10 15 20 20 15

3

5
4 4 5 4 3 2
5 3 2 4 3 1
5 4 3 1 1 3
1 4 3 1 5 4
5 5 4 5 4 2

4

Hint

Constraints

For $100\%$ of the testdata, it is guaranteed that $1 \le n \le 10^5$. All coordinates are between $1$ and $999$. Each cuboid is guaranteed to be parallel to the coordinate planes.

Notes

This problem is translated from COCI2006-2007 CONTEST #6 T6 PROSTOR。

Translated by ChatGPT 5