D1. 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 — 00. You need to handle qq queries of the following types:
- + xx — add the integer xx to the set. It is guaranteed that this integer is not contained in the set;
- ? kk — find the k-mexk-mex of the set.
In our problem, we define the k-mexk-mex of a set of integers as the smallest non-negative integer xx that is divisible by kk and which is not contained in the set.
Input
The first line contains an integer qq (1≤q≤2⋅1051≤q≤2⋅105) — the number of queries.
The following qq lines describe the queries.
An addition query of integer xx is given in the format + xx (1≤x≤10181≤x≤1018). It is guaranteed that xx was not contained in the set.
A search query of k-mexk-mex is given in the format ? kk (1≤k≤10181≤k≤1018).
It is guaranteed that there will be at least one query of type ?.
Output
For each query of type ? output a single integer — the k-mexk-mex of the set.
Examples
input
Copy
15
+ 1
+ 2
? 1
+ 4
? 2
+ 6
? 3
+ 7
+ 8
? 1
? 2
+ 5
? 1
+ 1000000000000000000
? 1000000000000000000
output
Copy
3 6 3 3 10 3 2000000000000000000
input
Copy
6
+ 100
? 100
+ 200
? 100
+ 50
? 50
output
Copy
200 300 150
Note
In the first example:
After the first and second queries, the set will contain elements {0,1,2}{0,1,2}. The smallest non-negative number that is divisible by 11 and is not contained in the set is 33.
After the fourth query, the set will contain the elements {0,1,2,4}{0,1,2,4}. The smallest non-negative number that is divisible by 22 and is not contained in the set is 66.
In the second example:
- Initially, the set contains only the element {0}{0}.
- After adding an integer 100100 the set contains elements {0,100}{0,100}.
- 100-mex100-mex of the set is 200200.
- After adding an integer 200200 the set contains elements {0,100,200}{0,100,200}.
- 100-mex100-mex of the set is 300300.
- After adding an integer 5050 the set contains elements {0,50,100,200}{0,50,100,200}.
- 50-mex50-mex of the set is 150150.
解析：
要求这个列表当中能被k整除的最小非负元素，且这个元素不被列表包含 。那么很显然，只要从k开始考虑是否满足，如果不满足那就考虑k的倍数是否满足就可以了，但是如果每次询问k的时候都从自身开始加的话绝对会TLE（别问我是怎么知道的），那么这个时候就要节约时间，那么每次询问k并且找到答案之后，就将此时的答案记录的k这个位置，下次再问到k的时候就从这个记录的答案开始找，那么就会节约很多 的时间
ac代码：
#include
#include
#include
#include
#include
#include
#include
#include
#include