#include using namespace std; const int N=5e5+5; char buf[1<<23],*p1=buf,*p2=buf; #define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<23,stdin),p1==p2)?EOF:*p1++) template void read(rd &x){ char c=getchar(); for(;c<48||c>57;c=getchar()); for(x=0;c>47&&c<58;c=getchar())x=(x<<1)+(x<<3)+(c^48); } int n,m,dp[N],fa[N],tp[N],son[N],sz[N],lp[N],rp[N],ans[N]; vectore[N],g[N],lk[N]; bool vis[N]; struct node{ int l,r,w; }q[N]; vectorva[N]; set >s[N]; #define L k<<1 #define R k<<1|1 struct seg{ int tr[N<<2]; void upd(int k,int l,int r,int x,int v){ tr[k]=max(tr[k],v); if(l==r)return vis[l]=true,void(); int mid=l+r>>1; if(x<=mid)upd(L,l,mid,x,v); else upd(R,mid+1,r,x,v); } int query(int k,int l,int r,int x,int y){ if(tr[k]>1,o=-1; if(x>mid)o=query(R,mid+1,r,x,y); if(o==-1)o=query(L,l,mid,x,y); return o; } }T; struct seg2{ int tr[N<<2],tg[N<<2]; void pushtg(int k,int v){ tg[k]=max(tg[k],v); tr[k]=max(tr[k],v); } void pushdown(int k){ if(tg[k]){ pushtg(L,tg[k]); pushtg(R,tg[k]); tg[k]=0; } } void upd(int k,int l,int r,int x,int y,int v){ if(x<=l&&r<=y)return pushtg(k,v); int mid=l+r>>1; pushdown(k); if(x<=mid)upd(L,l,mid,x,y,v); if(y>mid)upd(R,mid+1,r,x,y,v); tr[k]=max(tr[L],tr[R]); } int query(int k,int l,int r,int x,int y){ if(x<=l&&r<=y)return tr[k]; int mid=l+r>>1,res=0; pushdown(k); if(x<=mid)res=max(res,query(L,l,mid,x,y)); if(y>mid)res=max(res,query(R,mid+1,r,x,y)); return res; } }T2; void dfs1(int x){ sz[x]=1; for(auto v:e[x])if(!sz[v]){ fa[v]=x,dp[v]=dp[x]+1; dfs1(v); sz[x]+=sz[v]; if(sz[v]>sz[son[x]])son[x]=v; } } void dfs2(int x,int t){ tp[x]=t; if(son[x])dfs2(son[x],t); for(auto v:e[x])if(!tp[v])dfs2(v,v); } int lca(int x,int y){ for(int fx=tp[x],fy=tp[y];fx!=fy;x=fa[fx],fx=tp[x])if(dp[fx]second; if(ql>qr)ans[v]=max(ans[v],T2.query(1,1,n,qr,ql)); } } for(int i=1;i<=m;++i)printf("%d\n",ans[i]); return 0; }