本题使用标准输入、标准输出，无需读写题面中提到的文件。

题目描述

在过去，农夫约翰曾思考过许多关于新型奶牛运动的创新点子，其中之一是“奶牛障碍赛（Cow Steeplechase）”，在这项运动中，成群的奶牛会绕着赛道奔跑并跨越栏杆。他过去为推广这项运动所做的努力成效不一，因此他希望在自己的农场里建造一个更大的奶牛障碍赛赛道，以便为这项运动制造更多的宣传。

农夫约翰的新赛道围绕着 $N$ 个栏杆精心规划，这些栏杆方便地编号为 $1 \ldots N$ $(2 \leq N \leq 10^5$)，每个栏杆在赛道的二维地图上用一条线段表示。这些线段之间不应以任何方式相交，甚至端点也不能相交。

不幸的是，农夫约翰在绘制赛道地图时没有留意，发现线段之间存在相交。然而，他也注意到：如果只移除其中一条线段，地图就能恢复到原本“不存在相交线段（端点也不相交）”的预期状态。

请确定一条农夫约翰可以从计划中移除的线段，使得剩余线段不再相交。如果有多条线段都满足条件，请输出输入中编号最靠前的一条。

输入格式

第一行输入包含 $N$。 接下来的 $N$ 行每行用四个整数 $x_1$ $y_1$ $x_2$ $y_2$ 描述一条线段，均为不超过 $10^9$ 的非负整数。该线段的两个端点分别为 $(x_1, y_1)$ 和 $(x_2, y_2)$。 所有端点两两不同。

输出格式

输出在输入中最早出现的那条线段的编号，使得移除该线段后其余线段互不相交。

4
2 1 6 1
4 0 1 5
5 6 5 5
2 7 1 3

2

提示

注意：由于线段端点坐标的整数范围较大，你可能需要小心整数溢出问题。 题目来源：Brian Dean

来源

USACO|2019|Silver