Codeforces Round 830 (Div. 2) |
---|
Finished |
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:
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.
18+ 1+ 2? 1+ 4? 2+ 6? 3+ 7+ 8? 1? 2+ 5? 1+ 1000000000000000000? 1000000000000000000- 4? 1? 2
3 6 3 3 10 3 2000000000000000000 3 4
10+ 100? 100+ 200? 100- 100? 100+ 50? 50- 50? 50
200 300 100 100 50
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:
Name |
---|