暂无测试数据。

蒜头君新开了一家热血格斗场。格斗场实行会员制，但是新来的会员不需要交入会费，而只要同一名老会员打一场表演赛，证明自己的实力。

我们假设格斗的实力可以用一个正整数表示，成为实力值。另外，每个人都有一个唯一的 $\text{id}$，也是一个正整数。为了使得比赛更好看，每一个新队员都会选择与他实力最为接近的人比赛，即比赛双方的实力值之差的绝对值越小越好，如果有两个人的实力值与他差别相同，则他会选择比他弱的那个。

不幸的是，蒜头君一不小心把比赛记录弄丢了，但是他还保留着会员的注册记录。现在请你帮蒜头君恢复比赛纪录，按照时间顺序依次输出每场比赛双方的 $\text{id}$。

输入格式

第一行一个数 $n(0 < n \le 100000)$，表示格斗场新来的会员数（不包括蒜头君）。

以后 $n$ 行每一行两个数，按照入会的时间给出会员的 $\text{id}(2 \le \text{id} \le 10^6)$ 和实力值($\le 10^9$)。一开始，蒜头君就算是会员，$\text{id}$ 为 $1$，实力值 $1000000000$。

输入保证两人的实力值不同。

输出格式

$N$ 行，每行两个数，为每场比赛双方的 $\text{id}$，新手的 $\text{id}$ 写在前面。

3
2 1
3 3
4 2

2 1
3 2
4 2