测试数据来自 system/2960

作业已超过截止时间，您无法递交本题目。

时间限制：1秒　　内存限制：256M

---

【题目描述】

　　比武大会要求每一名新来的武士都要先与一位老武士进行一场比武，以确定自己的实力地位。

　　每名武士都有一个实力值和一个唯一的编号，他们都是正整数。新武士比武时会选择与他实力最为接近的老武士（实力值之差的绝对值越小越好），如果有多老名武士的实力值与他接近程度相同，则他会选择编号最小的那位。

　　现在请你编程，根据输入的新武士顺序，依次输出他们比武对象的编号。

【输入格式】

　　第一行是整 \(n\)，表示新武士的数量，最初只有一个大会盟主，他不包含在新武士中。
　　接下来 \(n\) 行每一行两个正整数，按照顺序给出了每个名新武士的编号和实力值。注意，盟主的编号为1，实力值10^9。

【输出格式】

　　包含 \(n\) 行，每行一个数，为每次比武时老武士的编号。

【输入输出样例】

　Input

4
12 30
15 10
13 20
14 15 

　Output

1
12
12
13

【数据限制】

　　对于 \(50\%\) 的数据：\(0 < n ≤10000\)。
　　对于 \(100\%\) 的数据：\(0 < n ≤100000\)，武士的编号和实力值均是小于 \(2^{31}\) 的正整数。

【来源】

　　Mr.he