Problem C
Compass Card Sales

Picture via Wikimedia Commons, public domain

To decide how unique a card is in the deck, she proceeds as follows. For each of the three colors she finds the closest other card in both directions, and then computes the angle between these two other cards. For instance if she has three cards with red angles $42$, $90$ and $110$, then the uniqueness values of their red angles are $340$, $68$, and $312$, respectively. If two cards $A$ and $B$ have the same angle, $B$ is considered the closest to $A$ in both directions so that the uniqueness value of $A$ (and $B$) for that color is $0$.

By summing the uniqueness values over the three colours, Katla finds how unique each card is. When selling a card, Katla sells the currently least unique card (smallest uniqueness value). If two cards have the same uniqueness value, she will sell the one with the higher ID first. After each card is sold, the uniqueness values of the remaining cards are updated before selling the next card.

Input

The first line of input contains an integer $n$, the number of cards ($1 \le n \le 10^5$). Then follows $n$ lines. Each of these $n$ lines contains $4$ integers $r, g, b, \text {id}$ ($0 \le r, g, b < 360$, $0 \le \text {id} < 2^{31}$), giving the red, green and blue angles as well as the ID of a card. No two cards have the same ID.

Output

Output $n$ lines, containing the IDs of the cards in the order they are to be sold, from first (least unique) to last (most unique).

3
42 1 1 1
90 1 1 2
110 1 1 3

2
3
1

4
0 0 0 0
120 120 120 120
240 240 240 240
0 120 240 2017

2017
240
120
0