Non-Intersecting Star Pairing

You are given n stars in the sky, where the i-th star is located at \( (x_i,y_i) \). Your task is to connect the stars with straight line segments such that:

• Each star is used as an endpoint of exactly one segment.
• All segments are pairwise non‐intersecting (they do not intersect, not even at their endpoints).
• If a segment connects two stars, denote its left endpoint (the one with the smaller \( x \)-coordinate) as \( (x_l,y_l) \) and its right endpoint as \( (x_r,y_r) \). The objective is to choose a pairing so that the total sum of \( |x_l-x_r| \) over all segments is minimized.

If a valid pairing exists (note that since each segment uses two stars, a necessary condition is that \( n \) is even), output the connection scheme. Otherwise, report that there is no solution.

inputFormat

The first line contains an integer \( n \) representing the number of stars.

Each of the following \( n \) lines contains two integers \( x_i \) and \( y_i \), the coordinates of the \( i \)-th star.

\( 1 \le n \le 10^5 \); it is not guaranteed that a solution exists unless \( n \) is even.

outputFormat

If a valid connection scheme exists, output \( n/2 \) lines. Each line should contain two integers representing the 1-based indices of two stars that are paired. The pairing must satisfy the non-intersecting condition and the sum of \( |x_l-x_r| \) over all segments must be minimized.

If no valid scheme exists, output a single line with the text No solution.

sample

4
0 0
1 1
2 2
3 3

1 2
3 4