CF2115F1.Gellyfish and Lycoris Radiata (Easy Version)

This is the easy version of the problem. The difference between the versions is that in this version, the time limit and the constraints on $n$ and $q$ are lower. You can hack only if you solved all versions of this problem.

Gellyfish has an array consisting of $n$ sets. Initially, all the sets are empty.

Now Gellyfish will do $q$ operations. Each operation contains one modification operation and one query operation, for the $i$-th ($1 \leq i \leq q$) operation:

First, there will be a modification operation, which is one of the following:

1. Insert operation: You are given an integer $r$. For the $1$-th to $r$-th sets, insert element $i$. Note that the element inserted here is $i$, the index of the operation, not the index of the set.
2. Reverse operation: You are given an integer $r$. Reverse the $1$-th to $r$-th sets.
3. Delete operation: You are given an integer $x$. Delete element $x$ from all sets that contain $x$.

Followed by a query operation:

• Query operation: You are given an integer $p$. Output the smallest element in the $p$-th set (If the $p$-th set is empty, the answer is considered to be $0$).

Now, Flower needs to provide the answer for each query operation. Please help her!

Additional constraint on the problem: Gellyfish will only give the next operation after Flower has answered the previous query operation. That is, you need to solve this problem online. Please refer to the input format for more details.

这是该问题的简单版本。两个版本的区别在于：在此版本中，时间限制以及 $n$ 和 $q$ 的约束更小。仅当你已解决该问题的所有版本时，才允许你进行 Hack。

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

接下来 Gellyfish 将执行 $q$ 次操作。每次操作包含一次修改操作和一次查询操作；对于第 $i$ 次操作（$1 \leq i \leq q$）：

首先，执行一次修改操作，其类型为以下之一：

1. 插入操作：给定一个整数 $r$。对第 $1$ 个至第 $r$ 个集合，插入元素 $i$。（注意：此处插入的元素是操作的索引 $i$，而非集合的索引。）
2. 翻转操作：给定一个整数 $r$。将第 $1$ 个至第 $r$ 个集合进行翻转。
3. 删除操作：给定一个整数 $x$。从所有包含元素 $x$ 的集合中删除 $x$。

随后，执行一次查询操作：

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

现在，Flower 需要为每次查询操作提供答案。请帮助她！

本题附加约束：Gellyfish 仅在 Flower 回答完上一次查询操作后，才会给出下一次操作。即，你需要在线求解本题。更多细节请参阅输入格式说明。

The first line contains two integers $n$ and $q$ ($1 \leq n, q \leq 10^5$) — the number of the sets and the number of operations.

As you need to respond to the operations online, the operations will be encoded.

The $i$-th line of the following $q$ lines contains three integers $a$, $b$, and $c$ ($1 \leq a \leq 3$, $1 \leq c \leq n$) — describing the $i$-th operation in an encoded form.

Here, $a$ represents the type of modification operation. Among them, $a=1$ represents Insert operation, $a=2$ represents Reverse operation, $a=3$ represents Delete operation.

• If $a = 1$, then the modification operation is the Insert operation. It will be guaranteed that $1 \leq b \leq n$. $r$ will be calculated as $r=(b+\text{ans}_{i-1}-1) \bmod n + 1$.
• If $a=2$, then the modification operation is the Reverse operation. It will be guaranteed that $1 \leq b \leq n$. $r$ will be calculated as $r=(b+\text{ans}_{i-1}-1) \bmod n + 1$.
• If $a=3$, then the modification operation is the Delete operation. It will be guaranteed that $1 \leq b \leq q$. $x$ will be calculated as $x=(b+\text{ans}_{i-1}-1) \bmod q + 1$.

For the query operation, $p$ will be calculated as $p = (c+\text{ans}_{i-1}-1) \bmod n + 1$.

Here $ \text{ans}{i} (1 \leq i \leq q)$ represents the answer to the query operation in the $i$-th operation. Additionally, we define $ \text{ans}{0} = 0$.

第一行包含两个整数 $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$ 表示插入操作（Insert），$a=2$ 表示翻转操作（Reverse），$a=3$ 表示删除操作（Delete）。

• 若 $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$。

For each query operation, output the answer to the query.

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

All the sets are empty in the beginning, so the array is $[{}, {}, {}, {}, {}]$.

With the decoding method given before, we can see what happens in each operation:

