#include<bits/stdc++.h> using namespace std; #define int long long #define pii pair<int,int> #define lson (pos<<1) #define rson (pos<<1|1) #define fr first #define sc second #define mk make_pair #define x1 lylakioi #define y1 yjbakioi #define inx(u) int I=h[(u)],v=edge[I].v,w=edge[I].w;I;I=edge[I].nx,v=edge[I].v,w=edge[I].w int read(){int x=0,f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return x*f;} const int MAXN=200010,MAXM=4010,MXN=110,N=25,K=50,inf=1000000000; struct Edge{int v,nx,w;}edge[MAXN<<1];int h[MAXN],CNT;void add_side(int u,int v,int w){ // cout<<" "<<u<<" "<<v<<" "<<w<<endl; edge[++CNT]={v,h[u],w};h[u]=CNT;edge[++CNT]={u,h[v],w};h[v]=CNT;} void init(int x){for(int i=1;i<=x;i++)h[i]=0;CNT=1;} int id,op,n,q; void decode(int &l,int &r,int &k,int lstans,int testop){lstans%=19260817;if(testop){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 a[MAXN],cnt,ans,dfn[MAXN],dep[MAXN],sd[MAXN],f[MAXN][N+5]; void dfs(int u,int lst){ dfn[u]=++cnt,f[u][0]=lst; for(inx(u))if(v!=lst){ dep[v]=dep[u]+w; sd[v]=sd[u]+1; dfs(v,u); } } int lca(int x,int y){ if(sd[x]<sd[y])swap(x,y); for(int i=N;~i;i--)if(sd[f[x][i]]>=sd[y])x=f[x][i]; if(x==y)return x; for(int i=N;~i;i--)if(f[x][i]!=f[y][i])x=f[x][i],y=f[y][i]; return f[x][0]; } bool cmp(int x,int y){return dfn[x]<dfn[y];} int len[MAXN],son[MAXN],tot; pii ln[MAXN]; void dfs1(int u,int lst){ len[u]=son[u]=0; for(inx(u))if(v!=lst){ dfs1(v,u); if(len[v]+w>len[u])len[u]=len[v]+w,son[u]=v; } } void dfs2(int u,int lst,int ty){ ln[ty].sc=u; if(son[u])dfs2(son[u],u,ty); for(inx(u))if(v!=son[u]&&v!=lst){ ln[++tot]=mk(len[v]+w,v); dfs2(v,u,tot); } } int dis(int x,int y){return -dep[lca(x,y)]*2+dep[x]+dep[y];} pair<int,pii> mrge(int x1,int x2,int y1,int y2,int len1,int len2){ if(!x1||!x2)return mk(len2,mk(y1,y2)); if(!y1||!y2)return mk(len1,mk(x1,x2)); int x1y1=dis(x1,y1),x2y1=dis(x2,y1),x1y2=dis(x1,y2),x2y2=dis(x2,y2),tmp=max(max(x1y1,x2y1),max(x1y2,x2y2)); if(len1>tmp)return mk(len1,mk(x1,x2)); if(len2>tmp)return mk(len2,mk(y1,y2)); if(tmp==x1y1)return mk(tmp,mk(x1,y1)); if(tmp==x2y1)return mk(tmp,mk(x2,y1)); if(tmp==x1y2)return mk(tmp,mk(x1,y2)); if(tmp==x2y2)return mk(tmp,mk(x2,y2)); } struct node{ int k,x,y,le; pii p[MXN]; void inst(int d){ p[++k]=mk(0,d); pair<int,pii> tmp=mrge(x,y,d,d,le,0); x=tmp.sc.fr,y=tmp.sc.sc,le=tmp.fr; } node operator*(const node&G)const{ node res; cnt=0; for(int i=1;i<=k;i++)a[++cnt]=p[i].sc; for(int i=1;i<=G.k;i++)a[++cnt]=G.p[i].sc; sort(a+1,a+cnt+1,cmp); for(int i=cnt;i>1;i--){ a[++cnt]=lca(a[i],a[i-1]); } sort(a+1,a+cnt+1,cmp); cnt=unique(a+1,a+cnt+1)-a-1; for(int i=2;i<=cnt;i++){ int L=lca(a[i],a[i-1]); add_side(a[i],L,dep[a[i]]-dep[L]); } pair<int,pii> tmp=mrge(x,y,G.x,G.y,le,G.le); res.x=tmp.sc.fr,res.y=tmp.sc.sc,res.le=tmp.fr; dfs1(res.x,res.x); tot=0; ln[++tot]=mk(len[res.x],res.x); dfs2(res.x,res.x,1); sort(ln+1,ln+tot+1,greater<pii>()); res.k=min(K,min(tot+1,k+G.k)); res.p[1]=mk(0,res.x); for(int i=2;i<=res.k;i++)res.p[i]=ln[i-1]; for(int i=1;i<=cnt;i++)h[a[i]]=0;CNT=1; return res; } void build(){ cnt=0; for(int i=1;i<=k;i++)a[++cnt]=p[i].sc; sort(a+1,a+cnt+1,cmp); for(int i=2;i<=k;i++){ a[++cnt]=lca(a[i],a[i-1]); } sort(a+1,a+cnt+1,cmp); cnt=unique(a+1,a+cnt+1)-a-1; for(int i=cnt;i>1;i--){ int L=lca(a[i],a[i-1]); add_side(a[i],L,dep[a[i]]-dep[L]); } dfs1(x,x); tot=0; ln[++tot]=mk(len[x],x); dfs2(x,x,1); sort(ln+1,ln+tot+1,greater<pii>()); k=min(min(tot+1,K),k); p[1]=mk(0,x); for(int i=2;i<=k;i++)p[i]=ln[i-1]; for(int i=1;i<=cnt;i++)h[a[i]]=0;CNT=1; } void clear(){ x=y=le=k=0; } void prt(){ cout<<k<<" "<<x<<" "<<y<<" "<<le<<endl; for(int i=1;i<=k;i++)cout<<p[i].fr<<"_"<<p[i].sc<<" ";cout<<endl; } int qry(int d){ // prt(); int res=0; if(d==1)return 0; for(int i=1;i<=min(k,d);i++)res+=p[i].fr; return res; } }P,Q; int bel[MAXN]; struct STB{ node f[N][MAXM]; int m,lg2[MAXN]; void build(){ for(int i=1;i<=n;i++)lg2[i]=i>1?lg2[i>>1]+1:0; for(int i=1;i<=n;i+=K){ m++; f[0][m].clear(); for(int j=1;j<=K&&i+j-1<=n;j++)f[0][m].inst(i+j-1),bel[i+j-1]=m; f[0][m].build(); } bel[n+1]=m+1; for(int i=1;i<=N;i++) for(int j=1;j+(1<<i)-1<=m;j++) f[i][j]=f[i-1][j]*f[i-1][j+(1<<i-1)]; } node qry(int l,int r){ int g=lg2[r-l+1]; return f[g][l]*f[g][r-(1<<g)+1]; } }T; struct side{ int u,v,w; }s[MAXN]; void slv(){ id=read(),op=read(),n=read(); for(int i=1;i<n;i++){ int u=read(),v=read(),w=read(); s[i]={u,v,w}; } for(int i=1;i<=n;i++)a[read()]=i; for(int i=1;i<n;i++)add_side(a[s[i].u],a[s[i].v],s[i].w); dfs(1,1),init(n); for(int i=1;i<=N;i++)for(int j=1;j<=n;j++)f[j][i]=f[f[j][i-1]][i-1]; T.build(); q=read(); while(q--){ int l=read(),r=read(),k=read(); decode(l,r,k,ans,op); P.clear(),Q.clear(); if(bel[l]==bel[r]){ for(int i=l;i<=r;i++)P.inst(i); P.build(); ans=P.qry(k); } else{ for(int i=l;bel[i]==bel[l];i++)P.inst(i); for(int i=r;bel[i]==bel[r];i--)Q.inst(i); if(bel[l]+1>bel[r]-1)ans=(P*Q).qry(k); else ans=(P*Q*T.qry(bel[l]+1,bel[r]-1)).qry(k); } printf("%lld\n",ans); } } signed main(){ slv(); return 0; }