Problem G
Artur

You have most definitely heard the legend of King Arthur and the Knights of the Round Table. Almost all versions of this story proudly point out that the roundness of the Round Table is closely related to Arthur’s belief of equality among the Knights. That is a lie! In fact, Arthur’s choice of table is conditioned by his childhood traumas.

In fact, Arthur was forced to clean up quadratic tables from a young age after a tournament in pick-up sticks¹ had been played on them. After the tournament, typically there would be a bunch of sticks on the table that do not touch each other. In the spirit of the game, the organizers issued strict regulations for the table cleaners. More precisely, the sticks on the table need to be removed one by one in a way that the cleaners pull them in the shortest way towards the edge of the table closest to where they are currently sitting. They also mustn’t rotate or touch the other sticks while doing this (not even in the edge points).

In this task, we will represent the table in the coordinate system with a square that has opposite points in the coordinates $(0,0)$ and $(10\, 000, 10\, 000)$, whereas the sticks will be represented with straight line segments that lie within that square. We will assume that Arthur is sitting at the edge of the table lying on the $x$-axis. Then the movement of the stick comes down to translating the line segment along the shortest path towards the $x$-axis until the stick falls off the table (as shown in the image). It is your task to help Arthur determine the order of stick movements that meets the requirements from the previous paragraph.

Input

The first line of input contains the integer $N$ ($1 \leq N \leq 5\, 000$), the number of sticks on the table. Each of the following $N$ lines contains four integers $x_1$, $y_1$, $x_2$, $y_2$ ($0 \leq x_1, y_1, x_2, y_2 \leq 10\, 000$) that denote the edge points of a stick.

Output

The first and only line of output must contain space-separated stick labels in the order which they need to be taken off the table. A stick’s label corresponds to its position in the input sequence.

If there are multiple possible solutions, output any of them.

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