Domagoj's favorite school subject is P.E. Every P.E. class starts with warm-up exercises. The teacher has an interesting way of choosing the student who will lead the warm-up. The students stand in a line sorted by their height. The teacher will choose the student that is standing in the middle of the line. If two students are in the middle, he will choose the shorter one. For example: if the students have heights $135711$, the student with height $5$ will lead the warm-up exercises.

Domagoj does not remember how tall his classmates are. Luckily, next to him stands Lovro, who is very good at estimating people's heights. He gives Domagoj $n$ statements: "There are $a_i$ students entering the gym with height $v_i$". After every statement said by Lovro, Domagoj is interested in the height of the student who will lead the warm-up, if only the students who entered the gym come to P.E. class. Help him answer his questions!

Input Specification

The first line contains the integer $n$ $(1\le n\le 200000)$, the number of Lovro's statements.

The following $n$ lines contain two integers $v_i,a_i$ $(1\le v_i,a_i\le {10}^9)$, the height and the number of students in Lovro's statement.

Output Specification

In the $i^{\text{th}}$ of $n$ lines, output the answer to Domagoj's question after $i$ of Lovro's statements.

Constraints

Subtask	Points	Constraints
1	19	$n,v_i\le 1000$
2	26	$a_1=a_2=\cdots =a_n=1$
3	29	$v_1<v_2<\cdots <v_n$
4	36	No additional constraints.

Sample Input 1

3
2 1
3 1
1 1

Sample Output 1

2
2
2

Sample Input 2

4
17 2
23 5
11 4
9 5

Sample Output 2

17
23
17
11

Sample Input 3

3
10 20
100 5
1000 5

Sample Output 3

10
10
10