#include <bits/stdc++.h>
#define int long long
using namespace std;
constexpr int MAXN = 3e5 + 5,inf = 1e17;
int a[MAXN],b[MAXN],n,m,opt,l,r,x;
struct Info
{
int mx,smx,mxCnt,laz1,laz2;
void init()
{laz1 = laz2 = 0;}
};
struct Rukkhadevata
{
Info tag[2];
int ans;
}tree[MAXN << 2];
inline void pushup(int rt,bool t)
{
Info& ls = tree[rt << 1].tag[t],&rs = tree[rt << 1 | 1].tag[t];
tree[rt].tag[t].mx = max(ls.mx,rs.mx);
if(ls.mx == rs.mx)
{
tree[rt].tag[t].smx = max(ls.smx,rs.smx);
tree[rt].tag[t].mxCnt = ls.mxCnt + rs.mxCnt;
}
else if(ls.mx > rs.mx)
{
tree[rt].tag[t].smx = max(ls.smx,rs.mx);
tree[rt].tag[t].mxCnt = ls.mxCnt;
}
else
{
tree[rt].tag[t].smx = max(ls.mx,rs.smx);
tree[rt].tag[t].mxCnt = rs.mxCnt;
}
}
inline void pushup(int rt)
{
pushup(rt,0),pushup(rt,1);
tree[rt].ans = max(tree[rt << 1].ans,tree[rt << 1 | 1].ans);
}
inline void update(int rt,int laz1,int laz2,bool t)
{
tree[rt].tag[t].mx += laz1,tree[rt].ans += laz1;
if(tree[rt].tag[t].smx != -inf)
tree[rt].tag[t].smx += laz2;
tree[rt].tag[t].laz1 += laz1,tree[rt].tag[t].laz2 += laz2;
}
inline void pushdown(int rt,bool t)
{
Info &ls = tree[rt << 1].tag[t],&rs = tree[rt << 1 | 1].tag[t];
int Max = max(ls.mx,rs.mx);
if(ls.mx == Max)
update(rt << 1,tree[rt].tag[t].laz1,tree[rt].tag[t].laz2,t);
else
update(rt << 1,tree[rt].tag[t].laz2,tree[rt].tag[t].laz2,t);
if(rs.mx == Max)
update(rt << 1,tree[rt].tag[t].laz1,tree[rt].tag[t].laz2,t);
else
update(rt << 1 | 1,tree[rt].tag[t].laz1,tree[rt].tag[t].laz2,t);
tree[rt].tag[t].init();
}
inline void pushdown(int rt)
{
pushdown(rt,0),pushdown(rt,1);
}
inline void build(int l,int r,int rt)
{
tree[rt].tag[0].init(),tree[rt].tag[1].init();
if(l == r)
{
tree[rt].ans = a[l] + b[l];
tree[rt].tag[0].mx = a[l],tree[rt].tag[1].mx = b[l];
tree[rt].tag[0].smx = tree[rt].tag[1].smx = -inf;
tree[rt].tag[0].mxCnt = tree[rt].tag[1].mxCnt = 1;
return ;
}
int mid = (l + r) >> 1;
build(l,mid,rt << 1);
build(mid + 1,r,rt << 1 | 1);
pushup(rt);
}
inline void modifyMin(int rt,int l,int r,int L,int R,int val,bool t)
{
if(tree[rt].tag[t].mx <= val)
return ;
if(L <= l && R >= r && tree[rt].tag[t].smx < val)
return update(rt,val - tree[rt].tag[t].mx,0,t);
pushdown(rt);
int mid = (l + r) >> 1;
if(L <= mid)
modifyMin(rt << 1,l,mid,L,R,val,t);
if(R > mid)
modifyMin(rt << 1,mid + 1,r,L,R,val,t);
pushup(rt);
}
inline void modifySum(int rt,int l,int r,int L,int R,int val,bool t)
{
if(L <= l && R >= r)
return update(rt,val,val,t);
pushdown(rt);
int mid = (l + r) >> 1;
if(L <= mid)
modifySum(rt << 1,l,mid,L,R,val,t);
if(R > mid)
modifySum(rt << 1 | 1,mid + 1,r,L,R,val,t);
pushup(rt);
}
inline int query(int rt,int l,int r,int L,int R)
{
if(L <= l && R >= r)
return tree[rt].ans;
pushdown(rt);
int mid = (l + r) >> 1,res = -inf;
if(L <= mid)
res = max(res,query(rt << 1,l,mid,L,R));
if(R > mid)
res = max(res,query(rt << 1 | 1,mid + 1,r,L,R));
return res;
}
signed main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin >> n >> m;
for(int i = 1;i <= n;i++)
cin >> a[i];
for(int i = 1;i <= n;i++)
cin >> b[i];
for(int i = 1;i <= m;i++)
{
cin >> opt >> l >> r;
if(opt == 1 || opt == 2)
{
cin >> x;
modifyMin(1,1,n,l,r,x,opt - 1);
}
if(opt == 3 || opt == 4)
{
cin >> x;
modifySum(1,1,n,l,r,x,opt - 3);
}
if(opt == 5)
cout << query(1,1,n,l,r) << "\n";
}
}
RE + WA