1. For the first operation: $a = 1, r = 2, p = 2$. The modification operation is an Insert operation; element $1$ is inserted into the first two sets; so the array becomes $[{1}, {1}, {}, {}, {}]$, and the smallest element in the second set is $1$.
2. For the second operation: $a = 2, r = 4, p = 2$. The modification operation is a Reverse operation; the first four sets are reversed; so the array becomes $[{}, {}, {1}, {1}, {}]$, and the second set is empty, which means the answer is $0$.
3. For the third operation: $a = 1, r = 5, p = 3$. The modification operation is an Insert operation; element $3$ is inserted into all the sets; so the array becomes $[{3}, {3}, {1, 3}, {1, 3}, {3}]$, and the smallest element in the third set is $1$.
4. For the fourth operation: $a = 2, r = 3, p = 1$. The modification operation is a Reverse operation; the first three sets are reversed; so the array becomes $[{1, 3}, {3}, {3}, {1, 3}, {3}]$, and the smallest element in the first set is $1$.
5. For the fifth operation: $a = 1, r = 1, p = 3$. The modification operation is an Insert operation; element $5$ is inserted into the first set; so the array becomes $[{1, 3, 5}, {3}, {3}, {1, 3}, {3}]$, and the smallest element in the third set is $3$.
6. For the sixth operation: $a = 2, r = 2, p = 2$. The modification operation is a Reverse operation; the first two sets are reversed; so the array becomes $[{3}, {1, 3, 5}, {3}, {1, 3}, {3}]$, and the smallest element in the second set is $1$.
7. For the seventh operation: $a = 3, x = 3, p = 3$. The modification operation is a Delete operation; element $3$ is deleted from all the sets; so the array becomes $[{}, {1, 5}, {}, {1}, {}]$, and the third set is empty, which means the answer is $0$.
8. For the eighth operation: $a = 3, x = 1, p = 2$. The modification operation is a Delete operation; element $1$ is deleted from all the sets; so the array becomes $[{}, {5}, {}, {}, {}]$, and the smallest element in the second set is $5$.
9. For the ninth operation: $a = 3, x = 5, p = 5$. The modification operation is a Delete operation; element $5$ is deleted from all the sets; so the array becomes $[{}, {}, {}, {}, {}]$, and the fifth set is empty, which means the answer is $0$.
10. For the tenth operation: $a = 3, x = 2, p = 4$. The modification operation is a Delete operation; element $2$ is deleted from all the sets; so the array becomes $[{}, {}, {}, {}, {}]$, and the fourth set is empty, which means the answer is $0$.

Please note that although we have not inserted element $2$ into the sets, we still delete element $2$ from all the sets in the tenth operation, which means that the Delete operation doesn't necessarily require the existence of a set to contain the deleted element. It also shows that it is possible to have two Delete operations that delete the same element.

所有集合初始时均为空，因此数组为 $[{}, {}, {}, {}, {}]$。

根据之前给出的解码方法，我们可以观察每次操作中发生的变化：

1. 第一次操作：$a = 1, r = 2, p = 2$。该修改操作为插入（Insert）操作；将元素 $1$ 插入前两个集合；因此数组变为 $[{1}, {1}, {}, {}, {}]$，第二个集合中的最小元素为 $1$。
2. 第二次操作：$a = 2, r = 4, p = 2$。该修改操作为翻转（Reverse）操作；将前四个集合翻转；因此数组变为 $[{}, {}, {1}, {1}, {}]$，第二个集合为空，故答案为 $0$。
3. 第三次操作：$a = 1, r = 5, p = 3$。该修改操作为插入（Insert）操作；将元素 $3$ 插入所有集合；因此数组变为 $[{3}, {3}, {1, 3}, {1, 3}, {3}]$，第三个集合中的最小元素为 $1$。
4. 第四次操作：$a = 2, r = 3, p = 1$。该修改操作为翻转（Reverse）操作；将前三个集合翻转；因此数组变为 $[{1, 3}, {3}, {3}, {1, 3}, {3}]$，第一个集合中的最小元素为 $1$。
5. 第五次操作：$a = 1, r = 1, p = 3$。该修改操作为插入（Insert）操作；将元素 $5$ 插入第一个集合；因此数组变为 $[{1, 3, 5}, {3}, {3}, {1, 3}, {3}]$，第三个集合中的最小元素为 $3$。
6. 第六次操作：$a = 2, r = 2, p = 2$。该修改操作为翻转（Reverse）操作；将前两个集合翻转；因此数组变为 $[{3}, {1, 3, 5}, {3}, {1, 3}, {3}]$，第二个集合中的最小元素为 $1$。
7. 第七次操作：$a = 3, x = 3, p = 3$。该修改操作为删除（Delete）操作；从所有集合中删除元素 $3$；因此数组变为 $[{}, {1, 5}, {}, {1}, {}]$，第三个集合为空，故答案为 $0$。
8. 第八次操作：$a = 3, x = 1, p = 2$。该修改操作为删除（Delete）操作；从所有集合中删除元素 $1$；因此数组变为 $[{}, {5}, {}, {}, {}]$，第二个集合中的最小元素为 $5$。
9. 第九次操作：$a = 3, x = 5, p = 5$。该修改操作为删除（Delete）操作；从所有集合中删除元素 $5$；因此数组变为 $[{}, {}, {}, {}, {}]$，第五个集合为空，故答案为 $0$。
10. 第十次操作：$a = 3, x = 2, p = 4$。该修改操作为删除（Delete）操作；从所有集合中删除元素 $2$；因此数组变为 $[{}, {}, {}, {}, {}]$，第四个集合为空，故答案为 $0$。

请注意：尽管我们从未向集合中插入过元素 $2$，但在第十次操作中仍需从所有集合中删除元素 $2$，这表明删除（Delete）操作并不要求被删元素必须存在于某个集合中。这也说明，有可能出现两次删除同一元素的操作。