Rejudge Progress:
2530: Crysis 3
Time Limit: 5000 MS Memory Limit: 65536 KBTotal Submit: 88 Accepted: 35 Page View: 110
Submit Status Discuss
Description
公元2047年，人类已经无法阻止Ceph入侵地球了！上决╇ф凭借着他的黑科技，在公元2023年研制出了Nanosuit 1.0。二十三年过去了，Nanosuit已经进化到了Nanosuit 3.0版本，具有超强的隐身、护甲、力量等2015年的人不可想象的超人类功能，而且配备了最强大的武器：狩猎弓。上决╇ф为了拯救世界，决定装备上最强的Nanosuit 3.0成为Prophet。
上图为上决╇ф在SWUST之战中使用狩猎弓与很多的Ceph进行战斗，我们可以很清楚地看到，Ceph居然很傻逼地站成了一排，毕竟外星人的世界我们懂不起。再看看，中间那个，体积这么大，肯定攻击力不同寻常，一定要先把这个Ceph干掉！但是，看下一张图，Nanosuit 3.0面罩反射的图:
这是有多少Ceph？不多，也就不超过100000只嘛。拿着狩猎弓慢慢射就行了。
现在的问题是，在这排成一排的Ceph中，上决╇ф想知道，在某个区间内，战斗力最强的Ceph在什么位置，以方便做出作战方案。但是，Ceph毕竟是外星人，战斗力是会变的！我们需要及时第更新数据，告诉上决╇ф他想知道的区间内最强Ceph的位置。
What are you prepared to sacrifice?
Input
第一行，是一个正整数T，表示测试的组数。
对于每一组测试，第一行是一个正整数n，m（1 <= n <= 100000）。代表Ceph的数目和操作次数。
接下来一排，有n个正整数数Ai，（1 <= Ai <= 1000000），分别代表从左往右第i只Ceph的战斗力。
接下来是m次操作。
每次操作为一行，每行有三个正整数op a b。op只可能为1或者2。当op=1时，为询问区间[a,b]内战斗力最强Ceph的位置（1 <= a <= b <= n）。当op=2时，表示在a位置的Ceph战斗力变成了b（1 <= a <=n,1 <= b <= 1000000）。
Output
对于每一次询问，输入区间内最强Ceph 的位置，如果区间内有多个最强Ceph，输入坐靠左边的那个位置。
1
5 3
1 1 1 1 1
1 1 5
2 3 5
1 1 5
1
3