U138304 疯狂的俏敏

俏敏是某实验中学的体育老师

俏敏上体育课的时候，采用了一种新型的体育运动方法，他先让所有学生站成一排，然后进行如下几种操作 1. 选择一个区间的人，让他们往同一个方向动起来，若已经动起来了，则将移动方向改为俏敏所指定的方向 1. 选择一个区间的人，让他们蹲下或站直，即改变他们的高度 1. 选择一个区间，询问该区间内的学生中最高的高度是多少 已知学生的移动速度为$1$个单位长度每秒，每个学生初始都处于静止状态，总人数$n$，俏敏发出指令数$m$，和每条指令的具体信息，现请你回答俏敏的所有询问的结果

输入第一行两个整数$n$和$m$，代表学生总人数和俏敏发出的指令总数 第二行$n$个整数，代表每个学生初始所在的位置 第三行$n$个整数，代表每个学生的初始高度 下$m$行每行先是两个整数$id$和$t$，代表操作种类和发生时间，保证发生时间已经按升序排列 1. $id=1$时，输入三个整数$x$，$y$，$a$，代表使得位置在$[x,y]$内的学生方向改为$a$（1为向正方向，-1为向负方向，0为使其不动） 1. $id=2$时，输入三个整数$x$，$y$，$b$，代表使得位置在$[x,y]$内的学生高度增加$b$，$b$可能为负数 1. $id=3$时，输入两个整数$x$，$y$，代表查询位置在$[x,y]$之间的学生最高的高度

对于每一个$id=3$的情况，输出一行一个整数，代表查询结果

对于$40\%$的数据：$n,m\le 100$ 对于$100\%$的数据：$n,m\le 10^5$ 保证所有学生高度与位置在$1\to 100000$之间 保证不会出现学生试图走向$0$或$100001$的位置