CF1217F.Forced Online Queries Problem

You are given an undirected graph with $n$ vertices numbered from $1$ to $n$. Initially there are no edges.

You are asked to perform some queries on the graph. Let $last$ be the answer to the latest query of the second type, it is set to $0$ before the first such query. Then the queries are the following:

• $1~x~y$ ($1 \le x, y \le n$, $x \ne y$) — add an undirected edge between the vertices $(x + last - 1)~mod~n + 1$ and $(y + last - 1)~mod~n + 1$ if it doesn't exist yet, otherwise remove it;
• $2~x~y$ ($1 \le x, y \le n$, $x \ne y$) — check if there exists a path between the vertices $(x + last - 1)~mod~n + 1$ and $(y + last - 1)~mod~n + 1$, which goes only through currently existing edges, and set $last$ to $1$ if so and $0$ otherwise.

Good luck!

你被给定一个包含 $n$ 个顶点的无向图，顶点编号为 $1$ 到 $n$。初始时图中没有边。

你需要对图执行若干查询操作。令 $last$ 表示上一次第二类查询的答案；在首次执行第二类查询之前，$last$ 的初始值为 $0$。查询操作如下：

• $1~x~y$（其中 $1 \le x, y \le n$，且 $x \ne y$）—— 若边尚未存在，则在顶点 $(x + last - 1)~\bmod~n + 1$ 与 $(y + last - 1)~\bmod~n + 1$ 之间添加一条无向边；否则，删除该边；
• $2~x~y$（其中 $1 \le x, y \le n$，且 $x \ne y$）—— 检查是否存在一条仅经过当前已存在边的路径，连接顶点 $(x + last - 1)~\bmod~n + 1$ 与 $(y + last - 1)~\bmod~n + 1$；若存在则将 $last$ 设为 $1$，否则设为 $0$。

祝你好运！

The first line contains two integer numbers $n$ and $m$ ($2 \le n, m \le 2 \cdot 10^5$) — the number of vertices and the number of queries, respectively.

Each of the following $m$ lines contains a query of one of two aforementioned types. It is guaranteed that there is at least one query of the second type.

第一行包含两个整数 $n$ 和 $m$（$2 \le n, m \le 2 \cdot 10^5$），分别表示顶点数和查询数。

接下来的 $m$ 行中，每行包含一个上述两种类型之一的查询。保证至少存在一个第二类查询。

Print a string, consisting of characters '0' and '1'. The $i$-th character should be the answer to the $i$-th query of the second type. Therefore the length of the string should be equal to the number of queries of the second type.

输出一个由字符 '0' 和 '1' 组成的字符串。其中第 $i$ 个字符应为第 $i$ 个第二类查询的答案。因此，该字符串的长度应等于第二类查询的数量。

The converted queries in the first example are:

• 1 1 2
• 1 1 3
• 2 3 2
• 1 3 5
• 2 4 5
• 1 2 4
• 2 3 4
• 1 2 4
• 2 5 4

The converted queries in the second example are:

• 1 1 2
• 1 2 3
• 1 3 1
• 2 1 3
• 1 1 3
• 2 3 1
• 1 2 3
• 2 2 3
• 2 1 2

第一个示例中转换后的查询为：

• 1 1 2
• 1 1 3
• 2 3 2
• 1 3 5
• 2 4 5
• 1 2 4
• 2 3 4
• 1 2 4
• 2 5 4

第二个示例中转换后的查询为：

• 1 1 2
• 1 2 3
• 1 3 1
• 2 1 3
• 1 1 3
• 2 3 1
• 1 2 3
• 2 2 3
• 2 1 2