题目描述

在遥远的数学森林里，聪明兔和大笨龙正在玩一种新式的跳格子游戏。森林里有一排共 $n$ 个树桩，每个树桩 $j$ 上都标有一个神秘数字 $a_j$，代表这个位置能提供的“弹跳能量”。

游戏规则如下： 如果你从位置 $p$ 出发，你当前能跳到的最远位置 $i$ 取决于你经过的所有树桩中，能量最大的那一个。只要满足 $max_(j=p)^i a_j > i$，就说明当前的能量还没耗尽，你必须继续往后跳。

直到你到达某一个位置 $i$，满足 $max_(j=p)^i a_j <= i$，你才会停下来。那个让你停下的最小位置 $i$，就是聪明兔想要寻找的“终点”。

大笨龙是个捣蛋鬼，他会时不时改变某个树桩上的数字。你需要处理 $q$ 次操作，包括修改树桩能量和询问聪明兔的终点。

输入格式

输入的第一行包含两个正整数 $n,q$，表示序列 $a$ 的长度和询问的次数。

第二行包含 $n$ 个正整数，第 $i$ 个正整数表示 $a_i$。

接下来 $q$ 行，修改操作对应三个整数 $1,u,x$ 表示修改 $a_u$ 的值为 $x$；询问对应两个整数 $2,p$ 表示聪明兔从树桩 $p$ 开始游戏。

输出格式

对每个询问输出一个整数，表示聪明兔停留的终点。数据保证聪明兔可以在 $n$ 之前停下。

样例1输入

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

样例1输出

3
7
7