Consider a multiset $S$ that is initially empty. We will perform $n$ operations sequentially.

In each operation, we add or remove a specific integer $x$ from the multiset $S$. It is guaranteed that at any time, the sum of all elements in the multiset $S$ will not exceed $5 \times 10^5$.

Your task is to calculate and output the number of distinct integers that can be formed by the sum of a subset of elements in $S$ (where each element can either be included or not included in the sum) after each operation.

Please note that the effect of each operation on $S$ is permanent.

Input

The first line contains an integer $n$ ($1 \le n \le 5 \times 10^3$), representing the number of operations.

The next $n$ lines each contain two integers $op$ and $x$ ($op \in \{1, 2\}$, $1 \le x \le 5 \times 10^5$), representing the operation type and the element:

• If $op = 1$, insert $x$ into $S$. It is guaranteed that $x$ is not already in $S$.
• If $op = 2$, remove $x$ from $S$. It is guaranteed that $x$ is already in $S$.

It is guaranteed that after each operation, the sum of all elements in $S$ is less than or equal to $5 \times 10^5$.

Output

There are $n$ lines, each containing one integer, where the $i$-th line outputs the number of distinct integers that can be formed by the sum of a subset of $S$ after the $i$-th operation.

Examples

Input 1

4
1 100
1 999
1 10
2 100

Output 1

1
3
7
3

Input 2

7
1 1
1 2
1 1
1 4
1 5
2 1
2 4

Output 2

1
3
4
8
13
12
7