Did you think that you could safely leave Ozersk after visiting a friend? Of course not. The policeman again stopped you and again asks you to solve the problem to make sure that you can leave the city. You will have to solve another problem.
Initially, you have a set that has a single — this is 0. You will need to support q queries like this:
+ x — add the number x to the set. It is guaranteed that it was not there before,
- x — remove the number x from the set. It is guaranteed that this number is there,
? k — find k − mex sets.
In our problem, we assume that k − mex sets — is the smallest non-negative integer x that is divisible by k and is not in the set.
Input
The first line contains an integer q (1 <= q <= 2 · 10
5) — number of requests.
The next q lines contain descriptions of queries. If this is an add request, then in the format
+ x (1 <= x <= 10
18) if delete request then - x (1 <= x <= 10
18) if the same search query, then ? k (1 <= k <= 10
18). It is guaranteed that there will be at least one query like ?.
Imprint
For each query like ? output k − mex sets.
Examples
| # |
Input |
Output |
| 1 |
18
+ 1
+ 2
? 1
+ 4
? 2
+ 6
? 3
+7
+8
? 1
? 2
+5
? 1
+ 100000000
? 100000000
- 4
? 1
? 2 |
3
6
3
3
10
3
200000000
3
4 |
Remark
After the first and second queries, the set will contain elements 0,1,2. The smallest non-negative number that is not divisible by 1 and is not in the set is 3.
After the fourth query, the set will contain elements 0,1,2,4. The smallest non-negative number that is not divisible by 2 and is not in the set is 6