椰子

成绩 0 开启时间 2013年02月21日 星期四 18:02
折扣 0.8 折扣时间 2013年02月28日 星期四 18:02
允许迟交 关闭时间 2013年02月28日 星期四 18:02
输入文件 coconuts.in 输出文件 coconuts.out

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

当游戏开始时,一个椰子沿着与地面垂直的方向落到地面上指定的位置,如果椰子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,表示接下来测试数据的个数。
每一个测试数据由一个整数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
coconuts.out
1 2
1 1

1 0
1 2
1 1
2 1