Under construction

Still being built. Things may change

Rectangles in Three Dimensions

Time limit1sMemory limit128 MB

Summary
Given N axis-aligned rectangles in 3D each parallel to one coordinate plane, count pairs of rectangles that intersect in at least one point.
Level

Hard8 of 10

Topics
Geometry, Sorting, Segment tree, Implementation
Solved
No attempts yet

Problem

There are N rectangles in three-dimensional space. Each rectangle is parallel to exactly one of the XY, YZ, and ZX planes.

Each rectangle is given by the coordinates of two opposite vertices. Two rectangles are considered to intersect if they share at least one point. Sharing only an edge or only a vertex also counts.

Find the number of intersecting pairs of rectangles.

Input

The first line contains the number of rectangles N. (1 ≤ N ≤ 100,000)

Each of the next N lines contains six integers x1 y1 z1 x2 y2 z2 describing one rectangle. The first three integers are the coordinates of one vertex, and the next three integers are the coordinates of the opposite vertex.

Every coordinate is an integer from 1 to 999, inclusive. Because each rectangle is parallel to one coordinate plane, exactly one of the three coordinate values is the same for the two given vertices.

Output

Print the number of intersecting pairs of rectangles.

Examples3

  1. Example 1

    Input
    3
1 1 1 1 3 3
1 3 3 1 6 6
1 4 4 1 5 5
    Expected output
    2

  2. Example 2

    Input
    3
15 10 10 15 20 20
10 15 10 20 15 20
10 10 15 20 20 15
    Expected output
    3

  3. Example 3

    Input
    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
    Expected output
    4