#include using namespace std; using ll=long long; using pi=pair; #define fi first #define se second bool ST; const int N=5e5+5,B=1000; int n,m,nd,C,dep[N],rt[N],L[N],R[N],V[N],q[N],ql[N],qr[N],ans[N],Mx[N],st[N],b[N],suf[N],vv[N],id[N],id1[N],a0[N]; vectore[N]; vectorc[N]; void add(int l,int r){c[nd].push_back({r,r-l+1});} struct sgt{ int sz; struct tree{int l,r,s,ls,rs;}t[N*20]; void Add(int p,int lp,int rp,int l,int r) { if(t[p].s==r-l+1) { if(lp||rp)add(l-lp,r+rp); }else { if(t[p].ls&&lp)add(l-lp,l+t[p].ls-1); if(t[p].rs&&rp)add(r-t[p].rs+1,r+rp); } } void upd(int p,int l,int r) { int mid=l+r>>1;t[p].s=t[t[p].l].s+t[t[p].r].s; t[p].ls=(t[t[p].l].s==mid-l+1?mid-l+1+t[t[p].r].ls:t[t[p].l].ls); t[p].rs=(t[t[p].r].s==r-mid?r-mid+t[t[p].l].rs:t[t[p].r].rs); } void ins(int&p,int x,int l=1,int r=n) { p=++sz,t[p].s=1,t[p].ls=(x==l),t[p].rs=(x==r); if(l==r)return;int mid=l+r>>1; (x<=mid?ins(t[p].l,x,l,mid):ins(t[p].r,x,mid+1,r)); } int merge(int p,int q,int l=1,int r=n,int lp=0,int rp=0,int lq=0,int rq=0) { if(!q)return Add(p,lq,rq,l,r),p; if(!p)return Add(q,lp,rp,l,r),q; int mid=l+r>>1; t[p].l=merge(t[p].l,t[q].l,l,mid,lp,(t[t[p].r].s==r-mid?rp+r-mid:t[t[p].r].ls),lq,(t[t[q].r].s==r-mid?rq+r-mid:t[t[q].r].ls)); t[p].r=merge(t[p].r,t[q].r,mid+1,r,(t[t[p].l].s==mid-l+1?lp+mid-l+1:t[t[p].l].rs),rp,(t[t[q].l].s==mid-l+1?lq+mid-l+1:t[t[q].l].rs),rq); return upd(p,l,r),p; } }T; void dfs(int x,int p) { T.ins(rt[x],x),dep[x]=dep[p]+1,nd=dep[x],add(x,x); for(int y:e[x])if(y!=p)dfs(y,x),nd=dep[x],rt[x]=T.merge(rt[x],rt[y]); } void Sort(int*a,int&m,int l,int r) { for(int i=l;i<=r;i++)for(pi j:c[i])Mx[j.fi]=max(Mx[j.fi],j.se),m++; if(m>n) { for(int i=l;i<=r;i++)for(pi j:c[i])vv[j.fi]=1; m=0;for(int i=1;i<=n;i++)if(vv[i])vv[i]=0,a[++m]=i; return; }m=0; for(int i=l;i<=r;i++)for(pi j:c[i])a[++m]=j.fi; if(m<=1000)sort(a+1,a+m+1); else { for(int i=1;i<=m;i++)a0[i]=a[i],id[i]=i; for(int o=0;o<2;o++) { fill(vv,vv+B+1,0); for(int i=1;i<=m;i++)vv[a[i]%B]++,id1[i]=id[i]; for(int i=1;irr)return; if(l==r){for(int i=ll;i<=rr;i++)ans[q[i]]=l;return;} int mid=l+r>>1,tl=0,tr=0,num=0,top=0,j=ll; Sort(b,num,mid+1,r); auto qry=[&](int id,int x) { int p=lower_bound(st+1,st+top+1,L[x]+V[x]-1)-st; if(suf[id]<=R[x]-V[x]+1||(p!=top+1&&Mx[st[p]]>=V[x]))qr[++tr]=x;else ql[++tl]=x; }; suf[num+1]=n+1; for(int i=num;i;i--)suf[i]=min(suf[i+1],b[i]-Mx[b[i]]+1); for(int i=1;i<=num;i++) { while(j<=rr&&R[q[j]]Mx[st[top]])top--; st[++top]=b[i]; } while(j<=rr)qry(num+1,q[j++]); for(int i=1;i<=num;i++)Mx[b[i]]=0; for(int i=1;i<=tl;i++)q[ll+i-1]=ql[i]; for(int i=1;i<=tr;i++)q[ll+tl+i-1]=qr[i]; slv(ll,ll+tl-1,l,mid),slv(ll+tl,rr,mid+1,r); } bool ED; int main() { freopen("query.in","r",stdin); freopen("query.out","w",stdout); ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); cerr<<"Memory: "<<(&ST-&ED)/1024.0/1024.0<<" MB\n"; cin>>n; for(int i=1,x,y;i>x>>y,e[x].push_back(y),e[y].push_back(x); cin>>m; for(int i=1,l,r,k;i<=m;i++)cin>>L[i]>>R[i]>>V[i],q[i]=i; sort(q+1,q+m+1,[&](int x,int y){return R[x]