Compass Card Sales

Katla has stopped playing the collectible card game Compass. A Compass card has a red angle, a green angle and a blue angle, each an integer from 0 to 359, and it also has an ID. Now that she has quit, Katla wants to sell all of her cards, and she wants the deck still in her hands to stay as unique as possible while she sells them. Work out the order in which she should sell the cards.

Katla measures how unique a card is as follows. For each of the three colors she finds the closest other card in both directions around the circle, then measures the angle between those two other cards. For example, if three cards with red angles 42, 90 and 110 are left, the uniqueness values of their red angles are 340, 68 and 312. If two cards A and B have the same angle, then B is the closest card to A in both directions, so the uniqueness value of A (and of B) for that color is 0.

Stated exactly: fix one color and let $a$ be the angle of a remaining card A. Among the angles $x$ of the remaining cards other than A, let $p$ be one that minimizes $(a - x) \bmod 360$ and let $q$ be one that minimizes $(x - a) \bmod 360$. The uniqueness value of A for that color is $(q - p) \bmod 360$.

The uniqueness of a card is the sum of its uniqueness values over the three colors. Katla sells the remaining card with the smallest uniqueness. If several cards have the same uniqueness, she sells the one with the larger ID first. After each card is sold, the uniqueness values of the remaining cards are recomputed before the next card is sold. When only one card is left there is no other card, so that card is sold last.

The first line contains the number of cards $n$ ($1 \le n \le 10^5$).

Each of the next $n$ lines describes one card with the red angle $r$, the green angle $g$, the blue angle $b$ and the $\mathrm{id}$ of the card, separated by spaces ($0 \le r, g, b < 360$, $0 \le \mathrm{id} < 2^{31}$). No two cards have the same ID.

Print $n$ lines with the IDs of the cards in the order they are sold, one ID per line. The first line holds the ID of the card sold first, the least unique one, and the last line holds the ID of the card sold last.