上帝之手
时间限制：20s 空间限制：256MB
题目描述
上帝之手操纵着四维空间。假设四维空间中上帝关心的部分共N天，定义第i天结束时一个三维世界的混乱度为Xi。由于一些自然的原因，第i天该世界的混乱度会增加Di，即Xi=Xi-1+Di。但为了世界的平衡，每天该世界都有一个混乱度的上限值Li，即实际上Xi=min{Xi-1+Di , Li}。
上帝想对该四维空间作一系列测试，于是希望你帮忙建立一个模型。具体有以下三种测试：
（1）给定A、B和K，要求找到一个C（A<=C<=B），使得世界以LC-1的初始混乱度从第C天开始发展将得到第K大的XB。你只需告诉上帝第K大的XB值即可。
（2）给定A、B和X0，要求找到一个C（A<=C<=B），使得世界以X0的初始混乱度从第C天开始发展将得到最大的XB。你只需告诉上帝最大的XB值即可（注意：X0可能大于LC-1）。
（3）给定A和B，要求对于所有满足A<=C<=B 的C，求出世界以LC-1的初始混乱度从第C天开始发展将得到的XB的不同值的种数。
当然，上帝还会根据测试的结果修改某些位置的Li。你能成功帮助上帝完成测试吗？
输入格式
第一行包含两个正整数N和M，按序表示总天数和总操作（包含测试和修改）次数。
第二行为N个非负整数 D1-DN，第三行为N+1个非负整数L0-LN。含义见问题描述。
第四行起的M行，每行第一个整数type表示操作种类。
若type=0，则后面跟有两个整数u和x，表示将Lu改为x。
若type>0，则type等于题目描述中对应的测试种类编号。type=1时后面跟有三个整数A、B和K；type=2时后面跟有三个整数A、B和X0；type=3时后面跟有两个整数A和B。具体含义见问题描述。
输出格式
对于每个测试输出一行，包含一个整数表示测试结果。
样例输入
3 5 2 1 3 2 6 7 5 1 1 2 2 3 1 3 0 3 15 3 1 3 2 1 3 2
样例输出
5 1 2 8
提示
对于100%的数据，N<=10^5，M<=2×10^5，0<=Di<=10^4，0<=Li, X0, x<=10^9，0<=u<=N，1<=A<=B<=N，1<=K<=B-A+1。
题目来源
2015年集训队互测