题目描述

小 C 有一个集合 $S$，最开始 $S=\{0\}$。

现在有两种操作，分别如下：

• + x，将 $S\leftarrow S\cup\{x\}$，即将元素 $x$ 加入集合 $S$ 中。（一个元素可能会被加入多次）
• ? k，求出最小的整数 $t\times k(t\ge0)$，满足 $t\times k\notin S$。

现在小 C 给了你 $q$ 次命令，每次命令为两种操作中的一种，你需要对于所有的询问操作给出答案。

输入格式

输入的第一行包含一个整数 $q$。

接下来 $q$ 行，每行包含一次命令，格式见题目描述。

输出格式

输出包含若干行，每行输出一个整数，表示当前询问操作的答案。

样例输入 #1

5
+ 7
+ 4
? 3
+ 1
? 2

样例输出 #1

3
2

样例输入 #2

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

样例输出 #2

200
300
150

数据范围

• 对于 $30\%$ 的数据，保证 $q \le 500$。
• 对于另 $30\%$ 的数据，保证 $q$ 次命令中询问次数不超过 $1000$ 种。
• 对于 $100\%$ 的数据，保证 $1 \le q \le 10^{5}$，$1\le x\le 10^9$，$1\le k\le 10^9$。