Cow Obstacle Course

Farmer John once dreamed up many novel cow sports, including a cow obstacle course in which cows race along a track and jump over barriers. In his latest plan, he has designed N obstacles (numbered 1 through N) for a new, larger course. Each obstacle is represented by a line segment on a 2D map. The original design ensured that no two segments would intersect – not even at their endpoints.

However, due to carelessness in drawing the map, some segments now intersect. Farmer John observed that by removing exactly one segment, the map would be restored to the intended state without any intersections. Your task is to determine which segment to remove. If more than one segment can be removed to achieve a non-intersecting set, output the one with the smallest index.

Note: Two segments are considered intersecting if they share any point, including endpoints.

The equations in this problem are formatted in LaTeX. For example, the number of obstacles satisfies \(2 \leq N \leq 10^5\), and the obstacle indices are \(1, 2, \ldots, N\).

inputFormat

The first line contains an integer N, the number of line segments (obstacles).

The next N lines each contain four integers x₁ y₁ x₂ y₂ representing the endpoints of a segment. It is guaranteed that, if one correct segment is removed, the remaining segments do not intersect (not even at endpoints).

outputFormat

Output one integer: the index (1-indexed) of a segment whose removal results in a set of non-intersecting segments. If multiple segments satisfy the condition, output the smallest index among them.

sample

4
0 0 4 4
0 4 4 0
5 5 6 6
7 7 8 8

1