Balance (Hard version)
Contest: Codeforces Round 830 (Div. 2)
Difficulty rating: 2400
Tags: brute force, data structures, number theory

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.

Input format:
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 format:
For each query of type ? output a single integer — the $$$k\text{-mex}$$$ of the set.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

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

Example input:
18
+ 1
+ 2
? 1
+ 4
? 2
+ 6
? 3
+ 7
+ 8
? 1
? 2
+ 5
? 1
+ 1000000000000000000
? 1000000000000000000
- 4
? 1
? 2

Example output:
3
6
3
3
10
3
2000000000000000000
3
4

Example input:
10
+ 100
? 100
+ 200
? 100
- 100
? 100
+ 50
? 50
- 50
? 50

Example output:
200
300
100
100
50

Editorial:
Let's look at a stupid solution and try to improve it.
In a stupid solution, we can simply add and remove elements from the set, and when answering a query, iterate over the numbers $$${0, k, 2k, 3k, \ldots}$$$ and so on until we find the answer. This solution will take a long time if the answer is $$$c \cdot k$$$, where $$$c$$$ is large.
We will improve the solution, first consider the solution of the problem without the removal operation. If a request comes to us for the first time for a given $$$k$$$, then we calculate the answer for it greedily and remember it. In the future, we will no longer check with $$$0$$$ whether there is a number in the set, but with the previous answer.
Now consider a variant of the problem with the delete operation. Let's set for a fixed $$$k$$$ to store all the numbers that we have removed and they are $$$\leq$$$ than the maximum answer found for this $$$k$$$. Then let's see what happens during the search for an answer operation. If set for a given $$$k$$$ is not empty, then the answer will be the minimum element from the set, otherwise we will try to improve the current maximum answer for this $$$k$$$ (that is, if it was equal to $$$c \cdot k$$$, then we will check $$$ c \cdot k, (c + 1) \cdot k, \ldots$$$).
It remains to figure out how we can recalculate these set in the case of an add/remove operation. Let's actually just remember for each value in which set it participates and we will update all of them.
Let's calculate the running time. Let's understand how many sets a given value $$$x$$$ can participate in. First, it lies in sets where $$$x$$$ is divisible by $$$k$$$. Second, if $$$x$$$ is in the set for the number $$$k$$$, then at least $$$\frac{x}{k}$$$ numbers have already been added. That is, if $$$x$$$ lies in $$$t$$$ sets and among these $$$k$$$ there are the largest divisors of $$$x$$$, then we should already have added approximately $$$\sum\limits_{k_i=1}^t \frac{x }{k_i}$$$, where $$$k_i$$$ is the $$$i$$$-th largest divisor of $$$x$$$. Since we have $$$q$$$ queries in total, the given value $$$x$$$ may not lie in a large number of sets.