CF 上可以顺利AC，在luogu上MLE了。这已经是CF官方题解的做法了/kk

#include<cstdio>
#include<iostream>
#include<queue>
#include<algorithm>
#include<cstring>
#include<set>
#include<vector>
#include<cmath>
#include<map>
#define PII pair<int,int>
#define pb push_back
#define ep emplace_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
inline 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<<3)+(x<<1)+(c^48);c=getchar();}
	return f==1?x:~x+1;
}
inline void print(int x){
	if(x<0) putchar('-'),x=~x+1;
	if(x>=10) print(x/10);
	putchar((x%10)|48);
}
int n,D,U,Q;
int h[100010];
int rt[200010];
int ls[10000010],rs[10000010];
vector<int>vec[10000010]; 
int cnt;
PII edge[200010];
map<PII,int>Map;
bool ed[200010];
void modify(int &p,int l,int r,int L,int R,int k){
	if(!p) p=++cnt;
	if(l>=L&&r<=R){
		vec[p].pb(k);return ;
	}
	int mid=l+r>>1;
	if(L<=mid) modify(ls[p],l,mid,L,R,k);
	if(R>mid) modify(rs[p],mid+1,r,L,R,k);
}
void query(int p,int l,int r,int pos,vector<int>&s){
	if(!p) return ;
	for(int i:vec[p]) s.pb(i);
	if(l==r) return ;
	int mid=l+r>>1;
	if(pos<=mid) query(ls[p],l,mid,pos,s);
	else query(rs[p],mid+1,r,pos,s);
}
int main(){
	n=read(),D=read(),U=read(),Q=read();
	for(int i=1;i<=n;++i) h[i]=read();
	for(int i=1;i<=U;++i){
		int a=read(),b=read();
		++a,++b;
		edge[i].fi=min(a,b),edge[i].se=max(a,b);
		if(Map[edge[i]]){
			int t=Map[edge[i]];
			ed[t]=ed[i]=1;
			modify(rt[a],1,U,t,i-1,h[b]);
			modify(rt[b],1,U,t,i-1,h[a]);
			Map[edge[i]]=0;
		}
		else Map[edge[i]]=i;
	}
	Map.clear();
	for(int i=1;i<=U;++i){
		if(!ed[i]){
			int x=edge[i].fi,y=edge[i].se;
			modify(rt[x],1,U,i,U,h[y]);
			modify(rt[y],1,U,i,U,h[x]);
		}
	}
	vector<int>sx,sy;
	for(int i=1;i<=Q;++i){
		int x=read(),y=read(),t=read();
		++x,++y;
		query(rt[x],1,U,t,sx);
		query(rt[y],1,U,t,sy);
		int ans=1e9;
		if(sx.empty()||sy.empty()){
			printf("%d\n",ans);fflush(stdout);
		sx.clear();sy.clear();continue ;
		}
		sort(sx.begin(),sx.end());
		sort(sy.begin(),sy.end());
		int N=sx.size()-1,M=sy.size()-1;
//		for(int j=0;j<=N;++j) printf("%d ",sx[j]);
		for(int j=0,k=0;j<=N;++j){
			while(k<=M&&sy[k]<=sx[j]) ans=min(ans,sx[j]-sy[k++]);
			if(k<=M) ans=min(ans,sy[k]-sx[j]);
		} 
		sx.clear();sy.clear();
		printf("%d\n",ans);fflush(stdout);
	}
}