题目描述

Katla 不再玩名为 Compass 的集换式卡牌游戏，准备把自己的卡牌全部卖掉。每张卡有三个角度：红色角度、绿色角度、蓝色角度，每个角度都是 $0$ 到 $359$ 之间的整数；此外每张卡还有一个唯一的 ID。

Katla 希望在卖牌的过程中，让剩余牌堆尽可能“独特”。她对一张牌的独特性定义如下。

对于某一种颜色，考虑这张牌对应的角度。沿圆周两个方向，分别找到离它最近的另一张牌的同色角度，然后计算这两个最近角度之间的夹角。这个夹角就是该颜色下的独特值。

例如，若三张牌的红色角度分别为 $42,90,110$，则它们红色角度的独特值分别为 $340,68,312$。如果两张牌在某个颜色上的角度相同，那么它们互为该方向上最近的牌，该颜色的独特值为 $0$。

一张牌的总独特值为红、绿、蓝三种颜色独特值之和。

卖牌时，Katla 每次卖掉当前总独特值最小的牌；如果有多张牌总独特值相同，则先卖 ID 更大的牌。每卖掉一张牌后，剩余牌的独特值都会重新计算，然后再卖下一张。

请输出所有牌被卖出的顺序。

输入格式

第一行包含一个整数 $n$，表示卡牌数量，满足 $1\le n\le 10^5$。

接下来 $n$ 行，每行包含四个整数 $r,g,b,\mathrm{id}$，分别表示一张牌的红、绿、蓝角度以及 ID，满足：

• $0\le r,g,b<360$；
• $0\le \mathrm{id}<2^{31}$；
• 没有两张牌的 ID 相同。

输出格式

输出 $n$ 行，依次表示卡牌从最先卖出到最后卖出的 ID。

输入输出样例 #1

输入 #1

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

输出 #1

2
3
1

输入输出样例 #2

输入 #2

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

输出 #2

2017
240
120
0