Problem Description

There are $n$ sticks placed on a tabletop. Find an order to move the sticks toward the edge of the table along the $x$ axis, such that the sticks do not collide (all sticks move toward the table edge at the same speed).

Input Format

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

The next $N$ lines each contain four integers $x1_i,y1_i,x2_i,y2_i$, representing the coordinates of the two endpoints of a stick.

Output Format

Output one line with $n$ integers, representing a valid order to move the sticks.

4
1 3 2 2
1 1 3 2
2 4 7 3
3 3 5 3

2 4 1 3

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

4 3 1 2

3
4 6 5 5
2 1 15 1
3 2 8 7

2 3 1

Hint

Sample 1 Explanation

As shown in the figure, another valid moving order is 2 1 4 3.

Constraints

For $40\%$ of the testdata, $1\le N\le 10$.

For $60\%$ of the testdata, $1\le N\le 300$.

For $100\%$ of the testdata, $1\le N\le 5000$, $0\le x1,y1,x2,y2\le 10^4$.

Notes

The scoring of this problem follows the original problem, with a full score of 100.

This problem is translated from T3 ARTUR of COCI 2015-2016 CONTEST #2.

Translated by ChatGPT 5