#include<bits/stdc++.h> using namespace std; #define int long long int op; int n,q,k=100,id; inline void decode(int &l,int &r,int &k,int lstans) { lstans%=19260817; if(op){ l^=lstans;l=(l%n+n)%n+1; r^=lstans;r=(r%n+n)%n+1; if(l>r)swap(l,r); k^=lstans; k=(k%min(r-l+1,100ll))+1; } } int per[200300]; #define pii pair<int,int> #define p1(x) x.first #define p2(x) x.second int dfn[200300],tk; vector<pii>g[200300],G[200300]; int siz[200300],fa[200300],hs[200300]; int tp[200300],dep[200300],d[200300]; inline void dfs(int u){ siz[u]=1; dep[u]=dep[fa[u]]+1; for(pii e:g[u])if(p1(e)!=fa[u]){ int v=p1(e),c=p2(e); fa[v]=u; d[v]=d[u]+c; dfs(v); siz[u]+=siz[v]; if(siz[v]>siz[hs[u]])hs[u]=v; } } inline void dfs2(int u,int t){ tp[u]=t; dfn[u]=++tk; if(hs[u])dfs2(hs[u],t); for(pii e:g[u])if(p1(e)!=fa[u]&&p1(e)!=hs[u]) dfs2(p1(e),p1(e)); } inline int LCA(int u,int v){ while(tp[u]!=tp[v]){ if(dep[tp[u]]<dep[tp[v]])swap(u,v); u=fa[tp[u]]; } if(dep[u]<dep[v])return u; return v; } inline int dis(int u,int v){ if(u==0||v==0)return -1e18; return d[u]+d[v]-2*d[LCA(u,v)]; } inline bool cmp(int x,int y){ return dfn[x]<dfn[y]; } inline void bd_xt(vector<int>&A){ sort(A.begin(),A.end(),cmp); int k=A.size(); for(int i=0;i+1<k;i++) A.emplace_back(LCA(A[i],A[i+1])); vector<int>U; sort(A.begin(),A.end(),cmp); k=A.size(); for(int i=0;i<k;i++) if(U.empty()||U.back()!=A[i])U.emplace_back(A[i]); for(int x:U)G[x].clear(); int lst=0; for(int x:U){ if(lst){ int L=LCA(x,lst); int c=d[x]-d[L]; G[L].push_back({x,c}); G[x].push_back({L,c}); } lst=x; } } int p[200030]; vector<int>LF; inline bool cmpL(int x,int y){ return p[x]>p[y]; } int ls[200300],lsw[200300]; inline int dfs(int u,int f,int d){ int mx=d; ls[u]=0; lsw[u]=0; for(pii e:G[u])if(p1(e)!=f){ int v=p1(e),c=p2(e); int w=dfs(v,u,d+c); if(w>mx){ls[u]=v;mx=w;lsw[u]=c;} } if(!ls[u]&&f)LF.push_back(u); return mx; } inline void dfs2(int u,int f,int d){ if(ls[u])dfs2(ls[u],u,d+lsw[u]); else p[u]=d; for(pii e:G[u])if(p1(e)!=f&&p1(e)!=ls[u]) dfs2(p1(e),u,p2(e)); } inline void calL(int u){ LF.clear(); dfs(u,0,0); dfs2(u,0,0); sort(LF.begin(),LF.end(),cmpL); } struct node{ int x,y; vector<int>w,X; friend node operator +(const node A,const node B){ if(!A.x&&!B.x){ if(!B.X.empty()){ cerr<<B.X.size()<<" "<<B.X[0]<<endl; } assert(A.X.empty()&&B.X.empty()); return A; } vector<int>NW=A.X; for(int x:B.X)NW.emplace_back(x); bd_xt(NW); int x=0,y=0,len=-1; int w=dis(A.x,A.y); if(w>len)x=A.x,y=A.y,len=w; w=dis(A.x,B.x); if(w>len)x=A.x,y=B.x,len=w; w=dis(A.x,B.y); if(w>len)x=A.x,y=B.y,len=w; w=dis(A.y,B.x); if(w>len)x=A.y,y=B.x,len=w; w=dis(A.y,B.y); if(w>len)x=A.y,y=B.y,len=w; w=dis(B.x,B.y); if(w>len)x=B.x,y=B.y,len=w; calL(x); int k=min(100ll,(int)LF.size()); vector<int>W(k+1),X(k+1); W[0]=0,X[0]=x; for(int i=0;i<k;i++){ X[i+1]=LF[i]; W[i+1]=W[i]+p[LF[i]]; } return {x,y,W,X}; } }st[12][2010],UN; const int SIZ=100; int L[2010],R[2010]; int bel[200100]; inline pii dia(int l,int r){ int a=per[l],b=a; for(int j=l+1;j<=r;j++){ int c=per[j]; int d=dis(a,b),da=dis(a,c),db=dis(b,c); // cerr<<a<<" "<<b<<" "<<d<<" "<<da<<" "<<db<<endl; if(da>d&&da>db)b=c; else if(db>d)a=c; } assert(a!=0&&b!=0); return {a,b}; } inline vector<int> ST(int l,int r){ vector<int>A; for(int i=l;i<=r;i++)A.push_back(per[i]); return A; } int lg[2010]; inline node gt(int l,int r){ if(l>r)return UN; int p=lg[r-l+1]; // cerr<<l<<" "<<r<<" "<<p<<endl; return st[p][l]+st[p][r-(1<<p)+1]; } inline node force(int l,int r){ pii P=dia(l,r); return UN+(node){p1(P),p2(P),{},ST(l,r)}; } signed main(){ ios::sync_with_stdio(0); cin.tie(0),cout.tie(0); // int CC=clock(); // freopen("19.in","r",stdin); // freopen("d.out","w",stdout); for(int i=2;i<=2000;i++) lg[i]=lg[i>>1]+1; cin>>id>>op; cin>>n; for(int i=1;i<n;i++){ int u,v,w; cin>>u>>v>>w; g[u].push_back({v,w}); g[v].push_back({u,w}); } dfs(1); dfs2(1,1); for(int i=1;i<=n;i++) cin>>per[i]; // cout<<(n+SIZ-1)/SIZ<<endl; // return 0; for(int i=1;i<=n;i++){ bel[i]=(i+SIZ-1)/SIZ; if(!L[bel[i]])L[bel[i]]=i; R[bel[i]]=i; } for(int i=1;i<=bel[n];i++){ pii A=dia(L[i],R[i]); st[0][i].x=p1(A),st[0][i].y=p2(A); for(int j=L[i];j<=R[i];j++) st[0][i].X.push_back(per[j]); st[0][i]=st[0][i]+UN; } // return 0; for(int i=1;i<=10;i++) for(int j=1;j+(1<<i)-1<=bel[n];j++) st[i][j]=st[i-1][j]+st[i-1][j+(1<<i-1)]; cin>>q; int lst=0; while(q--){ int l,r,k; cin>>l>>r>>k; decode(l,r,k,lst); node A; if(bel[l]!=bel[r]){ // if(bel[l]+1==bel[r])cout<<"?"; A=gt(bel[l]+1,bel[r]-1); // if(bel[l]+1==bel[r])cout<<A.x<<" "<<A.y<<" "<<A.w.size()<<" "<<A.X.size()<<" "; // cerr<<"?"<<l<<" "<<R[bel[l]]<<" "<<force(l,R[bel[l]]).x<<" "<<force(l,R[bel[l]]).y<<" "<<p1(dia(l,R[bel[l]]))<<" "<<p2(dia(l,R[bel[l]]))<<"||| "; A=A+force(l,R[bel[l]]); // cerr<<"?"; A=A+force(L[bel[r]],r); // if(bel[l]+1==bel[r])cout<<A.x<<" "<<A.y<<" "<<A.w.size()<<" "<<A.X.size()<<" "; // cerr<<"!"<<endl; } else A=force(l,r); lst=A.w[min(k-1,(int)A.w.size()-1)]; cout<<lst<<"\n"; } cout.flush(); return 0; }