Корова с препятствиями II

В прошлом фермер Джон обдумывал ряд новаторских идей для новых видов спорта с коровами, в том числе "Бег с препятствиями для коров", когда стада могут бегать по трассе и преодолевать препятствия. Его прошлые усилия по повышению интереса к этому виду спорта привели к неоднозначным результатам, поэтому ФД надеется построить на своей ферме еще большую трассу для бега с препятствиями для коров, чтобы попытаться привлечь больше внимания к этому виду спорта.

Новый маршрут ФД тщательно спланирован вокруг $n$ препятствий, пронумерованых от $1$ до $n$, каждое из которых описано как отрезок на двухмерной карте трассы. Эти отрезки не должны никоим образом пересекать друг друга, даже в конечных точках.

К сожалению, ФД не уделял должного внимания при создании карты и впоследствии заметил, что между отрезками имеются пересечения. Однако он также заметил, что если убрать только один отрезок, то карта будет восстановлена до предполагаемого состояния (без пересекающихся сегментов, даже в конечных точках).

Определите отрезок, который ФД может удалить из своего плана, чтобы восстановить свойство, при котором отрезки не пересекаются. Если таким образом можно удалить несколько отрезков, выведите индекс наименьшего.

Входные данные

Первая строка содержит число $n(2\le n\le 10^5)$. Каждая из оставшихся $n$ строк описывает один отрезок с четырьмя целыми числами $x_1{y}_1{x}_2{y}_2$, все неотрицательные целые числа не более $10^9$. Концы отрезков имеют координаты $(x_1,y_1)$ и $(x_2,y_2)$. Все точки отрезков отличаются друг от друга.

Выходные данные

Выведите наименьший индекс отрезка, после удаления которого оставшиеся отрезки не пересекаются.

Примеры

Будьте осторожны с целочисленным переполнением из-за размера целых чисел, представляющих координаты точек отрезков.