#include using namespace std; namespace io { constexpr int S1=1<<20; char buf1[S1],*l1,*r1; inline char getc() { return ((l1==r1&&(r1=(l1=buf1)+fread(buf1,1,S1,stdin)),l1!=r1)?*l1++:EOF); } templateinline T read() { T x=0,y=1; char c=getc(); for(;c<'0'||c>'9';c=getc()) if(c=='-') y=-1; for(;c>='0'&&c<='9';c=getc()) x=c-'0'+x*10; return x*y; } constexpr int S2=1<<20; char buf2[S2],*l2=buf2; inline void putc(char c) { l2==buf2+S2&&(fwrite(buf2,1,S2,stdout),l2=buf2),*l2++=c; } int st[42]; templateinline void write(T x,char end='\n') { if(x<0) putc('-'),x=-x; int tp=0; do st[++tp]=x%10; while(x/=10); while(tp) putc(st[tp--]+'0'); if(end) putc(end); } inline void ps(const char*a,char end='\n') { for(const char*p=a;*p;p++) putc(*p); if(end) putc(end); } struct end { ~end() { fwrite(buf2,1,l2-buf2,stdout); } }ender; } using io::getc; using io::read; using io::putc; using io::write; using io::ps; constexpr int MN=500005; int n,q,m,d,fa[MN],dep[MN],siz[MN],hson[MN],dfn[MN],cnt,st[20][MN],lc[20][MN],md[20][MN],ans[MN],c[MN]; vectorg[MN],v[MN]; mapmp[MN]; struct node { int x,y,z,v; }a[MN*2],b[MN*2]; struct BIT { int a[MN]; void clr(int x) { for(;x<=n;x+=x&(-x)) a[x]=0; } void add(int x,int y) { for(;x<=n;x+=x&(-x)) a[x]=max(a[x],y); } int ask(int x) { int r=0; for(;x;x&=x-1) r=max(r,a[x]); return r; } }T; inline int ck(int x,int y) { return dep[x]siz[hson[x]]) hson[x]=y; } } inline int LCA(int x,int y) { if(x==y) return x; x=dfn[x],y=dfn[y]; if(x>y) swap(x,y); x++; int g=__lg(y-x+1); return fa[ck(st[g][x],st[g][y-(1<second==l-1) l=pit->first,mp[i].erase(pit),ch=1; } if(it!=mp[i].end()&&it->first==r+1) r=it->second,mp[i].erase(it),ch=1; mp[i][l]=r; if(ch) a[++m]={n-l+1,r,n-(r-l+1)+1,d}; } void solve(int l,int r) { if(l==r) return; int mid=(l+r)>>1; solve(l,mid),solve(mid+1,r); int i,j,cnt=0; for(i=l,j=mid+1;j<=r;j++) { for(;i<=mid&&a[i].y<=a[j].y;i++) { b[cnt++]=a[i]; if(a[i].v>0) T.add(a[i].z,a[i].v); } b[cnt++]=a[j]; if(a[j].v<0) ans[-a[j].v]=max(ans[-a[j].v],T.ask(a[j].z)); } for(j=l;j0) T.clr(a[j].z); for(;i<=mid;i++) b[cnt++]=a[i]; for(int i=0;i