Platform Falling Simulation

In a 2D space (with platforms parallel to the x-axis), you are given n platforms. The i-th platform is represented by three integers L_i, R_i and Y_i, where the platform spans an open interval on the x-axis (L_i, R_i) (i.e. the endpoints are not included) and is located at height Y_i.

An object falls vertically downward from each platform’s left and right edge. Specifically, for a given platform i:

• The left drop occurs at x = L_i.
• The right drop occurs at x = R_i.

When an object falls, it is considered to start falling immediately below the platform (i.e. it will not land on any platform at the same height as the starting one). The object will land on the first platform below whose horizontal open interval (i.e. (L, R)) contains the x-coordinate from which it fell. Note that if the falling x-coordinate is exactly equal to the left or right endpoint of a platform, it is not counted as landing on that platform. Platforms may overlap.

If there exist two or more candidate platforms at the same highest height (i.e. the same Y value) that the object could fall onto, the object will land on the one with the smallest index (the platforms are given in input order, 1-indexed).

Your task is to determine, for every platform, which platform the object will land on when falling from its left edge and from its right edge respectively. If the object does not land on any platform, output -1 for that drop.

Mathematical formulation:

For each platform i with parameters \(L_i, R_i, Y_i\), for each drop position \(x = L_i\) or \(x = R_i\), find a platform j such that:

[ L_j < x < R_j \quad \text{and} \quad Y_j < Y_i, ]

and among all such platforms choose the one with the maximum Y (if there is a tie, choose the one with the smallest index). If no such platform exists, output \(-1\).

inputFormat

The first line contains a single integer n (1 ≤ n ≤ 10⁵), representing the number of platforms.

Each of the following n lines contains three integers L, R, and Y (with L < R), representing the left endpoint, right endpoint and the height of a platform respectively.

Platforms are 1-indexed and may overlap.

outputFormat

Output n lines. The i-th line contains two space-separated integers:

• The first integer is the index of the platform where the object lands when falling from the left edge of platform i.
• The second integer is the index of the platform where the object lands when falling from the right edge of platform i.

If the object does not land on any platform, output -1 for that drop.

sample

3
1 5 10
2 7 8
0 3 6

3 2
3 -1
-1 -1

</p>