No submission language available for this problem.

Description

Input

The first line contains an integer $q$ ($1 \leq q \leq 2 \cdot 10^5$) — the number of queries.

The following $q$ lines describe the queries.

An addition query of integer $x$ is given in the format + $x$ ($1 \leq x \leq 10^{18}$). It is guaranteed that $x$ was not contained in the set.

A search query of $k\text{-mex}$ is given in the format ? $k$ ($1 \leq k \leq 10^{18}$).

It is guaranteed that there will be at least one query of type ?.

Output

For each query of type ? output a single integer — the $k\text{-mex}$ of the set.

15
+ 1
+ 2
? 1
+ 4
? 2
+ 6
? 3
+ 7
+ 8
? 1
? 2
+ 5
? 1
+ 1000000000000000000
? 1000000000000000000

3
6
3
3
10
3
2000000000000000000

6
+ 100
? 100
+ 200
? 100
+ 50
? 50

200
300
150

Note

In the first example:

After the first and second queries, the set will contain elements $\{0, 1, 2\}$. The smallest non-negative number that is divisible by $1$ and is not contained in the set is $3$.

After the fourth query, the set will contain the elements $\{0, 1, 2, 4\}$. The smallest non-negative number that is divisible by $2$ and is not contained in the set is $6$.

In the second example:

• Initially, the set contains only the element $\{0\}$.
• After adding an integer $100$ the set contains elements $\{0, 100\}$.
• $100\text{-mex}$ of the set is $200$.
• After adding an integer $200$ the set contains elements $\{0, 100, 200\}$.
• $100\text{-mex}$ of the set is $300$.
• After adding an integer $50$ the set contains elements $\{0, 50, 100, 200\}$.
• $50\text{-mex}$ of the set is $150$.