题目描述

JZYZ的校长听说孩子们学习压力都很大，于是校长集体组织去夏威夷旅游（明显不现实←_←），有些不懂事的家伙喜欢爬到椰子树上玩，每次一个孩子从树上把一个椰子扔到地上来，（如下图所示），每一个椰子重量都不相同，最初这些椰子都挂在一棵很高的树上，它们被固定在一根与地面平行的轴线上。

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

  X
　　　　   X
 OYO =>  OYO

（2）如果椰子Y的两边都没有其它的椰子，并且椰子X比椰子Y重，那么椰子X将取代椰子Y的位置，同时椰子Y会滑落到其右侧的位置；但是如果椰子X比椰子Y轻，那么椰子X将直接滑落到Y的左侧。（下图中用“-”表示空位）

  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（T<=30），表示接下来测试数据的个数。 每一个测试数据由一个整数N（1<=N<=1000）开始，表示要掉落的椰子数量，接下来有N行，每行有两个整数Pi和Wi（1<=Pi,Wi<=1000），Pi表示第i个椰子在水平方向的坐标，Wi表示其重量，任意两个椰子的重量都不相同。

输出格式

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

样例数据

input

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

output

1 2
1 1

1 0
1 2
1 1
2 1

注释

纯模拟

数据规模与约定

保证$T \leq 30、 1 \leq N \leq 1000、 1 \leq Pi,Wi \leq 1000$

时间限制：$1 \text {s}$

空间限制：$256 \text {MB}$