最初，我们有一个长度为 $1$ 的数组，其中仅包含数字 $0$。所有自然数按升序排列在“预留列表”中（列表中的第一个数字是 $1$）。该数组会经历 $q$ 次操作。第 $i$ 次操作是以下之一：

• Insert(p, x)：在数组中的数字 $p$ 之后，按升序插入预留列表中的前 $x$ 个数字。这些数字将从预留列表中移除。
• Remove(p, x)：移除数组中数字 $p$ 之后的接下来的 $x$ 个数字。这些数字不会被退回到预留列表中。

给你关于 $q$ 次操作的信息，要求你确定每次操作后写在数组中间的数字。如果第 $i$ 次操作后数组的长度为 $n$，你应该找到数组的第 $\lceil \frac{n}{2} \rceil$ 个元素。注意，数组的索引从 $1$ 开始。

输入格式

第一行包含一个整数 $q$ ($1 \le q \le 5 \cdot 10^5$)，表示操作的次数。

接下来的 $q$ 行，每行包含两个整数：$p_i$ ($0 \le p_i \le 2 \cdot 10^9$) 和 $k_i$ ($1 \le |k_i| \le 2 \cdot 10^9$)。

如果 $k_i = +x$，则执行操作 Insert(p_i, x)。如果 $k_i = -x$，则执行操作 Remove(p_i, x)。

保证所有操作都是合法的，且不会对数组执行不可能的操作。此外，最多有 $2 \cdot 10^9$ 个数字从预留列表移动到数组中。

输出格式

输出 $q$ 行。在第 $i$ 行中，输出执行第 $i$ 次操作后数组的中间元素。

样例

输入样例 1

10
0 3
0 2
5 -2
4 1
0 -2
5 2
7 3
3 2
10 5
12 20

输出样例 1

1
5
4
6
5
7
9
10
16
22