这是问题的简单版本。唯一的区别是,在此版本中没有“删除”查询。
最初,您有一个包含一个元素的集合 - $$$0$$$。您需要处理以下类型的 $$$q$$$ 查询:
- + $$$x$$$ — 将整数 $$$x$$$ 添加到集合中。保证该整数不包含在集合中;
- ? $$$k$$$ — 找到集合中的 $$$k\text{-mex}$$$。
在我们的问题中,我们将一组整数的 $$$k\text{-mex}$$$ 定义为可被 $$$k$$$ 整除且不包含在该集合中的最小非负整数 $$$x$$$。
输入
第一行包含一个整数 $$$q$$$ ($$$1 \leq q \leq 2 \cdot 10^5$$$) — 查询数。
以下 $$$q$$$ 行描述了查询。
整数 $$$x$$$ 的加法查询以 + $$$x$$$ ($$$1 \leq x \leq 10^{18}$$$) 的格式给出。保证 $$$x$$$ 不包含在集合中。
$$$k\text{-mex}$$$ 的搜索查询以以下格式给出? $$$k$$$ ($$$1 \leq k \leq 10^{18}$$$)。
保证至少有一个类型为 ? 的查询。
输出
对于类型为 ? 的每个查询输出单个整数 - 集合的 $$$k\text{-mex}$$$。
示例
输入 #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
注意
在第一个示例中:
在第一次和第二次查询之后,集合将包含元素 $$$\{0, 1, 2\}$$$。可被$$$1$$$整除且不包含在集合中的最小非负数是$$$3$$$。
第四次查询后,集合将包含元素 $$$\{0, 1, 2, 4\}$$$。可被$$$2$$$整除且不包含在集合中的最小非负数是$$$6$$$。
在第二个示例中:
- 最初,集合仅包含元素 $$$\{0\}$$$。
- 添加整数 $$$100$$$ 后,集合包含元素 $$$\{0, 100\}$$$。
- 该组的 $$$100\text{-mex}$$$ 为 $$$200$$$。
- 添加整数 $$$200$$$ 后,集合包含元素 $$$\{0, 100, 200\}$$$。
- 该套装的 $$$100\text{-mex}$$$ 为 $$$300$$$。
- 添加整数 $$$50$$$ 后,集合包含元素 $$$\{0, 50, 100, 200\}$$$。
- 该套装的 $$$50\text{-mex}$$$ 为 $$$150$$$。