C. Манхэттенские пары
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам даны $$$n$$$ точек $$$(x_i, y_i)$$$ на 2D плоскости, где $$$n$$$ — четное число. Выберите $$$\tfrac{n}{2}$$$ непересекающихся пар $$$(a_i, b_i)$$$, чтобы сумма манхэттенских расстояний между точками в парах была максимальна. Иными словами, максимизируйте $$$$$$\sum_{i=1}^{n/2} |x_{a_i} - x_{b_i}| + |y_{a_i} - y_{b_i}|.$$$$$$

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит одно четное целое число $$$n$$$ ($$$2 \leq n \leq 2 \cdot 10^5$$$) — количество точек.

$$$i$$$-я из следующих $$$n$$$ строк содержит два целых числа $$$x_i$$$ и $$$y_i$$$ ($$$-10^6 \le x_i, y_i \le 10^6$$$) — координаты $$$i$$$-й точки.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

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

Для каждого набора входных данных выведите $$$\tfrac{n}{2}$$$ строк, в $$$i$$$-й строке содержатся два целых числа $$$a_i$$$ и $$$b_i$$$ — индексы точек в $$$i$$$-й паре.

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

Пример
Входные данные
2
4
1 1
3 0
4 2
3 4
10
-1 -1
-1 2
-2 -2
-2 0
0 2
2 -3
-4 -4
-4 -2
0 1
-4 -2
Выходные данные
4 1
2 3
8 1
9 10
7 5
2 3
6 4
Примечание

В первом наборе входных данных оптимальным решением является выбор пар $$$(1, 4)$$$ и $$$(2, 3)$$$, что дает сумму расстояний $$$5 + 3 = 8$$$.

Во втором наборе входных данных оптимальным решением является выбор пар $$$(1, 8)$$$, $$$(9, 10)$$$, $$$(5, 7)$$$, $$$(2, 3)$$$, $$$(4, 6)$$$, что дает сумму расстояний $$$4 + 7 + 10 + 5 + 7 = 33$$$.