背景

ZYH和XYH是"好"朋友
ZYH给XYH出了一道题

描述

给出N,\(A_i(1\leq i\leq N)\),\(B_i(1\leq i\leq N)\)
M个操作
A l r d 表示\(A_i\)+=d\((l\leq i\leq r)\)
B l r v 表示\(B_i\)=max(\(B_i\),v)\((l\leq i\leq r)\)
Q l r 表示询问max(\(A_i\)+\(B_i\))\((l\leq i\leq r)\)

输入

第一行两个正整数N,M
第二行N个整数\(A_i(1\leq i\leq N)\)
第三行N个整数\(B_i(1\leq i\leq N)\)
接下来M行，每行一个操作

输出

对于每个询问，输出一行一个整数为max值

样例

输入

3 6
4 8 3 
6 10 7 
A 1 2 1
B 1 2 2
B 1 3 8
B 1 2 6
B 2 3 15
Q 1 3

输出

24

范围

50% N<=3000 M<=5000
60% M<=10000
70% N<=10000 M<=30000
80% N,M<=\(5\ast 10^4\)
90% N,M<=\(10^5\)
100% N,M<=\(3\ast 10^5\) -1000<=\(A_i\),\(B_i\)<=1000 1<=l<=r<=N -10<=d<=1000 1<=v<=\(3\ast 10^7\)

限制

1s
128M