在面向学生的开放编程奥林匹克竞赛中，共有 $n$ 名参赛者，编号为 $1$ 到 $n$。第 $i$ 号参赛者穿着颜色为 $a_i$ 的 T 恤。竞赛组织者计划依次邀请参赛者进入比赛大厅。为了使过程更具观赏性，他们希望避免连续进入的两位参赛者穿着相同颜色的 T 恤。为了实现这一点，参赛者将按照以下算法被邀请：

• 第一位进入比赛大厅的参赛者是 $1$ 号参赛者。
• 随后，每一位新被邀请的参赛者，其 T 恤颜色必须与上一位进入的参赛者不同。如果有多个这样的参赛者，则选择编号最小的那一位。
• 最后，如果所有剩余未进入的参赛者穿着的 T 恤颜色都与上一位进入的参赛者相同，则所有剩余参赛者将按编号递增的顺序被邀请。

在奥赛前夜，组织者准备了一份参赛者入场计划，但在开赛前，他们注意到编号相邻的参赛者有时会交换 T 恤。当然，这导致之前的计划不再符合规则，组织者需要制定一份新的计划。

你需要处理两类询问：

1. 编号为 $x_i$ 和 $(x_i + 1)$ 的两位参赛者交换 T 恤。
2. 找出在考虑了之前所有 T 恤交换的情况下，如果参赛者按照上述算法开始入场，第 $y_i$ 号参赛者进入比赛大厅的顺序（即他是第几个进入的）。

输入格式

第一行包含两个整数 $n$ 和 $q$ ($1 \le n \le 500\,000, 1 \le q \le 500\,000$)，分别表示参赛者人数和询问次数。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$)，表示参赛者按编号顺序排列的初始 T 恤颜色。

接下来的 $q$ 行描述询问。第 $i$ 行包含一个整数 $t_i$ ($1 \le t_i \le 2$)，表示第 $i$ 次询问的类型。

1. 如果 $t_i = 1$，则下一行包含一个整数 $x_i$ ($1 \le x_i < n$)。在这种情况下，第 $i$ 次询问表示编号为 $x_i$ 和 $(x_i + 1)$ 的参赛者交换 T 恤。
2. 如果 $t_i = 2$，则下一行包含一个整数 $y_i$ ($1 \le y_i \le n$)。在这种情况下，第 $i$ 次询问需要你找出在考虑了之前所有 T 恤交换的情况下，如果参赛者按照上述算法开始入场，第 $y_i$ 号参赛者进入比赛大厅的顺序。

输出格式

对于每类询问，输出一个整数并换行——即询问的答案。

保证至少存在一个第二类询问。

样例

样例输入 1

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

样例输出 1

2
4
3
10
2
3
4
6
10

说明

在第一个样例中，初始配置下，参赛者进入比赛大厅的顺序为： $1, 2, 4, 3, 5, 6, 8, 7, 9, 10$ 即 $2$ 号参赛者第二个进入，$3$ 号参赛者第四个进入，$4$ 号参赛者第三个进入，$10$ 号参赛者第十个进入。

在编号 $1$ 和 $2$ 的参赛者交换 T 恤后，参赛者的 T 恤颜色变为： $1, 3, 1, 2, 2, 1, 1, 2, 2, 2$ 因此，在此次变动后，参赛者进入比赛大厅的顺序为： $1, 2, 3, 4, 6, 5, 7, 8, 9, 10$ 即 $2$ 号参赛者第二个进入，$3$ 号参赛者第三个进入，$4$ 号参赛者第四个进入，$5$ 号参赛者第六个进入，$10$ 号参赛者第十个进入。

样例输入 2

10 10
1 2 2 2 3 4 5 6 7 8
2 1
1 1
2 2
1 2
2 3
1 3
2 4
1 4
2 3
2 5

样例输出 2

1
2
2
2
5
4

说明

在第二个样例中，初始配置下，参赛者进入比赛大厅的顺序为： $1, 2, 5, 3, 6, 4, 7, 8, 9, 10$ 即 $1$ 号参赛者第一个进入。

在编号 $1$ 和 $2$ 的参赛者交换 T 恤后，参赛者的 T 恤颜色变为： $2, 1, 2, 2, 3, 4, 5, 6, 7, 8$ 因此，在此次变动后，参赛者进入顺序为： $1, 2, 3, 5, 4, 6, 7, 8, 9, 10$ 即 $2$ 号参赛者第二个进入。

在编号 $2$ 和 $3$ 的参赛者交换 T 恤后，参赛者的 T 恤颜色变为： $2, 2, 1, 2, 3, 4, 5, 6, 7, 8$ 因此，在此次变动后，参赛者进入顺序为： $1, 3, 2, 5, 4, 6, 7, 8, 9, 10$ 即 $3$ 号参赛者第二个进入。

在编号 $3$ 和 $4$ 的参赛者交换 T 恤后，参赛者的 T 恤颜色变为： $2, 2, 2, 1, 3, 4, 5, 6, 7, 8$ 因此，在此次变动后，参赛者进入顺序为： $1, 4, 2, 5, 3, 6, 7, 8, 9, 10$ 即 $4$ 号参赛者第二个进入。

在编号 $4$ 和 $5$ 的参赛者交换 T 恤后，参赛者的 T 恤颜色变为： $2, 2, 2, 3, 1, 4, 5, 6, 7, 8$ 因此，在此次变动后，参赛者进入顺序为： $1, 4, 2, 5, 3, 6, 7, 8, 9, 10$ 即 $3$ 号参赛者第五个进入，且 $5$ 号参赛者第四个进入。

评分

本题的测试点共分为 12 个组。只有通过该组中的所有测试点以及之前所有组的测试点，才能获得该组的分数。注意，某些组不需要通过样例测试。离线验证（Offline verification）意味着该组测试点的结果仅在比赛结束后可见。每组的最终得分为所有提交记录中该组测试点所获得的最高分。