Description

少林寺以其功夫僧人而闻名。每年都有很多年轻人去少林寺，试图成为一名僧人。当一个年轻人通过所有考试并被宣布为少林的新僧人时，将有一场战斗作为欢迎会的一部分。每个僧人都有一个独特的身份和战斗等级，这些都是整数。新僧人必须与一位战斗等级最接近他的战斗等级的老僧人战斗。若有两个老僧人满足这个条件，则新僧人将选择战斗等级低于他的僧人。大师是少林的第$1$个僧人，他的编号是$1$号，他的战斗等级是$10$万。他刚刚失去了战斗记录，但还记得早些时候加入少林的人。请帮他恢复战斗记录。

Input

输入几个测试用例。每个测试用例的第1行都是一个整数$n（0<n ≤10^5 ）$，表示在大师之后加入少林的僧人数量；接下来的$n$行，每行都有两个整数$k$ 和$g （0≤k , g ≤5×10^6 ）$，表示僧人的身份编号和他的战斗等级。僧人按照加入的时间升序列出。输入以$n =0$结束。

Output

对每个测试用例，都按发生时间的升序输出所有战斗。对每场比赛都输出一行，首先输出新僧人的编号，然后输出老僧人的编号。

Samples

3
2 1
3 3
4 2
0

2 1
3 2
4 2