Корова з перешкодами 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)$. Усі точки відрізків відрізняються одна від одної.

Вихідні дані

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

Приклади

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