CF1732D2.Balance (Hard version)

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.

这是该问题的困难版本。唯一的区别在于本版本中包含删除查询。

初始时，你拥有一个仅含一个元素 $0$ 的集合。你需要处理 $q$ 个如下类型的查询：

• + x — 将整数 $x$ 加入集合；保证该整数当前不在集合中；
• - x — 将整数 $x$ 从集合中删除；保证该整数当前在集合中；
• ? k — 求该集合的 $k\text{-mex}$。

在本题中，我们定义整数集合的 $k\text{-mex}$ 为：不小于 $0$、能被 $k$ 整除、且不在集合中的最小整数 $x$。

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

第一行包含一个整数 $q$（$1 \leq q \leq 2 \cdot 10^5$）—— 表示查询的次数。

接下来的 $q$ 行描述了这些查询。

添加整数 $x$ 的查询格式为 + $x$（$1 \leq x \leq 10^{18}$）。保证 $x$ 当前不在集合中。

删除整数 $x$ 的查询格式为 - $x$（$1 \leq x \leq 10^{18}$）。保证 $x$ 当前在集合中。

查询 $k\text{-mex}$ 的格式为 ? $k$（$1 \leq k \leq 10^{18}$）。

保证至少存在一个类型为 ? 的查询。

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

对于每个类型为 ? 的查询，输出一个整数——该集合的 $k\text{-mex}$。

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

在第一个例子中：

执行第一次和第二次查询后，集合将包含元素 $\{0, 1, 2\}$。不在此集合中、且能被 $1$ 整除的最小非负整数是 $3$。

执行第四次查询后，集合将包含元素 $\{0, 1, 2, 4\}$。不在此集合中、且能被 $2$ 整除的最小非负整数是 $6$。

在第二个例子中：

• 初始时，集合仅包含元素 $\{0\}$。
• 添加整数 $100$ 后，集合包含元素 $\{0, 100\}$。
• 该集合的 $100\text{-mex}$ 为 $200$。
• 添加整数 $200$ 后，集合包含元素 $\{0, 100, 200\}$。
• 该集合的 $100\text{-mex}$ 为 $300$。
• 删除整数 $100$ 后，集合包含元素 $\{0, 200\}$。
• 该集合的 $100\text{-mex}$ 为 $100$。
• 添加整数 $50$ 后，集合包含元素 $\{0, 50, 200\}$。
• 该集合的 $50\text{-mex}$ 为 $100$。
• 删除整数 $50$ 后，集合包含元素 $\{0, 200\}$。
• 该集合的 $100\text{-mex}$ 为 $50$。