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