Katla 最近停止了收集卡牌游戏 Compass。正如你可能记得的那样，Compass 是一款游戏，每张卡牌都有一个红色、绿色和蓝色的角度，每个角度都在 0 到 359 之间，以及一个 ID。由于她已经不再玩这个游戏，Katla 决定卖掉她所有的卡牌。然而，她希望在卖掉卡牌的同时，尽可能保持她牌组的独特性。你能帮她算出她应该按什么顺序卖掉这些卡牌吗？

图片来自维基共享资源，公有领域

为了决定一张卡牌在牌组中有多独特，她按以下方式进行计算。对于三种颜色中的每一种，她都会找到顺时针和逆时针方向上最近的其他卡牌，然后计算这两张其他卡牌之间的角度。例如，如果她有三张红色角度分别为 42、90 和 110 的卡牌，那么它们红色角度的独特性值分别为 340、68 和 312。如果两张卡牌 $A$ 和 $B$ 的角度相同，则 $B$ 被视为 $A$ 在两个方向上最近的卡牌，因此该颜色下 $A$（和 $B$）的独特性值为 0。

通过将三种颜色的独特性值相加，Katla 可以得出每张卡牌的独特性。在卖出卡牌时，Katla 会卖掉当前独特性最低（独特性值最小）的卡牌。如果两张卡牌的独特性值相同，她会先卖掉 ID 较大的那张。每卖出一张卡牌后，剩余卡牌的独特性值会更新，然后再卖出下一张卡牌。

输入格式

第一行包含一个整数 $n$，表示卡牌的数量 ($1 \le n \le 10^5$)。接下来有 $n$ 行。每行包含 4 个整数 $r, g, b, id$ ($0 \le r, g, b < 360, 0 \le id < 2^{31}$)，分别表示一张卡牌的红色、绿色、蓝色角度以及 ID。没有两张卡牌的 ID 相同。

输出格式

输出 $n$ 行，包含卡牌的 ID，按卖出的顺序排列，从第一张（最不独特）到最后一张（最独特）。

样例

输入格式 1

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

输出格式 1

2
3
1

输入格式 2

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

输出格式 2

2017
240
120
0