A15455 | $Balance (Easy version)$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

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.

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

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

输入 #1

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

输出 #1

3
6
3
3
10
3
2000000000000000000

输入 #2

输出 #2

200
300
150

C++ 编辑器

输入

输出