传送门

#include<bits/stdc++.h>
#define int long long
using namespace std;
int w,f[150005][35],dis[150005],lans,s,dep[150005],cnt,fa[150005],pos[150005],temp,res,u,v,a[150005],vis[150005],maxp[150005],dis2[150005],sums,id,n,m,op,x,k,head[300005];
struct node{
	int to,nxt,w;
}e[300005];
struct node2{
	int val,sum;
	bool operator<(const node2& a)const{
		return val<a.val;
	};
};
vector<node2>ans[150005][3];
void add(int x,int y,int w){
	e[++cnt].to=y;
	e[cnt].nxt=head[x];
	head[x]=cnt;
	e[cnt].w=w;
}
void dfs(int x,int pre){
	dis2[x]=1;
	maxp[x]=0;
	for(register int i=head[x];i;i=e[i].nxt){
		if(e[i].to==pre||vis[e[i].to]){
			continue;
		}
		dfs(e[i].to,x);
		dis2[x]+=dis2[e[i].to];
		maxp[x]=max(maxp[x],dis2[e[i].to]);
	}
	maxp[x]=max(maxp[x],sums-dis2[x]); 
	if(maxp[id]>maxp[x]){
		id=x;
	}
}
void dfs2(int x,int pre,int depth){
	dep[x]=depth;
	f[x][0]=pre;
	for(register int i=1;i<=20;i++){
		f[x][i]=f[f[x][i-1]][i-1];
	}
	for(register int i=head[x];i;i=e[i].nxt){
		if(e[i].to==pre){
			continue;
		}
		dis[e[i].to]+=dis[x]+e[i].w;
		dfs2(e[i].to,x,depth+1);
	}
}
int lca(int x,int y){
	if(dep[x]<dep[y]){
		swap(x,y); 
	}
	for(register int i=20;i>=0;i--){
		if(dep[f[x][i]]>dep[y]){
			x=f[x][i];
		}
	}
	if(x==y){
		return x;
	}
	for(register int i=20;i>=0;i--){
		if(f[x][i]!=f[y][i]){
			x=f[x][i];
			y=f[y][i];
		}
	}
	return f[x][0];
} 
void dfs3(int x,int pre,int father,int id){
	ans[father][id].push_back((node2){a[x],dis[x]+dis[father]-dis[lca(x,father)]*2});
	for(register int i=head[x];i;i=e[i].nxt){
		if(vis[e[i].to]||e[i].to==pre){
			continue;
		}
		dfs3(e[i].to,x,father,id);
	}
}
void build(int x){
	vis[x]=1;
	for(register int i=head[x];i;i=e[i].nxt){
		if(vis[e[i].to]){
			continue;
		}
		ans[x][temp].push_back((node2){-1,0});
		ans[x][temp].push_back((node2){s+1,0});
		dfs3(e[i].to,x,x,temp);
		sort(ans[x][temp].begin(),ans[x][temp].end());
		for(register int j=1;j<=ans[x][temp].size()-1;j++){
			ans[x][temp][j].sum+=ans[x][temp][j-1].sum;
		}
		temp++;
	}
	temp=0;
	for(register int i=head[x];i;i=e[i].nxt){
		if(vis[e[i].to]){
			continue;
		}
		id=0;
		sums=dis2[e[i].to];
		maxp[0]=1e18;
		dfs(e[i].to,0);
		sums=dis2[e[i].to];
		dfs(id,0);
		fa[id]=x;
		pos[id]=temp;
		temp++;
		build(id);
	}
} 
int query(int x,int l,int r){
	int last=0,tot=0;
	for(register int i=x;i;i=fa[i]){
		if(l<=a[i]&&a[i]<=r){
			tot+=dis[x]+dis[i]-dis[lca(x,i)]*2;
		}
		for(register int j=0;j<=2;j++){
			if(j==pos[last]||!ans[i][j].size()){
				continue;
			}
			int left=lower_bound(ans[i][j].begin(),ans[i][j].end(),node2{l,-1})-ans[i][j].begin();
			int right=lower_bound(ans[i][j].begin(),ans[i][j].end(),node2{r+1,-1})-ans[i][j].begin();
			for(register int o=0;o<ans[i][j].size();o++){
				//cerr<<i<<" "<<j<<" "<<ans[i][j][o].val<<" "<<ans[i][j][o].sum<<"测试"<<endl<<flush;
			}
			tot+=(dis[x]+dis[i]-dis[lca(x,i)]*2)*(right-left)+ans[i][j][right-1].sum-ans[i][j][left-1].sum;
		}
		last=i;
	}
	for(register int i=0;i<=2;i++){
		if(ans[x][i].empty()){
			continue;
		}
		int left=lower_bound(ans[x][i].begin(),ans[x][i].end(),node2{l,-1})-ans[x][i].begin();
		int right=lower_bound(ans[x][i].begin(),ans[x][i].end(),node2{r+1,-1})-ans[x][i].begin();
		tot+=ans[x][i][right-1].sum-ans[x][i][left-1].sum;
	}
	return tot;
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m>>s;
	for(register int i=1;i<=n;i++){
		cin>>a[i];
	}	
	for(register int i=1;i<=n-1;i++){
		cin>>u>>v>>w;
		add(u,v,w);
		add(v,u,w);
	}
	dfs2(1,0,1);  
	sums=n;
	maxp[x]=1e18;
	dfs(1,0);
	sums=n;
	dfs(id,0);
	build(id);
	for(register int i=1;i<=m;i++){
		cin>>w>>u>>v;
		u=(u+lans)%s;
		v=(v+lans)%s;
		if(u>v){
			swap(u,v);
		}
		cout<<(lans=query(w,u,v))<<'\n';
	}
}