毕业以后，FLself拿着SSSSSSP加入了卓动科技，他以自己多年前玩过的游戏为基础开发出了一款新的游戏，这个游戏是这样的：

一共有$n$个敌人，第$i$个敌人有$a_i$点战斗力，同时还有$b_i$点能源。主角可以干掉一个拥有$a_i$战斗力的敌人，当且仅当$x\geq a_i$，战胜一个敌人之后该敌人会消失，且主角的战斗力会增加为$b_i+x$。接下来游戏会给出$m$次的询问或者修改操作：若为询问操作，则询问打败战斗力位于$[L,R]$的全部敌人的最小初始战斗力(可以以任意顺序挑战)，若为修改操作，则修改第$i$个敌人的$a_i$和$b_i$。

如果你能在$2\times 666^{e^{i\pi}+1}$秒内解决该问题，那么则视为你挑战成功。另一位专业第一的大佬wwj是这个游戏的忠实粉丝，然而他又菜又爱玩，实在无法通关，只好向你求助。

输入第一行两个整数$n(2\leq n \leq 10^5)$和$m(1\leq m \leq 10^5)$。

输入第二行共$n$个整数，第$i$个整数为$a_i\ (1\leq a_i\leq 10^{14})$。

输入第三行共$n$个整数，第$i$个整数为$b_i\ (1\leq b_i\leq 10^{14})$。

接下来一共$m$行，每一行的第一个整数为$op(op\in {1，2})$。

若$op=1$，则表示这是一个修改操作，后跟三个整数$x(1\leq x\leq n),a'(1\leq a' \leq 10^{14}),b'(1\leq b' \leq 10^{14})$，表示将$a_x$修改为$a'$，$b_x$修改为$b'$。

若$op=2$，则表示这是一个询问操作，后跟两个整数$L,R(1\leq L \leq R \leq 10^{14})$，表示询问打败战斗力位于$[L,R]$的敌人的所需的最小初始战斗力。

数据时刻保证 $n\leq \sum_{i=1}^n ai,\ \sum{i=1}^n b_i \leq 10^{18}$。

对于每一个询问操作，依次输出一行一个整数，第$i$行的整数表示第$i$个询问中，打败战斗力位于$[L,R]$的敌人的所需的最小初始战斗力，若没有战斗力位于$[L,R]$的敌人，则输出$0$。