Horizontally Visible Segments

Time limit1sMemory limit128 MB

Summary

Given disjoint vertical segments, count triangles formed by triples that are pairwise horizontally visible using a sweep and visibility structure.

Level: Hard8 of 10
Topics: Sorting, Geometry, Segment tree
Solved: No attempts yet

Problem

You are given a set of pairwise disjoint vertical line segments in the plane (no two segments share any point).

Two segments are said to be horizontally visible if they can be joined by a horizontal segment that has no common point with any other vertical segment. Three distinct vertical segments form a triangle of segments if each of the three pairs among them is horizontally visible.

For each data set, read the description of a set of vertical segments and report how many triangles of segments it contains.

Input

The first line contains one positive integer $d$ , the number of data sets, with $1 \le d \le 20$ . The data sets follow.

The first line of each data set contains one integer $n$ with $1 \le n \le 8000$ , the number of vertical segments. Each of the next $n$ lines contains three non-negative integers $y_i'$ , $y_i''$ , $x_i$ separated by single spaces: the $y$ -coordinate of the lower endpoint, the $y$ -coordinate of the upper endpoint, and the $x$ -coordinate of the $i$ -th segment. The coordinates satisfy $0 \le y_i' < y_i'' \le 8000$ and $0 \le x_i \le 8000$ , and the segments are pairwise disjoint.

Output

Print exactly $d$ lines, one per data set. The $i$ -th line must contain a single integer: the number of triangles of segments in the $i$ -th data set.

Examples9

Example 1
Input
```
1
5
0 4 4
0 3 1
3 4 2
0 2 2
0 2 3
```
Expected output
```
1
```
Example 2
Input
```
1
1
0 5 0
```
Expected output
```
0
```
Example 3
Input
```
1
3
0 10 0
0 3 1
0 10 2
```
Expected output
```
1
```
Example 4
Input
```
1
3
0 10 0
0 10 1
0 10 2
```
Expected output
```
0
```

Example 5

Input

Expected output

1
0
1

Example 6
Input
```
1
3
0 3 1
3 6 2
0 6 3
```
Expected output
```
1
```
Example 7
Input
```
1
4
0 20 0
0 1 1
3 4 1
6 7 1
```
Expected output
```
0
```
Example 8
Input
```
1
5
0 1 0
0 1 1
0 1 2
0 1 3
0 1 4
```
Expected output
```
0
```
Example 9
Input
```
1
2
0 2 5
5 7 5
```
Expected output
```
0
```