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

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.

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

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

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

Example output:
3
6
3
3
10
3
2000000000000000000

Example input:
6
+ 100
? 100
+ 200
? 100
+ 50
? 50

Example output:
200
300
150

Editorial:
Let's look at a stupid solution and try to improve it.
In a stupid solution, we can simply add to 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. 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.
Let's count for each value $$$x$$$ how many times we can check for its presence in the set. First, we do this for $$$k$$$ such that $$$x$$$ is divisible by $$$k$$$. Secondly, the set must already contain elements $$${0, k, 2k, \ldots, x - k}$$$, that is, $$$\frac{x}{k}$$$ numbers. Note that if $$$k$$$ is not one of the largest divisors of $$$x$$$, then $$$\frac{x}{k}$$$ becomes greater than $$$q$$$. Therefore, this solution will work quite quickly.