Description

There are several platforms in space. Given the position of each platform, determine which platform you will land on after stepping off each platform’s edges.

Note: If the x-coordinates of some edge of two platforms are the same, then an object falling from the upper platform will not land on the lower one (i.e., each platform covers an open interval, excluding endpoints). Platforms may overlap.

When stepping off a platform, the fall is considered to start just below that platform, so you will not land on a platform of the same height. If there are two platforms with the same height that are both eligible to be landed on, you will land on the one with the smaller index.

Input Format

The first line contains an integer $N$, the number of platforms.

Each of the next $N$ lines contains three integers: the height $H_i$, the left endpoint’s $X$-coordinate $L_i$, and the right endpoint’s $X$-coordinate $R_i$.

Constraints: $1 \le N \le 10^3$, $0 \le H, L, R \le 2 \times 10^4$.

Output Format

Output $N$ lines. For each $i$, output two integers: the index of the platform reached by falling from the left edge of platform $i$, and the index reached by falling from the right edge of platform $i$.

Platforms are numbered from $1$ in the input. If there is no platform below a given edge, output $0$.

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

0 5
1 5
1 5
5 5
0 0

Hint

Translated by ChatGPT 5