这是问题的简单版本。版本之间的区别在于,该版本的时间限制以及$$$n$$$和$$$q$$$的约束较低。只有解决了该问题的所有版本,您才能破解。
Gellyfish 有一个由 $$$n$$$ 组组成的数组。最初,所有集合都是空的。
现在 Gellyfish 将执行 $$$q$$$ 操作。每个操作包含一个修改操作和一个查询操作,对于第 $$$i$$$ ($$$1 \leq i \leq q$$$) 操作:
首先,会有一个修改操作,它是以下之一:
- 插入 操作:给你一个整数$$$r$$$。对于第 $$$1$$$ 到第 $$$r$$$ 组,插入元素 $$$i$$$。注意,这里插入的元素是$$$i$$$,是操作的索引,而不是集合的索引。
- 反向 操作:给你一个整数$$$r$$$。将第 $$$1$$$ 组反转到第 $$$r$$$ 组。
- 删除 操作:给你一个整数$$$x$$$。从包含 $$$x$$$ 的所有集合中删除元素 $$$x$$$。
接下来是查询操作:
- 查询 操作:给你一个整数$$$p$$$。输出第 $$$p$$$ 个集合中的最小元素(如果第 $$$p$$$ 个集合为空,则答案被认为是 $$$0$$$)。
现在,Flower 需要为每个查询操作提供答案。请帮助她!
对该问题的附加约束:Gellyfish只有在Flower回答了上一个查询操作后才会给出下一个操作。也就是说,你需要解决这个问题 在线。请参阅输入格式了解更多详细信息。
输入
第一行包含两个整数 $$$n$$$ 和 $$$q$$$ ($$$1 \leq n, q \leq 10^5$$$) - 集合的数量和操作的数量。
由于您需要在线响应操作,因此操作将会被编码。
以下 $$$q$$$ 行中的第 $$$i$$$ 行包含三个整数 $$$a$$$、$$$b$$$ 和 $$$c$$$ ($$$1 \leq a \leq 3$$$, $$$1 \leq c \leq n$$$) — 以编码形式描述第 $$$i$$$ 操作。
这里,$$$a$$$表示修改操作的类型。其中$$$a=1$$$代表 插入 运算,$$$a=2$$$代表 反向 运算,$$$a=3$$$代表 删除 操作。
- 如果$$$a = 1$$$,则修改操作是 插入 操作。将保证 $$$1 \leq b \leq n$$$。 $$$r$$$ 将计算为 $$$r=(b+\text{ans}_{i-1}-1) \bmod n + 1$$$。
- 如果$$$a=2$$$,则修改操作为 反向 操作。将保证 $$$1 \leq b \leq n$$$。 $$$r$$$ 将计算为 $$$r=(b+\text{ans}_{i-1}-1) \bmod n + 1$$$。
- 如果$$$a=3$$$,则修改操作为 删除 操作。将保证 $$$1 \leq b \leq q$$$。 $$$x$$$ 将计算为 $$$x=(b+\text{ans}_{i-1}-1) \bmod q + 1$$$。
对于查询操作,$$$p$$$ 将计算为 $$$p = (c+\text{ans}_{i-1}-1) \bmod n + 1$$$。
这里$$$ \text{ans}_{i} (1 \leq i \leq q)$$$表示第$$$i$$$操作中查询操作的答案。此外,我们定义 $$$ \text{ans}_{0} = 0$$$。
输出
对于每个查询操作,输出查询的答案。
示例
输入复制
5 101 2 22 3 11 5 32 2 51 5 22 4 43 2 23 1 23 10 53 2 4
输出复制
1 0 1 1 3 1 0 5 0 0
注意
所有集合一开始都是空的,所以数组是$$$[\{\}, \{\}, \{\}, \{\}, \{\}]$$$。
通过之前给出的解码方法,我们可以看到每个操作发生了什么:
- 对于第一个操作:$$$a = 1,r = 2,p = 2$$$。修改操作是一个 插入 操作;元素 $$$1$$$ 被插入到前两个集合中;因此数组变为 $$$[\{1\}, \{1\}, \{\}, \{\}, \{\}]$$$,第二组中的最小元素是 $$$1$$$。
- 对于第二个操作:$$$a = 2,r = 4,p = 2$$$。修改操作是一个 反向 操作;前四组逆转;所以数组变成$$$[\{\}, \{\}, \{1\}, \{1\}, \{\}]$$$,第二组为空,这意味着答案是$$$0$$$。
- 对于第三个操作:$$$a = 1,r = 5,p = 3$$$。修改操作是一个 插入 操作;元素 $$$3$$$ 被插入到所有集合中;因此数组变为 $$$[\{3\}, \{3\}, \{1, 3\}, \{1, 3\}, \{3\}]$$$,第三组中的最小元素是 $$$1$$$。
- 对于第四个操作:$$$a = 2,r = 3,p = 1$$$。修改操作是一个 反向 操作;前三组逆转;因此数组变为 $$$[\{1, 3\}, \{3\}, \{3\}, \{1, 3\}, \{3\}]$$$,第一个集合中的最小元素是 $$$1$$$。
- 对于第五个操作:$$$a = 1,r = 1,p = 3$$$。修改操作是一个 插入 操作;元素 $$$5$$$ 被插入到第一个集合中;因此数组变为 $$$[\{1, 3, 5\}, \{3\}, \{3\}, \{1, 3\}, \{3\}]$$$,第三组中的最小元素是 $$$3$$$。
- 对于第六个操作:$$$a = 2,r = 2,p = 2$$$。修改操作是一个 反向 操作;前两组相反;因此数组变为 $$$[\{3\}, \{1, 3, 5\}, \{3\}, \{1, 3\}, \{3\}]$$$,第二组中的最小元素是 $$$1$$$。
- 对于第七个操作:$$$a = 3,x = 3,p = 3$$$。修改操作是一个 删除 操作;元素 $$$3$$$ 从所有集合中删除;所以数组就变成了$$$[\{\}, \{1, 5\}, \{\}, \{1\}, \{\}]$$$,而第三组是空的,这意味着答案是$$$0$$$。
- 对于第八个操作:$$$a = 3,x = 1,p = 2$$$。修改操作是一个 删除 操作;元素 $$$1$$$ 从所有集合中删除;因此数组变为 $$$[\{\}, \{5\}, \{\}, \{\}, \{\}]$$$,第二组中的最小元素是 $$$5$$$。
- 对于第九个操作:$$$a = 3,x = 5,p = 5$$$。修改操作是一个 删除 操作;元素 $$$5$$$ 从所有集合中删除;所以数组变成$$$[\{\}, \{\}, \{\}, \{\}, \{\}]$$$,第五组为空,这意味着答案是$$$0$$$。
- 对于第十次操作:$$$a = 3,x = 2,p = 4$$$。修改操作是一个 删除 操作;元素 $$$2$$$ 从所有集合中删除;所以数组就变成$$$[\{\}, \{\}, \{\}, \{\}, \{\}]$$$,第四组为空,这意味着答案是$$$0$$$。
请注意,虽然我们没有将元素$$$2$$$插入到集合中,但我们仍然在第十次操作中从所有集合中删除了元素$$$2$$$,这意味着 删除 操作不一定需要存在包含已删除元素的集合。它还表明可以有两个 删除 删除相同元素的操作。