Domagoj 最喜欢的学校科目是体育课。每节体育课都以热身运动开始。老师有一种有趣的方式来挑选带领热身运动的学生。学生们按身高排成一列。老师会选择站在队伍中间的学生。如果队伍中间有两名学生，他会选择较矮的那一位。例如：如果学生的身高为 1 3 5 7 11，那么身高为 5 的学生将带领热身运动。
Domagoj 不记得他的同学们有多高了。幸运的是，站在他旁边的 Lovro 非常擅长估计人们的身高。他给了 Domagoj $n$ 条陈述：“有 $a_i$ 名身高为 $v_i$ 的学生进入了体育馆”。在 Lovro 说出每一条陈述后，Domagoj 都想知道，如果只有目前进入体育馆的学生参加体育课，谁将带领热身运动（即该学生的身高是多少）。请帮他回答这些问题！
输入格式
第一行包含一个整数 $n$ ($1 \le n \le 200,000$)，表示 Lovro 的陈述数量。
接下来的 $n$ 行，每行包含两个整数 $v_i, a_i$ ($1 \le v_i, a_i \le 10^9$)，分别表示 Lovro 陈述中学生的身高和人数。
输出格式
在 $n$ 行中，第 $i$ 行输出在 Lovro 的前 $i$ 条陈述之后，Domagoj 问题的答案。
子任务
| 子任务 | 分值 | 约束条件 |
|---|---|---|
| 1 | 19 | $n, v_i \le 1\,000$ |
| 2 | 26 | $a_1 = a_2 = \dots = a_n = 1$ |
| 3 | 29 | $v_1 < v_2 < \dots < v_n$ |
| 4 | 36 | 无附加约束 |
样例
输入 1
3 2 1 3 1 1 1
输出 1
2 2 2
输入 2
4 17 2 23 5 11 4 9 5
输出 2
17 23 17 11
输入 3
3 10 20 100 5 1000 5
输出 3
10 10 10
Figure 1. 学生按身高排成一列