题目描述

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$ 行，表示在 Lovro 给出第 $i$ 条信息后，对 Domagoj 问题的回答。

输入输出样例 #1

输入 #1

3
2 1
3 1
1 1

输出 #1

2
2
2

输入输出样例 #2

输入 #2

4
17 2
23 5
11 4
9 5

输出 #2

17
23
17
11

输入输出样例 #3

输入 #3

3
10 20
100 5
1000 5

输出 #3

10
10
10

说明/提示