codeforces#P1732D2. Balance (Hard version)

Balance (Hard version)

Description

This is the hard version of the problem. The only difference is that in this version there are remove queries.

Initially you have a set containing one element — $0$. You need to handle $q$ queries of the following types:

  • + $x$ — add the integer $x$ to the set. It is guaranteed that this integer is not contained in the set;
  • - $x$ — remove the integer $x$ from the set. It is guaranteed that this integer is contained in the set;
  • ? $k$ — find the $k\text{-mex}$ of the set.

In our problem, we define the $k\text{-mex}$ of a set of integers as the smallest non-negative integer $x$ that is divisible by $k$ and which is not contained in the set.

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$ is not contained in the set.

A remove query of integer $x$ is given in the format - $x$ ($1 \leq x \leq 10^{18}$). It is guaranteed that $x$ is 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 is at least one query of type ?.

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

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$ is not contained in the set.

A remove query of integer $x$ is given in the format - $x$ ($1 \leq x \leq 10^{18}$). It is guaranteed that $x$ is 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 is at least one query of type ?.

Output

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

18
+ 1
+ 2
? 1
+ 4
? 2
+ 6
? 3
+ 7
+ 8
? 1
? 2
+ 5
? 1
+ 1000000000000000000
? 1000000000000000000
- 4
? 1
? 2
10
+ 100
? 100
+ 200
? 100
- 100
? 100
+ 50
? 50
- 50
? 50
3
6
3
3
10
3
2000000000000000000
3
4
200
300
100
100
50

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 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 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 $300$.
  • After removing an integer $100$ the set contains elements $\{0, 200\}$.
  • $100\text{-mex}$ of the set is $100$.
  • After adding an integer $50$ the set contains elements $\{0, 50, 200\}$.
  • $50\text{-mex}$ of the set is $100$.
  • After removing an integer $50$ the set contains elements $\{0, 200\}$.
  • $100\text{-mex}$ of the set is $50$.