#include<bits/stdc++.h> #define up(i,l,r) for(int i=(l);i<=(r);++i) #define down(i,l,r) for(int i=(l);i>=(r);--i) #define pi pair<int,int> #define p1 first #define p2 second #define p_b push_back #define m_p make_pair typedef long long ll; typedef unsigned long long ull; using namespace std; const int maxn=2e5+10; inline ll read(){ ll x=0;short t=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')t=-1;ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*t; } int n,op,P[maxn],dfn[maxn],siz[maxn],ct;ll lst; vector<pi>v[maxn]; //int fa[maxn][20],dep[maxn]; int dep[maxn],fa[maxn],Top[maxn],Son[maxn]; ll dis[maxn]; void dfs(int u){ dep[u]=dep[fa[u]]+1,dfn[u]=++ct,siz[u]=1; for(auto it:v[u]){ int x=it.p1,w=it.p2; if(!(x^fa[u]))continue; fa[x]=u;dis[x]=dis[u]+w;dfs(x); siz[u]+=siz[x]; if(siz[x]>siz[Son[u]])Son[u]=x; } } void dfs2(int u,int tp){ Top[u]=tp; for(auto it:v[u])if(it.p1!=fa[u]){ if(it.p1==Son[u])dfs2(Son[u],tp); else dfs2(it.p1,it.p1); } } int lca(int x,int y){ while(Top[x]!=Top[y]){ if(dep[Top[x]]>=dep[Top[y]])x=fa[Top[x]]; else y=fa[Top[y]]; }if(dep[x]>dep[y])return y; return x; } ll g(int x,int y){ return dis[x]+dis[y]-2*dis[lca(x,y)]; } void dec(int &l,int &r,int &k){ l=read(),r=read(),k=read(); if(op){ lst%=19260817; l^=lst,r^=lst;l=(l%n+n)%n+1;r=(r%n+n)%n+1; if(l>r)swap(l,r); k^=lst;k=k%min(r-l+1,100)+1; } } vector<pair<int,ll> >vec[maxn]; int en[maxn],son[maxn],top[maxn]; ll mxd[maxn],W[maxn]; void DFS(int u,int ff){ if(!ff)W[u]=0; son[u]=0,mxd[u]=0; for(auto it:vec[u]){ int x=it.p1;ll w=it.p2; if(x==ff)continue; W[it.p1]=w; DFS(it.p1,u);w+=mxd[it.p1]; if(w>mxd[u])mxd[u]=w,son[u]=it.p1; } } void DFS2(int u,int tp,int ff){ en[tp]=u;top[u]=tp; for(auto it:vec[u]){ int x=it.p1; if(x==ff)continue; if(x==son[u])DFS2(x,tp,u); else DFS2(x,x,u); } } struct nd { int x,y;ll w; vector<int>S; nd(){} }; void UQ(vector<int>&A){ //for(int x:A)cout<<x<<" ";cout<<endl; vector<int>B;int lst=-1; for(int x:A)if(x!=lst)lst=x,B.p_b(x); A.swap(B); //for(int x:A)cout<<x<<" ";cout<<endl; } void lk(int a,int b,ll w){ vec[a].p_b(m_p(b,w)); vec[b].p_b(m_p(a,w)); } nd operator+(nd a,nd b){ //cout<<"MERGE"<<endl; //cout<<a.x<<" ";for(int x:a.S)cout<<x<<" ";cout<<endl; //cout<<b.x<<" ";for(int x:b.S)cout<<x<<" ";cout<<endl; nd c; if(a.w<b.w)c=b;else c=a;c.S.clear(); if(dis[a.x]+dis[b.x]>c.w){ ll w=g(a.x,b.x); if(w>c.w)c.w=w,c.x=a.x,c.y=b.x; } if(dis[a.x]+dis[b.y]>c.w){ ll w=g(a.x,b.y); if(w>c.w)c.w=w,c.x=a.x,c.y=b.y; } if(dis[a.y]+dis[b.x]>c.w){ ll w=g(a.y,b.x); if(w>c.w)c.w=w,c.x=a.y,c.y=b.x; } if(dis[a.y]+dis[b.y]>c.w){ ll w=g(a.y,b.y); if(w>c.w)c.w=w,c.x=a.y,c.y=b.y; } vector<int>T;T.p_b(a.x),T.p_b(b.x); for(int x:a.S)T.p_b(x);for(int x:b.S)T.p_b(x); auto cmp=[](int x,int y){ return dfn[x]<dfn[y]; }; sort(T.begin(),T.end(),cmp); UQ(T); vector<int>A;int sz=T.size(); up(i,0,sz-2)A.p_b(lca(T[i],T[i+1])); for(int x:T)A.p_b(x);T.swap(A); //cout<<"!! "<<endl; //for(int x:T)cout<<x<<" ";cout<<endl; sort(T.begin(),T.end(),cmp); UQ(T); vector<pair<pi,ll> >G;sz=T.size(); up(i,0,sz-2){ int u=lca(T[i],T[i+1]),x=T[i+1]; G.p_b(m_p(m_p(u,x),g(u,x))); }for(auto it:G)vec[it.p1.p1].clear(),vec[it.p1.p2].clear(); for(auto it:G)/*cout<<"EDGE "<<it.p1.p1<<" "<<it.p1.p2<<endl,*/lk(it.p1.p1,it.p1.p2,it.p2); DFS(c.x,0);DFS2(c.x,c.x,0); auto cmp2=[](int x,int y){ return mxd[top[x]]+W[top[x]]>mxd[top[y]]+W[top[y]]; };A.clear(); //if(a.x==8&&a.y==8&&b.x==6&&b.y==6)cout<<"! "<<top[6]<<" "<<en[8]<<endl; for(int x:T)if(en[top[x]]==x)A.p_b(x); sort(A.begin(),A.end(),cmp2);UQ(A); T.clear();for(int x:A)if(x!=c.x)T.p_b(x);A.swap(T); sz=min((int)A.size(),100); up(i,0,sz-1)c.S.p_b(A[i]); //cout<<"now"<<endl; //cout<<c.x<<" ";for(int x:c.S)cout<<x<<" ";cout<<endl; return c; } int bel[maxn],len; struct ZJ { int x,y;ll w; }; ZJ operator+(ZJ a,ZJ b){ ZJ c; if(a.w<b.w)c=b;else c=a; if(dis[a.x]+dis[b.x]>c.w){ ll w=g(a.x,b.x); if(w>c.w)c.w=w,c.x=a.x,c.y=b.x; } if(dis[a.x]+dis[b.y]>c.w){ ll w=g(a.x,b.y); if(w>c.w)c.w=w,c.x=a.x,c.y=b.y; } if(dis[a.y]+dis[b.x]>c.w){ ll w=g(a.y,b.x); if(w>c.w)c.w=w,c.x=a.y,c.y=b.x; } if(dis[a.y]+dis[b.y]>c.w){ ll w=g(a.y,b.y); if(w>c.w)c.w=w,c.x=a.y,c.y=b.y; }return c; } nd calc(int l,int r){ nd c; vector<int>T; up(i,l,r)T.p_b(P[i]); auto cmp=[](int x,int y){ return dfn[x]<dfn[y]; }; sort(T.begin(),T.end(),cmp); UQ(T); vector<int>A;int sz=T.size(); up(i,0,sz-2)A.p_b(lca(T[i],T[i+1])); for(int x:T)A.p_b(x);T.swap(A); //cout<<"!! "<<endl; //for(int x:T)cout<<x<<" ";cout<<endl; sort(T.begin(),T.end(),cmp); UQ(T); vector<pair<pi,ll> >G;sz=T.size(); up(i,0,sz-2){ int u=lca(T[i],T[i+1]),x=T[i+1]; G.p_b(m_p(m_p(u,x),g(u,x))); }for(auto it:G)vec[it.p1.p1].clear(),vec[it.p1.p2].clear(); for(auto it:G)/*cout<<"EDGE "<<it.p1.p1<<" "<<it.p1.p2<<endl,*/lk(it.p1.p1,it.p1.p2,it.p2); ZJ f;f.x=f.y=P[l],f.w=0; up(i,l+1,r){ ZJ w;w.x=w.y=P[i],w.w=0; f=f+w; }c.x=f.x,c.y=f.y,c.w=f.w; DFS(c.x,0);DFS2(c.x,c.x,0); auto cmp2=[](int x,int y){ return mxd[top[x]]+W[top[x]]>mxd[top[y]]+W[top[y]]; };A.clear(); //if(a.x==8&&a.y==8&&b.x==6&&b.y==6)cout<<"! "<<top[6]<<" "<<en[8]<<endl; for(int x:T)if(en[top[x]]==x)A.p_b(x); sort(A.begin(),A.end(),cmp2);UQ(A); T.clear();for(int x:A)if(x!=c.x)T.p_b(x);A.swap(T); sz=min((int)A.size(),100); up(i,0,sz-1)c.S.p_b(A[i]); //cout<<"now"<<endl; //cout<<c.x<<" ";for(int x:c.S)cout<<x<<" ";cout<<endl; return c; } struct ST { int Log_2[maxn]; nd T[maxn/100+5][11]; void init(){ up(i,2,2000)Log_2[i]=Log_2[i>>1]+1; int len=100; up(i,1,bel[n]){ int l=(i-1)*len+1,r=min(i*len,n); T[i][0]=calc(l,r); } int B=bel[n]; up(i,1,Log_2[B])up(j,1,B-(1<<i)+1)T[j][i]=T[j][i-1]+T[j+(1<<i-1)][i-1]; }nd qry(int l,int r){ int k=Log_2[r-l+1]; return T[l][k]+T[r-(1<<k)+1][k]; } }st; struct DS { void bd(){ int len=100; up(i,1,n)bel[i]=(i-1)/len+1; st.init(); }nd qry(int l,int r){ if(bel[l]==bel[r])return calc(l,r); nd w=qry(l,bel[l]*100)+qry((bel[r]-1)*100+1,r); if(bel[l]+1<=bel[r]-1){ //w=w+st.qry(bel[l]+1,bel[r]-1); w=w+calc(bel[l]*100+1,(bel[r]-1)*100); } return w; } }ds; ll qry(int l,int r,int k){ nd w=ds.qry(l,r); //nd w=calc(l,r); //for(int x:w.S)cout<<x<<" ";cout<<endl; //cout<<"? "<<w.x<<endl; vector<int>A;A.p_b(w.x); k--;k=min(k,(int)w.S.size());up(i,0,k-1)A.p_b(w.S[i]);k=A.size(); auto cmp=[](int x,int y){ return dfn[x]<dfn[y]; }; sort(A.begin(),A.end(),cmp); ll all=0;for(int x:A)all+=dis[x]; up(i,0,k-1)all-=dis[lca(A[i],A[(i+1)%k])]; return all; } void slv(){ int id=read(); op=read(),n=read(); up(i,1,n-1){ int x=read(),y=read(),w=read(); v[x].p_b(m_p(y,w)),v[y].p_b(m_p(x,w)); }dfs(1);dfs2(1,1); up(i,1,n)P[i]=read(); ds.bd(); int q=read(),l=0,r=0,k=0; while(q--){ dec(l,r,k); lst=qry(l,r,k); printf("%lld\n",lst); } }int main(){ //freopen("d.in","r",stdin); //freopen("d.out","w",stdout); slv(); fclose(stdin); fclose(stdout); return 0; }