F2. 水母与彼岸花 (困难版)

时间限制： 5 秒
内存限制： 1024 MB

这是该问题的困难版。与简单版的区别在于，本版本的时间限制以及 $n$ 和 $q$ 的限制更高。只有解决了本题所有版本后，你才能进行 Hack。

---

题目描述

水母有一个由 $n$ 个集合组成的数组。初始时，所有集合均为空集。

接下来水母会进行 $q$ 次操作。每次操作包含一个修改操作和一个查询操作。对于第 $i$ 次操作（$1 \le i \le q$）：

首先，有一个修改操作，可以是以下三种之一：

• 插入操作：给定一个整数 $r$。向第 $1$ 到第 $r$ 个集合中插入元素 $i$。注意，这里插入的元素是操作编号 $i$，而不是集合的编号。
• 翻转操作：给定一个整数 $r$。翻转第 $1$ 到第 $r$ 个集合的顺序。
• 删除操作：给定一个整数 $x$。从所有包含元素 $x$ 的集合中删除该元素。

接着，是一个查询操作：

• 查询操作：给定一个整数 $p$。输出第 $p$ 个集合中的最小元素（如果第 $p$ 个集合为空，则答案视为 $0$）。

现在，彼岸花需要为每个查询操作提供答案。请帮助她！

额外约束：水母只有在彼岸花回答完上一个查询操作后，才会给出下一个操作。也就是说，你需要在线解决这个问题。更多细节请参考输入格式。

---

输入格式

第一行包含两个整数 $n$ 和 $q$（$1 \le n, q \le 3 \times 10^5$）—— 集合的个数和操作次数。

由于你需要在线回答操作，所以操作将被编码。

接下来的 $q$ 行中，第 $i$ 行包含三个整数 $a$、$b$ 和 $c$（$1 \le a \le 3$，$1 \le c \le n$）—— 以编码形式描述第 $i$ 次操作。

其中，$a$ 表示修改操作的类型：

• $a = 1$ 表示插入操作
• $a = 2$ 表示翻转操作
• $a = 3$ 表示删除操作

如果 $a = 1$，则修改操作为插入操作。保证 $1 \le b \le n$。$r$ 的计算方式为：

$$r = (b + ans_{i-1} - 1) \bmod n + 1$$

如果 $a = 2$，则修改操作为翻转操作。保证 $1 \le b \le n$。$r$ 的计算方式为：

$$r = (b + ans_{i-1} - 1) \bmod n + 1$$

如果 $a = 3$，则修改操作为删除操作。保证 $1 \le b \le q$。$x$ 的计算方式为：

$$x = (b + ans_{i-1} - 1) \bmod q + 1$$

对于查询操作，$p$ 的计算方式为：

$$p = (c + ans_{i-1} - 1) \bmod n + 1$$

这里 $ans_i$（$1 \le i \le q$）表示第 $i$ 次操作中查询操作的答案。另外，我们定义 $ans_0 = 0$。

---

输出格式

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

---

样例输入

5 10
1 2 2
2 3 1
1 5 3
2 2 5
1 5 2
2 4 4
3 2 2
3 1 2
3 10 5
3 2 4

样例输出

1
0
1
1
3
1
0
5
0
0

---

样例解释

初始所有集合为空，数组为 $[\{\}, \{\}, \{\}, \{\}, \{\}]$。

根据给出的解码方法，我们可以知道每次操作的具体内容：

1. 第1次操作：$a=1, r=2, p=2$。修改操作为插入操作，将元素 $1$ 插入前两个集合，数组变为 $[\{1\}, \{1\}, \{\}, \{\}, \{\}]$。第2个集合的最小元素为 $1$。
2. 第2次操作：$a=2, r=4, p=2$。修改操作为翻转操作，翻转前4个集合，数组变为 $[\{\}, \{\}, \{1\}, \{1\}, \{\}]$。第2个集合为空，答案为 $0$。
3. 第3次操作：$a=1, r=5, p=3$。修改操作为插入操作，将元素 $3$ 插入所有集合，数组变为 $[\{3\}, \{3\}, \{1,3\}, \{1,3\}, \{3\}]$。第3个集合的最小元素为 $1$。
4. 第4次操作：$a=2, r=3, p=1$。修改操作为翻转操作，翻转前3个集合，数组变为 $[\{1,3\}, \{3\}, \{3\}, \{1,3\}, \{3\}]$。第1个集合的最小元素为 $1$。
5. 第5次操作：$a=1, r=1, p=3$。修改操作为插入操作，将元素 $5$ 插入第1个集合，数组变为 $[\{1,3,5\}, \{3\}, \{3\}, \{1,3\}, \{3\}]$。第3个集合的最小元素为 $3$。
6. 第6次操作：$a=2, r=2, p=2$。修改操作为翻转操作，翻转前2个集合，数组变为 $[\{3\}, \{1,3,5\}, \{3\}, \{1,3\}, \{3\}]$。第2个集合的最小元素为 $1$。
7. 第7次操作：$a=3, x=3, p=3$。修改操作为删除操作，从所有集合中删除元素 $3$，数组变为 $[\{\}, \{1,5\}, \{\}, \{1\}, \{\}]$。第3个集合为空，答案为 $0$。
8. 第8次操作：$a=3, x=1, p=2$。修改操作为删除操作，从所有集合中删除元素 $1$，数组变为 $[\{\}, \{5\}, \{\}, \{\}, \{\}]$。第2个集合的最小元素为 $5$。
9. 第9次操作：$a=3, x=5, p=5$。修改操作为删除操作，从所有集合中删除元素 $5$，数组变为 $[\{\}, \{\}, \{\}, \{\}, \{\}]$。第5个集合为空，答案为 $0$。
10. 第10次操作：$a=3, x=2, p=4$。修改操作为删除操作，从所有集合中删除元素 $2$，数组变为 $[\{\}, \{\}, \{\}, \{\}, \{\}]$。第4个集合为空，答案为 $0$。

请注意，虽然我们从未将元素 $2$ 插入过任何集合，但在第10次操作中仍然执行了删除操作，这表明删除操作并不要求被删除的元素一定存在于某个集合中。同时，这也说明多次删除同一个元素是可能的。