背景

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