Farmer John为新场地精心设计了N个障碍栏架,编号为1…N(2≤N≤10^5),每一个栏架都可以用这一场地的二维地图中的一条线段来表示。这些线段本应两两不相交,包括端点位置。
不幸的是,Farmer John在绘制场地地图的时候不够仔细,现在发现线段之间出现了交点。然而,他同时注意到只要移除一条线段,这张地图就可以恢复到预期没有相交线段的状态(包括端点位置)。
请求出Farmer John为了恢复没有线段相交这一属性所需要从他的计划中删去的一条线段。如果有多条线段移除后均可满足条件,请输出在输入中出现最早的线段的序号。
4
2 1 6 1
4 0 1 5
5 6 5 5
2 7 1 3
2