题目描述

给定平面上的 $n$ 个点，$n$ 为偶数。你需要把所有点分成 $\frac n2$ 对，使得所有配对的曼哈顿距离之和最大。

点 $i$ 和点 $j$ 的曼哈顿距离为 $|x_i-x_j|+|y_i-y_j|$。

请输出任意一种达到最大值的配对方案。

输入格式

第一行一个整数 $t$，表示测试组数。

每组数据第一行一个偶数 $n$，表示点数。

接下来 $n$ 行，第 $i$ 行两个整数 $x_i,y_i$，表示第 $i$ 个点的坐标。

输出格式

对每组数据输出 $\frac n2$ 行，每行两个整数 $a_i,b_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)$，距离和为 $33$。

数据范围

$1\le t\le10^4$，$2\le n\le2\times10^5$，$n$ 为偶数，$-10^6\le x_i,y_i\le10^6$。

所有测试组的 $n$ 之和不超过 $2\times10^5$。