CF1732D1.Balance (Easy version)

This is the easy version of the problem. The only difference is that in this version there are no "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;
• ? $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$ 加入集合。保证该整数当前不在集合中；
• ? $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$ was not 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 will be at least one query of type ?.

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

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

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

搜索查询：格式为 ? $k$（$1 \leq k \leq 10^{18}$），表示查询当前集合的 $k\text{-mex}$。

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

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

在第一个例子中：

执行第一次和第二次查询后，集合将包含元素 $\{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$。
• 添加整数 $50$ 后，集合包含元素 $\{0, 50, 100, 200\}$。
• 该集合的 $50\text{-mex}$ 为 $150$。