百度之星2009初赛第一轮题三------钉子与木板

问题背景

墙上有n个钉子，编号为1, 2, ..., n。其中钉子i的横坐标为i，纵坐标初始为x_i。可以进行两种操作：
0 k v：移动操作。竖直移动钉子k，坐标变为(k, v)。
1 s t v：测试操作。若在高度为v处放一块横坐标范围是[s,t]的水平木板，它将下落到什么高度？换句话说，求出钉子s, s+1, s+2, …, t的纵坐标中，不超过v的最大值。如果这些钉子的高度全部大于v，则木板将落到地上，高度为0。

注意，在测试操作时，水平木板只是用来测试的“临时木板”，将在测试后立即被拿走，不会影响到后续测试工作。

输入格式

第一行包含两个整数n, m，即钉子的个数和操作的个数（1<=n,m<=10⁵）。以下n行每行一个不超过10⁹的非负整数，即x_i。 以下 m 行为各操作 （1 <= k <= n, 1 <= s < t <= n, 1 <= v <= 10⁹ ）

输出格式

按照输入的顺序，对于每个测试操作输出一个整数，即该测试水平木板的最后高度。

样例输入

5 4
1
3
5
7
9
1 2 4 6
0 3 10
1 3 5 7
1 3 5 5

样例输出

5
7
0