컴퍼스 카드 판매

카틀라는 수집형 카드 게임 컴퍼스를 그만두었다. 컴퍼스의 카드에는 빨강, 초록, 파랑 각도가 하나씩 있고 각 각도는 0 이상 359 이하의 정수이며, 카드마다 고유한 ID가 붙어 있다. 게임을 접은 카틀라는 카드를 전부 팔기로 했다. 대신 파는 동안 손에 남은 덱은 최대한 독특하게 유지하고 싶다. 카드를 어떤 순서로 팔아야 하는지 구하자.

카드가 얼마나 독특한지는 이렇게 정한다. 세 색깔 각각에 대해 원 위에서 양쪽 방향으로 가장 가까운 다른 카드를 찾고, 그 두 카드 사이의 각도를 잰다. 예를 들어 빨강 각도가 42, 90, 110인 카드 세 장이 남아 있으면 빨강 독특함 값은 차례대로 340, 68, 312이다. 두 카드 A와 B의 각도가 같으면 B가 A의 양쪽 방향 모두에서 가장 가까운 카드가 되고, 그 색깔에서 A와 B의 독특함 값은 0이다.

정확히 쓰면 이렇다. 한 색깔에서 남은 카드 A의 각도를 $a$라 하자. A가 아닌 남은 카드의 각도 $x$ 중 $(a - x) \bmod 360$을 최소로 만드는 각도를 $p$, $(x - a) \bmod 360$을 최소로 만드는 각도를 $q$라 하면, 그 색깔에서 A의 독특함 값은 $(q - p) \bmod 360$이다.

세 색깔의 독특함 값을 모두 더한 값이 그 카드의 독특함이다. 카틀라는 남은 카드 중 독특함이 가장 작은 카드를 판다. 독특함이 같은 카드가 둘 이상이면 ID가 더 큰 카드를 먼저 판다. 카드를 한 장 팔 때마다 남은 카드의 독특함 값을 다시 계산한 뒤 다음 카드를 판다. 카드가 한 장만 남으면 다른 카드가 없으므로 그 카드를 마지막에 판다.

첫째 줄에 카드의 수 $n$이 주어진다 ($1 \le n \le 10^5$).

다음 $n$개 줄에 카드 정보가 한 줄에 하나씩 주어진다. 각 줄에는 빨강 각도 $r$, 초록 각도 $g$, 파랑 각도 $b$, 카드의 $\mathrm{id}$가 공백으로 구분되어 주어진다 ($0 \le r, g, b < 360$, $0 \le \mathrm{id} < 2^{31}$). ID가 같은 카드는 없다.

$n$개 줄에 걸쳐 카드를 파는 순서대로 ID를 한 줄에 하나씩 출력한다. 첫째 줄에는 가장 먼저 파는 카드, 곧 독특함이 가장 작은 카드의 ID를 출력하고, 마지막 줄에는 가장 나중에 파는 카드의 ID를 출력한다.