E. Сдвиг на один
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

На бесконечной плоскости лежат $$$n$$$ точек. Координаты $$$i$$$-й точки $$$(x_i, y_i)$$$ такие, что $$$x_i > 0$$$ и $$$y_i > 0$$$. Координаты необязательно целые.

За один ход осуществляются следующие операции:

  • выбрать две точки $$$a$$$ и $$$b$$$ ($$$a \neq b$$$);
  • подвинуть точку $$$a$$$ из $$$(x_a, y_a)$$$ либо в $$$(x_a + 1, y_a)$$$, либо в $$$(x_a, y_a + 1)$$$;
  • подвинуть точку $$$b$$$ из $$$(x_b, y_b)$$$ либо в $$$(x_b + 1, y_b)$$$, либо в $$$(x_b, y_b + 1)$$$;
  • удалить точки $$$a$$$ и $$$b$$$.

Ход можно совершить только в том случае, если существует прямая, проходящая через новые координаты $$$a$$$, новые координаты $$$b$$$ и $$$(0, 0)$$$.

Иначе ход совершить нельзя, и точки остаются на своих начальных координатах $$$(x_a, y_a)$$$ и $$$(x_b, y_b)$$$, соответственно.

Нумерация точек не меняется после удаления точек. Если точки удалены, то они не могут быть выбраны в последующих ходах. Обратите внимание, что необходимо двигать обе точки во время хода, нельзя оставлять их в изначальных координатах.

Какое наибольшее количество ходов можно совершить? Какие это ходы?

Если существует несколько ответов, то выведите любой из них.

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

В первой строке записано одно целое $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — количество точек.

В $$$i$$$-й из следующих $$$n$$$ строк записаны четыре целых числа $$$a_i, b_i, c_i, d_i$$$ ($$$1 \le a_i, b_i, c_i, d_i \le 10^9$$$). Координаты $$$i$$$-й точки — $$$x_i = \frac{a_i}{b_i}$$$ и $$$y_i = \frac{c_i}{d_i}$$$.

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

В первой строке выведите одно целое число $$$c$$$ — наибольшее количество ходов, которые можно совершить.

В каждой из следующих $$$c$$$ строк должно быть записано описание хода: два целых числа $$$a$$$ и $$$b$$$ ($$$1 \le a, b \le n$$$, $$$a \neq b$$$) — точки, удаляемые на текущем ходу. Должен существовать способ подвинуть точки $$$a$$$ и $$$b$$$ согласно условию так, чтобы существовала прямая, проходящая через новые координаты $$$a$$$, новые координаты $$$b$$$ и $$$(0, 0)$$$. Никакая удаленная точка не может быть удалена в последующих ходах.

Если существует несколько ответов, то выведите любой из них. Можно выводить ходы и точки внутри ходов в произвольном порядке.

Примеры
Входные данные
7
4 1 5 1
1 1 1 1
3 3 3 3
1 1 4 1
6 1 1 1
5 1 4 1
6 1 1 1
Выходные данные
3
1 6
2 4
5 7
Входные данные
4
2 1 1 1
1 1 2 1
2 1 1 2
1 2 1 2
Выходные данные
1
1 2
Входные данные
4
182 168 60 96
78 72 45 72
69 21 144 63
148 12 105 6
Выходные данные
1
2 4
Примечание

Точки из первого примера и перемещения для тех из них, которые выбираются в ходах: