Moderation in all things

문제

Initially, we have an array of length $11$ containing only the number $00$. All natural numbers are listed in ascending order in the “reservation list” (the first number in the list is $11$). The array undergoes $qq$ operations. The $ii$^th operation, is one of the following:

• Insert(p, x): Insert the first $xx$ numbers from the reservation list after the number $pp$ in the array, in ascending order. These numbers are removed from the reservation list.
• Remove(p, x): Remove the next $xx$ numbers after number $pp$ in the array. These numbers are not returned to the reservation list.

You are given information about $qq$ operations, and you are asked to determine the number written in the middle of the array after each operation. If the length of the array after the $ii$^th operation is $nn$, you should find the $\lceil \frac{n}{2}\rceil \backslash lceil\; \backslash frac\{n\}\; \{2\}\; \backslash rceil$^th element of the array. Note that the indexing of the array starts from $11$.

입력

The first line contains an integer $qq$ ($1\le q\le 5\cdot {10}^{5}1\; \backslash le\; q\; \backslash le\; 5\; \backslash cdot\; 10^5$), which represents the number of operations. Each of the next $qq$ lines contains two integers: $p_{i}p\_i$ ($1\le p_i\le 2\cdot {10}^{9}1\; \backslash le\; p\_i\; \backslash le\; 2\; \backslash cdot\; 10^9$), and $k_{i}k\_i$ ($1\le \mathrm{\mid }{k}_i\mathrm{\mid }\le 2\cdot {10}^{9}1\; \backslash le\; |k\_i\; |\; \backslash le\; 2\; \backslash cdot\; 10^9$).

If $k_i=+xk\_i\; =\; +x$, operation Insert(pi, x) is executed. If $k_i=-xk\_i\; =\; -x$, operation Remove(pi, x) is executed. It is guaranteed that all operations are valid, and no impossible operation is performed on the array. Additionally, at most $2\cdot {10}^{9}2\; \backslash cdot\; 10^9$ numbers are moved from the reservation list into the array.

출력

Output $qq$ lines. In the $ii$^th line, print the middle element of the array after performing the $ii$^th operation.