题目描述

现在有一个格斗场，每个新会员入会时必须与一名老会员比赛，比赛双方的实力值应当尽量接近：

• 新会员会去找当前已入会会员中实力最接近自己的人比赛；
• 如果有两个人的实力值与他的差值相同，则他会选择实力较弱的那个；
• 规定 facer 为格斗场的第一个会员，实力值为 $1000000000$，id 为 $1$。

比赛时，输出比赛双方的 id，新会员的 id 写在前面。

输入

第一行一个整数 $n$，表示有 $n$ 个人陆续入会，$0 < n \le 100000$。

接下来 $n$ 行，每行两个正整数 $id$ 和 $p$，表示入会会员的 id 和实力值。

输入保证每个新会员的实力值与所有已有会员（含 facer）都不相同，且 id 互异。

输出

共 $n$ 行，每行两个整数：新会员的 id 与对手的 id，中间用空格隔开。

3
2 1
3 3
4 2

2 1
3 2
4 2