← 返回题目列表

Codeforces · 1732/D1

D1. 平衡(简易版)

中文机器翻译题面 查看原题

这是问题的简单版本。唯一的区别是,在此版本中没有“删除”查询。

最初,您有一个包含一个元素的集合 - $$$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$$$。