Sports Class Warm-up Leader Selection

In every physical education class, the session begins with a warm‐up exercise. In an interesting twist, the teacher selects the student who will lead the warm‐up based on their height. All students line up in non-decreasing order by height and the teacher chooses the student exactly in the middle. In case there are two middle students, the teacher selects the shorter one (i.e. the left one if the list is 0-indexed).

Domagoj, who doesn’t remember his classmates' heights, receives n pieces of information from his friend Lovro. Each piece states: "There are a_i students with height v_i entering the gym." After each message, Domagoj is curious about the height of the student who would be chosen to lead the warm‐up.

Your task is to help Domagoj determine the leader’s height after each piece of information assuming that all the students who entered the gym are attending the class.

Note: The median here is defined as the element at index \( \lfloor (m-1)/2 \rfloor\) in the sorted order (0-indexed) where \(m\) is the total number of students so far. Equivalently, if there are an even number of students, choose the lower median (i.e. the \(m/2\)th smallest element in 1-indexing).

Input Format: The first line contains a single integer n. Then n lines follow, each containing two space-separated integers a_i and v_i.

Output Format: For each of the n pieces of information, output a single line containing the selected student's height after processing that information.

inputFormat

The input begins with a line containing a single integer n (the number of pieces of information).

Each of the following n lines contains two integers a_i and v_i, indicating that a_i students with height v_i enter the gym.

outputFormat

Output n lines. The i-th line should contain a single integer representing the height of the student chosen to lead the warm-up after processing the first i pieces of information. Remember, if the number of students is even, the lower of the two middle values is chosen.

sample

1
1 5

5