CF2115F2 Gellyfish and Lycoris Radiata (Hard Version)

这是该问题的困难版本。不同之处在于本版本中 $n$ 和 $q$ 的限制更高，时间限制也更严格。只有在你解决了所有版本的问题后，才能进行 hack。 Gellyfish 有一个包含 $n$ 个集合的数组。最初，所有集合都是空的。 现在，Gellyfish 将进行 $q$ 次操作。每次操作包含一次修改操作和一次查询操作，对于第 $i$ 次（$1 \leq i \leq q$）操作： 首先，会有一次修改操作，可能是以下三种之一： 1. 插入操作：给定一个整数 $r$。将元素 $i$ 插入第 $1$ 到第 $r$ 个集合中。注意，这里插入的元素是 $i$，即操作的编号，而不是集合的编号。 2. 反转操作：给定一个整数 $r$。将第 $1$ 到第 $r$ 个集合的顺序反转。 3. 删除操作：给定一个整数 $x$。从所有包含 $x$ 的集合中删除元素 $x$。 接下来是一次查询操作： - 查询操作：给定一个整数 $p$。输出第 $p$ 个集合中的最小元素（如果该集合为空，则答案为 $0$）。 现在，Flower 需要为每次查询操作提供答案。请你帮助她！ 本题还有一个额外限制：只有在 Flower 回答了上一次查询操作后，Gellyfish 才会给出下一次操作。也就是说，你需要在线地解决本题。请参考输入格式了解更多细节。

第一行包含两个整数 $n$ 和 $q$（$1 \leq n, q \leq 3 \times 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$。

对于每次查询操作，输出查询的答案。

所有集合一开始都是空的，因此数组为 $[\{\}, \{\}, \{\}, \{\}, \{\}]$。 根据前述的解码方法，我们可以看到每次操作发生了什么： 1. 第一次操作：$a=1, r=2, p=2$。修改操作为插入操作，将元素 $1$ 插入前两个集合，数组变为 $[\{1\}, \{1\}, \{\}, \{\}, \{\}]$，第二个集合的最小元素为 $1$。 2. 第二次操作：$a=2, r=4, p=2$。修改操作为反转操作，前四个集合顺序反转，数组变为 $[\{\}, \{\}, \{1\}, \{1\}, \{\}]$，第二个集合为空，答案为 $0$。 3. 第三次操作：$a=1, r=5, p=3$。修改操作为插入操作，将元素 $3$ 插入所有集合，数组变为 $[\{3\}, \{3\}, \{1, 3\}, \{1, 3\}, \{3\}]$，第三个集合的最小元素为 $1$。 4. 第四次操作：$a=2, r=3, p=1$。修改操作为反转操作，前三个集合顺序反转，数组变为 $[\{1, 3\}, \{3\}, \{3\}, \{1, 3\}, \{3\}]$，第一个集合的最小元素为 $1$。 5. 第五次操作：$a=1, r=1, p=3$。修改操作为插入操作，将元素 $5$ 插入第一个集合，数组变为 $[\{1, 3, 5\}, \{3\}, \{3\}, \{1, 3\}, \{3\}]$，第三个集合的最小元素为 $3$。 6. 第六次操作：$a=2, r=2, p=2$。修改操作为反转操作，前两个集合顺序反转，数组变为 $[\{3\}, \{1, 3, 5\}, \{3\}, \{1, 3\}, \{3\}]$，第二个集合的最小元素为 $1$。 7. 第七次操作：$a=3, x=3, p=3$。修改操作为删除操作，从所有集合中删除元素 $3$，数组变为 $[\{\}, \{1, 5\}, \{\}, \{1\}, \{\}]$，第三个集合为空，答案为 $0$。 8. 第八次操作：$a=3, x=1, p=2$。修改操作为删除操作，从所有集合中删除元素 $1$，数组变为 $[\{\}, \{5\}, \{\}, \{\}, \{\}]$，第二个集合的最小元素为 $5$。 9. 第九次操作：$a=3, x=5, p=5$。修改操作为删除操作，从所有集合中删除元素 $5$，数组变为 $[\{\}, \{\}, \{\}, \{\}, \{\}]$，第五个集合为空，答案为 $0$。 10. 第十次操作：$a=3, x=2, p=4$。修改操作为删除操作，从所有集合中删除元素 $2$，数组变为 $[\{\}, \{\}, \{\}, \{\}, \{\}]$，第四个集合为空，答案为 $0$。 请注意，尽管我们没有将元素 $2$ 插入到集合中，但在第十次操作中仍然从所有集合中删除了元素 $2$，这说明删除操作不要求被删除的元素一定存在于集合中。同时也说明，可能会有两次删除操作删除同一个元素。 由 ChatGPT 4.1 翻译