Problem Description

Domagoj's favorite class is Physical Education. Every PE class starts with warm-up exercises. The PE teacher has an interesting way to choose the student who will lead the warm-up. The students stand in a line sorted by height from shortest to tallest, and the teacher chooses the student in the middle of the line. If there are two students in the middle, he chooses the shorter one. For example, if the students' heights are $1, 3, 5, 7, 11$, then the student with height $5$ will lead the warm-up.

Domagoj cannot remember his classmates' heights. Luckily, Lovro, who stands next to him, is very good at estimating other people's heights. He gives Domagoj $n$ pieces of information: "There are $a_i$ students of height $v_i$ who entered the gym." After Lovro finishes each piece of information, Domagoj is interested in the height of the student who will lead the warm-up. Assume that all students who enter the gym are attending the PE class. Please help him answer his questions.

Input Format

The first line contains an integer $n\ (1\le n\le 200\ 000)$, the number of pieces of information from Lovro.

The next $n$ lines each contain two integers $v_i, a_i\ (1\le v_i,a_i\le 10^9)$, representing the height and the number of students in Lovro's information.

Output Format

Output $n$ lines. The $i$-th line should be the answer to Domagoj's question after Lovro gives the $i$-th piece of information.

3
2 1
3 1
1 1

2
2
2

4
17 2
23 5
11 4
9 5

17
23
17
11

3
10 20
100 5
1000 5

10
10
10

Hint

Translated by ChatGPT 5