#include<bits/stdc++.h> using namespace std; #define ll long long int dep[300300],fa[300300][21]; vector<int>g[300400]; inline void dfs(int u){ dep[u]=dep[fa[u][0]]+1; for(int i=1;i<=20;i++) fa[u][i]=fa[fa[u][i-1]][i-1]; for(int v:g[u])if(v!=fa[u][0]){ fa[v][0]=u; dfs(v); } } int rt[300400]; struct node{ int lc,rc; ll mn,mx,tg; }T[32000000]; #define lc(x) T[x].lc #define rc(x) T[x].rc #define mn(x) T[x].mn #define mx(x) T[x].mx #define tg(x) T[x].tg inline void add(int x,ll k){ mn(x)+=k; tg(x)+=k; mx(x)+=k; } // inline void pd(int x){ // if(!tg(x))return ; // if(lc(x))add(lc(x),tg(x)); // if(rc(x))add(rc(x),tg(x)); // tg(x)=0; // } inline void upd(int x){ mn(x)=min(mn(lc(x)),mn(rc(x)))+tg(x); mx(x)=max(mx(lc(x)),mx(rc(x)))+tg(x); } inline int merge(int x,int y){ if(!x||!y)return x|y; tg(x)=tg(lc(x))+tg(rc(x)); lc(x)=merge(lc(x),lc(y)); rc(x)=merge(rc(x),rc(y)); upd(x); return x; } const ll M=998244353,IV2=(M+1)/2; inline ll S(ll l,ll r){ int a=(l+r)%M,b=(r-l+1)%M; return a*b%M*IV2%M; } const ll INF=1e18; inline ll gmn(int x,int l,int r,int L,int R,ll ex=0){ if(!x)return ex; if(L<=l&&r<=R)return mn(x)+ex; int mid=l+r>>1; ll res=INF; ex+=tg(x); if(L<=mid)res=min(res,gmn(lc(x),l,mid,L,R,ex)); if(R>mid)res=min(res,gmn(rc(x),mid+1,r,L,R,ex)); } inline ll gmx(int x,int l,int r,int L,int R,ll ex=0){ if(!x)return ex; if(L<=l&&r<=R)return mx(x)+ex; int mid=l+r>>1; ll res=-INF; ex+=tg(x); if(L<=mid)res=max(res,gmx(lc(x),l,mid,L,R,ex)); if(R>mid)res=max(res,gmx(rc(x),mid+1,r,L,R,ex)); } inline int gpre(int x,int l,int r,int R,ll lim,ll ex=0){ if(mn(x)+ex>lim)return -1; if(!x)return min(r,R); if(l==r)return l; int mid=l+r>>1; ex+=tg(x); if(R>mid){ int w=gpre(rc(x),mid+1,r,R,lim,ex); if(w==-1)return gpre(lc(x),l,mid,R,lim,ex); return w; } else return gpre(lc(x),l,mid,R,lim,ex); } int ct=0; inline void mod(int &x,int l,int r,int L,int R,int k){ if(!x)x=++ct; if(L<=l&&r<=R){ add(x,k); return ; } int mid=l+r>>1; if(L<=mid)mod(lc(x),l,mid,L,R,k); if(R>mid)mod(rc(x),mid+1,r,L,R,k); upd(x); } int ANS[300400]; vector<pair<int,int>>A[304000]; inline void calc(int rt,int t,int y){ } inline void calc(int u){ for(int v:g[u])if(v!=fa[u][0]) calc(v),rt[u]=merge(rt[u],rt[v]); } signed main(){ ios::sync_with_stdio(0); cin.tie(0);cout.tie(0); // freopen("candy.in","r",stdin); // freopen("candy.out","w",stdout); T[0]={0,0,0,0,0}; return 0; }