### 问题描述

小蓝最喜欢的学科是体育课。每节体育课都会以热身操开始。为了使热身操更有趣，也为了让学生们更加投入，体育老师会要求学生们按照身高顺序站成一排，并从中选出站在队伍中间的学生作为领队带头热身。如果有两个学生站在中间，他会选择较矮的那个。例如：

• 如果学生们的身高为 $1$、$3$、$5$、$7$、$11$，则身高为 $5$ 的学生将被选中带领热身操。
• 如果学生们的身高为 $1$、$3$、$7$、$11$，则身高为 $3$ 的学生将被选中带领热身操。

小蓝想要更好地参与体育课，对此，他希望自己能准确得知热身操领队学生的身高情况。

小蓝的朋友小桥很擅长估算人们的身高，他会给小蓝 $n$​ 条信息，每条信息的内容形式为：“有 $a_i$​ 个身高为 $v_i$​ 的学生进入了体育馆”。每当小桥说完一条信息后，小蓝都想知道，如果当前进入体育馆的学生都是来上体育课的，那么带领热身操的学生的身高会是多少。

请你帮助小蓝解答问题。

输入格式

第一行包含一个整数 $n$（$1 \leq n \leq 2\times 10^5$），表示小桥给出的信息条数。

接下来的 $n$ 行，每行包含两个整数 $v_i$ 和 $a_i$（$1 \leq v_i,a_i \leq 10^9$），其含义如题所述。

输出格式

输出 $n$ 行，每行一个整数。第 $i$ 行输出对应小桥给出第 $i$ 条信息后：在当前进入体育馆的学生都是来上体育课的情况下，带领热身操的学生的身高。

样例输入

3
2 1
3 1
1 1

样例输出

2
2
2