Глеб и Евлампий играют в шахматы. Они люди предельно простые, поэтому не обращают внимание на правила, по которым должны ходить фигуры — ребята считают, что каждая фигура может сходить с любой клетки на любую другую. Чтобы упростить игру еще сильнее, Глеб и Евлампий используют доску $$$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$$$ | — | Каждый тест |
42 5 4 57 1 4 54 5 6 58 8 1 1
3
В примере ситуация, описанная в первых трех строках, невозможна. Глеб не мог сделать ход с позиции $$$(4,5)$$$, поскольку его фигуру, которую он поставил на эту позицию, съели на предыдущем ходу.
