Balance (Easy version)

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.

Sample Input:

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

Sample Output:

3
6
3
3
10
3
2000000000000000000

Sample Input:

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

Sample Output:

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$$$.