Statement is not available in English language
G. Простые шахматы
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Глеб и Евлампий играют в шахматы. Они люди предельно простые, поэтому не обращают внимание на правила, по которым должны ходить фигуры — ребята считают, что каждая фигура может сходить с любой клетки на любую другую. Чтобы упростить игру еще сильнее, Глеб и Евлампий используют доску $$$8 \times 8$$$, на которой горизонтали пронумерованы числами от $$$1$$$ до $$$8$$$ и вертикали — тоже пронумерованы числами от $$$1$$$ до $$$8$$$.

Игроки делают ходы по очереди. Глеб играет белыми фигурами и ходит первым. Его фигуры изначально занимают все клетки горизонталей $$$1$$$ и $$$2$$$ (итого, $$$16$$$ фигур). Евлампий играет черными фигурами, изначально они расположены в горизонталях $$$7$$$ и $$$8$$$ (также $$$16$$$ фигур). Во время своего хода игрок должен взять одну из своих фигур (которая еще не была «съедена») и поставить ее на другую клетку, которая не занята фигурой этого же цвета. Можно ставить фигуру на клетку, которая занята другим игроком — в этом случае фигура противника будет «съедена» и убрана с доски.

Глеб и Евлампий сделали несколько ходов и записали их на бумажке. Каждый ход описывался $$$4$$$ числами — начальным положением фигуры, которой был сделан ход, и ее конечным положением. Ходы были записаны в хронологическом порядке. Однако, ребята могли допустить ошибки при записи ходов. Найдите наименьший номер строки, на которой можно утверждать, что записи сделаны некорректно.

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

В первой строке задано натуральное число $$$n$$$ — количество ходов, $$$1 \leq n \leq 100$$$.

В каждой из следующих $$$n$$$ строк задано по $$$4$$$ натуральных числа — $$$x_1, y_1, x_2, y_2$$$, где $$$x_1, y_1$$$ — координаты, где стояла фигура, которая делает ход ($$$x_1$$$ — номер горизонтали, $$$y_1$$$ — номер вертикали), а $$$x_2, y_2$$$ — координаты, куда эта фигура сделала ход.

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

Выведите одно число — минимальный номер $$$i$$$, такой что среди записей ходов от $$$1$$$ до $$$i$$$ включительно точно есть ошибка. Если данный набор ходов не содержит ошибки, выведите $$$-1$$$.

Система оценки
ГруппаБаллыДоп. ограниченияКомментарий
$$$0$$$$$$0$$$—Тесты из условия
$$$1$$$$$$100$$$—Каждый тест
Пример
Входные данные
4
2 5 4 5
7 1 4 5
4 5 6 5
8 8 1 1
Выходные данные
3
Примечание

В примере ситуация, описанная в первых трех строках, невозможна. Глеб не мог сделать ход с позиции $$$(4,5)$$$, поскольку его фигуру, которую он поставил на эту позицию, съели на предыдущем ходу.