椰子

“坠落的椰子”是一个传统的游戏，由一群小孩儿来玩，每次一个孩子从树上把一个椰子扔到地上来，（如下图所示），每一个椰子重量都不相同，最初这些椰子都挂在一棵很高的树上，它们被固定在一根与地面平行的轴线上。

当游戏开始时，一个椰子沿着与地面垂直的方向落到地面上指定的位置，如果椰子X落到了地上（因为地平线高度为0，故椰子在地上的高度为1），它会待在那里不动，如果它落在了另一个椰子上，就会出现下面几种情况：
（1）如果椰子Y的左右两边都已有椰子（下图中用“O”表示），则椰子会停在那里不动。

 X
          X
OYO  =>  OYO

 X
-Y- =>  -XY  (X比Y重)

 X
-Y- =>  XY-  (X比Y轻)

（3）如果椰子Y只有一边有一个其它的椰子，发生的情况如下图所示：

 X
-YO => YXO  (X比Y重)

 X
-YO => XYO  (X比Y轻)

 X
OY- => OXY  (X比Y重)

 X
OY- => OYX  (X比Y轻)

注意：每当椰子X或Y滑落到一个不同的位置时，它会继续滑落直到待到一个不能再滑落的位置为止。
你的任务是输出每一个椰子最终的位置。

输入格式：
输入文件的第一行有一个正整数T，表示接下来测试数据的个数。
每一个测试数据由一个整数N（1<=N<=1000）开始，表示要掉落的椰子数量，接下来有N行，每行有两个整数Pi和Wi（1<=Pi,Wi<=1000），Pi表示第i个椰子在水平方向的坐标，Wi表示其重量，任意两个椰子的重量都不相同。

输出格式：
对于每一个测试数据，输出N行，每一行有一个坐标（Xi,Yi），表示第i个椰子最终的位置，Xi表示高度，Yi表示其在水平方向上的坐标。请在每两组测试数据结果之间输出一个空行。

样例：
coconuts.in

2
2
1 1
1 2
4
1 1
2 2
1 3
1 4

1 2
1 1

1 0
1 2
1 1
2 1