Balance (Easy version)

题意翻译

有一个整数集合，初始只有一个元素 $0$，有两种操作，分别形如 `+ x` 和 `? k`。第一种操作的含义是在集合中加入一个元素 $x$，第二种是希望找出最小的整数 $t$，使得 $t\times k$ 不在集合内。

题目描述

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

6
+ 100
? 100
+ 200
? 100
+ 50
? 50

输出样例 #2

200
300
150

说明

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