配点 : 500 点
問題文
长度 N 序列 给出了 A=\lparen A_{1},A_{2},\ldots,A_{N} \rparen,B=\lparen B_{1},B_{2},\ldots,B_{N}\rparen 。 对于
查询描述如下 请处理 Q 件。
查询如下 3 类型。 更新至
1 p x: B_{p} 的数值 x 。 每个都令人满意2 L R: L \leq p \leq R 添加 A_{p} 如果你写 B_{p} 。 代表第3 p: A_{p} 。
制約
- 1 \leq N \leq 5 \times 10^{5}
- 1 \leq Q \leq 5 \times 10^{5}
- 0 \leq A_{i},B_{i} \leq 10^{9}
- 1 \leq p \leq N
- 1 \leq x \leq 10^{9}
- 1 \leq L \leq R \leq N
- 所有输入均为整数
入力
输入将以以下格式从标准输入给出。
N Q
A_{1} A_{2} \ldots A_{N}
B_{1} B_{2} \ldots B_{N}
\mathrm{query}_{1}
\mathrm{query}_{2}
\vdots
\mathrm{query}_{Q}
i 个查询 \mathrm{query}_{i} 如下 3 是以下类型之一。 按顺序输出查询
1 p x
2 L R
3 p
出力
3的答案,以换行符分隔。
入力例 1
5 5 3 1 4 1 5 2 7 1 8 2 1 2 3 1 4 4 3 2 2 1 3 3 2
出力例 1
1 4
最后 它变成 A=\lparen 5,4,5,1,5 \rparen , B=\lparen 2,3,1,4,2 \rparen 。
入力例 2
2 3 1000000000 1000000000 1000000000 1000000000 2 1 2 2 1 2 3 1
出力例 2
3000000000
小心溢出。