Фермер Джон организовывает бег с прыжками через барьеры для своих коров.
Имеется \(N\) барьеров, последовательно пронумерованных \(1 \ldots N\) \((2 \leq N \leq 10^5\)),
каждый из которых описывается отрезком на двумерной карте маршрута. Эти отрезки
не должны пересекаться даже в конечных точках.
Но оказалось - некоторые пересекаются. Но если убрать ровно один отрезок, тогда
пересекающихся отрезков не станет.
Определите отрезок, который ФД должен удалить, чтобы оставшиеся не пересекались.
Если таких отрезков несколько - выведите номер первого из них во вводе.
ФОРМАТ ВВОДА (файл cowjump.in):
Первая строка ввода содержит число \(N\). Каждая из последующих \(N\) строк
описывает один отрезок четырьмя целыми числами \(x_1\) \(y_1\) \(x_2\) \(y_2\),
все не отрицательные целые числа не более чем \(10^9\). Отрезок имеет
в качестве конечных точки \((x_1, y_1)\) и \((x_2, y_2)\). Все конечные точки
различаются друг от друга.
ФОРМАТ ВЫВОДА (файл cowjump.out):
Выведите наименьший номер во вводе отрезка, удаление которого
приведёт к тому, что оставшиеся отрезки не будут пересекаться.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
2 1 6 1
4 0 1 5
5 6 5 5
2 7 1 3
|
2
|