小 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 行，每行包含一次命令，格式见题目描述。

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

数据规模与约定

• 对于 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。

CSP-J模拟赛