题目描述

小 Z 掌握了时间之力。

小 Z 有 $n$ 个物品。小 Z 想将这些物品排成一排，在时刻 $i$ ，他会将编号为 $i$ 的物品插入到当前序列中从左往右第 $t_i$ 个物品之前。

为了体验穿越时空的感觉，小 Z 可能会回到过去的某个时刻，并修改该时刻原本应执行的操作。

小 Z 害怕因修改时间线而引发时间乱流，因此他还可能再次穿越到某个时刻，并查询此时某个物品在序列中的位置。请你帮他模拟这一系列操作，以验证时空是否错乱。

输入格式

输入的第一行包含一个非负整数 $c$ ，分别表示测试点编号。$c = 0$ 表示该测试点为样例。

第二行包含两个正整数 $n, q$ ，表示物品数量和操作个数。

第三行包含 $n$ 个正整数 $t_1, t_2, \dots, t_n$ ，其中 $t_i$ 表示 $i$ 号物品插入的位置。

接下来 $q$ 行，每一行为以下两种操作中的一个：

• 1 p y （$1\le y\le p\le n$），表示修改时刻 $p$ 时的操作，即将 $t_p$ 修改为 $y$ 。
• 2 p z （$1\le z \le p\le n$），表示查询时刻 $p$ 时 $z$ 号物品的位置。

输出格式

对于每个查询操作，输出一行一个整数表示答案。

样例 1 输入

0
4 9
1 1 2 3
2 4 1
2 4 2
2 4 3
2 4 4
1 3 3
2 4 1
2 4 2
2 4 3
2 4 4

样例 1 输出

4
1
2
3
2
1
4
3

样例 1 解释

初始，物品序列为 $[2,3,4,1]$ 。

在第 $5$ 个操作后，物品序列为 $[2,1,4,3]$ 。

数据范围

$1\le n,q\le 3\times 10^5, 1 \le t_i\le i$ 。

特殊性质 A：不存在 $1$ 操作。