题目描述

为了迎接 2022 年冬奥会，让大家了解各种冬奥会项目，小 A 开了一家滑冰场，滑冰场实行严格的会员制，但是新加入的会员不需要缴纳会费，而只要同一名之前已经加入的会员进行一场表演赛，证明自己的实力。我们假设滑冰的技能可以用一个正整数表示，称为技能值（用小于等于 $1000000000$ 的非负整数表示）。每个入会的会员都有一个唯一的会员 $id$ 号，也是一个正整数。为了使得比赛更好看，每一个新会员都会选择与他技能值最为接近的人比赛，即比赛双方的技能值之差的绝对值越小越好，如果有两个人的技能值与他差别相同，则他会选择比他弱（技能值小的）的那个人比赛。

不幸的是，小 A 不小心把比赛记录弄丢了，但好在小 A 有所有会员入会时的注册记录， 现在请你帮小 A 恢复比赛记录表，按照时间顺序依次输出每场比赛双方的会员 $id$ 号。

输入格式

第一行一个数 $n(0 < n ≤100000)$，表示滑冰场新来的会员数（不包括小 A 本人）。

以后 $n$ 行每行两个数，按照入会的时间给出会员 $id$ 号和技能值。一开始，小 A 也算是会员， $id$ 为 $1$，技能值 $1000000000$。输入保证两人的技能值不同。

输出格式

$n$ 行，每行两个数，为每场比赛双方的会员 $id$ 号，新入会的选手的会员 $id$ 号写在前面。

样例

4
2 1
3 3
4 2
5 4

2 1
3 2
4 2
5 3

数据范围

• 对于 $30\%$ 的测试数据满足：$1≤n≤10^3$。
• 对于 $60\%$ 的测试数据满足：$1≤n≤10^4$。
• 对于 $100\%$ 的测试数据满足：$1≤n≤10^5$。