题目描述
这是一道模板题。
给你两个序列 Ki 和 Bi,要求支持在线进行如下操作:
-
给 X>0,对于每个 Bi,变成 Bi+KiX。
-
给 L,R,Y,求出在 i∈[L,R] 中第 Y 大的 Bi 值。
-
修改一组 Ki,Bi。
输入格式
第一行输入两个正整数 N,Q。
接下来一行,输入 N 个整数表示 Ki。
接下来一行,输入 N 个整数表示 Bi。
接下来共 Q 行,每行首先输入一个整数表示操作编号,分别有以下三种情况:
- 1 X
- 2 L R Y
- 3 i k b
输出格式
对于每个 2 询问,输出一个整数表示答案。
样例
3 10
-1 3 1
1 -3 0
2 1 3 1
2 1 3 2
2 1 3 3
1 1
2 1 3 1
2 1 3 2
2 1 3 3
3 2 0 2
2 2 3 1
2 2 3 2
1
0
-3
1
0
0
2
1
数据范围与提示
对于 100% 的数据,保证 1≤N,Q≤2×105;1≤Y≤min(R−L+1,30);X,∣Ki∣≤106,∣Bi∣≤1018。