持久找区间极值

Time Limit: 6000ms

Memory Limit: 65535kb

Description

fishhead和鱼儿子一起做游戏。
fishhead给鱼儿子出了大家所熟知的找区间极值的问题,线段树解决。
fishhead给了N个数字,N比较大,然后需要询问M次,M也比较大,每次给出一个L和R,需要找到[L,R]的区间里的最大的数字。

fishhead给鱼儿子的任务是,在很快的时间内给出大量查询的结果。
聪明的鱼儿子很快解决了这个问题,fishhead对此无法直视了,数据结构居然比爹还强,果断不能忍。
为了显示fishhead自己数据结构的超强实力,于是他出了下面一个问题。


现在fishhead增加改变功能,他可以把一个数字改变成另外一个数字,同时,会记录他改变的次数。
fishhead想要知道,在他执行第i次变换之后,指定的[L,R]区间里的最大值是多少呢,当然,fishhead会给出很多的查询,你需要很快解决这个题目。
鱼儿子犯难了,所以向你请求帮助。

Input

第一行输入T(T约为10),表示有T组测试数据。
每组测试数据,第一行首先输入两个整数N,M(1<=N<=50000,1<=M<=100000)
第二行输入N个整数,表示原数组,整数在int范围内。
下面M行,有两种输入形式:
1 a c
2 a b c
另外记录一个偏移量d,对于1操作,对于第a+d个数字变成c+d,对于2操作,输出第c+d次操作后,在区间[a+d, b-d]内的最大值。
对于每组测试数据,d一开始为0,对于每次2操作,e表示输出的整数中,取绝对值后其二进制数1的个数,则有d=d+e。
我们保证在1操作里1<=a+d<=N,2操作里1<=a+d<=b-d<=N,0<=c+d<=当前输入的1操作个数,c+d=0表示原序列,即一次操作都没有。

Output

对于每次2操作,输出相应的最大值。

Sample Input

1
5 4
1 2 3 4 5
1 2 4
1 5 -1
2 1 3 1
2 2 6 1

Sample Output

4
4

Hint

None

Source

None

提交代码