На бесконечной плоскости лежат \(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)\), соответственно.
Нумерация точек не меняется после удаления точек. Если точки удалены, то они не могут быть выбраны в последующих ходах. Обратите внимание, что необходимо двигать обе точки во время хода, нельзя оставлять их в изначальных координатах.
Какое наибольшее количество ходов можно совершить? Какие это ходы?
Если существует несколько ответов, то выведите любой из них.
Выходные данные
В первой строке выведите одно целое число \(c\) — наибольшее количество ходов, которые можно совершить.
В каждой из следующих \(c\) строк должно быть записано описание хода: два целых числа \(a\) и \(b\) (\(1 \le a, b \le n\), \(a \neq b\)) — точки, удаляемые на текущем ходу. Должен существовать способ подвинуть точки \(a\) и \(b\) согласно условию так, чтобы существовала прямая, проходящая через новые координаты \(a\), новые координаты \(b\) и \((0, 0)\). Никакая удаленная точка не может быть удалена в последующих ходах.
Если существует несколько ответов, то выведите любой из них. Можно выводить ходы и точки внутри ходов в произвольном порядке.
Примечание
Точки из первого примера и перемещения для тех из них, которые выбираются в ходах:
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|
|
2
|
4
2 1 1 1
1 1 2 1
2 1 1 2
1 2 1 2
|
1
1 2
|
|
3
|
4
182 168 60 96
78 72 45 72
69 21 144 63
148 12 105 6
|
1
2 4
|