题目描述

现在有 $n$ 个学生排成一排，从左数第一个同学编号为 $1$，第二个同学编号为 $2$，$\dots$，第 $i$ 个同学编号为 $i$。

老师有时调换某两位同学的位置，有时会找找某位同学。但是调换换的次数太多了，老师也不记得大家的顺序了，请你帮帮老师。

老师进行了次 $m$ 个操作，有下列三种：

• 1 x y，把从左数第 $x$ 个同学与第 $y$ 个同学交换了位置。
• 2 a，查询当前从左数第 $a$ 个同学的编号。
• 3 b，查询编号为 $b$ 的同学在当前在从左数第几个。

对于每个操作 2 与操作 3，请你将查询的结果输出。

输入格式

第一行两个数 $n$ 和 $m$，用空格隔开。

接下来 $m$ 行每行一个操作，每个操作的格式是下面三种之一，参考题目描述。

• 1 x y
• 2 a
• 3 b

输出格式

针对每一个操作 2 和操作 3，分别输出一行，为该次操作的查询结果。

7 6
2 3
3 5
1 1 3
1 3 5
2 5
3 1

3
5
1
5

• 初始状态，$7$ 位同学从左往右编号分别是 1234567
• 第一个操作：查询左数第 $3$ 个人的编号，结果为 $3$
• 第二个操作：查询编号为 $5$ 的人在左数第几个，结果为第 $5$ 个
• 第三个操作：把左数第 $1$ 个人和左数第 $3$ 个人交换位置。$7$ 位同学从左往右编号分别是 3214567
• 第四个操作：把左数第 $3$ 个人和左数第 $5$ 个人交换位置。操作之后，$7$ 位同学从左往右编号分别是 3254167
• 第五个操作：查询左数第 $5$ 个人编号，结果为 $1$
• 第六个操作：查询编号为 $1$ 的人在左数第几个，结果为第 $5$ 个

数据规模与约定

对于 $100\%$ 的数据，$2 \le n,m \le 5\times10^5$。

• 子任务 1（30 分）：$2 \le n,m \le 10^3$
• 子任务 2（30 分）：没有操作 3
• 子任务 3（40 分）：没有特殊限制