#include <bits/stdc++.h>
#define L(i,j,k) for(int i=(j);i<=(k);i++)
#define R(i,j,k) for(int i=(j);i>=(k);i--)
#define all(x) x.begin(),x.end()
#define sz(a) ((int)a.size())
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair<int,int> ii;
const int MAXN=1e5+5,MAXU=2e5+5,INF=1e9;
int n,u,d,q,h[MAXN],a[MAXU],b[MAXU];
void flip(set<int>&s,int x){
if(s.count(x))s.erase(x);
else s.insert(x);
}
int memo[200000];
struct Block{
int start;
set<int>nodes;
vector<pair<int,int>>heights,changes;
void add(int day,int x){
changes.push_back({day,x});
}
Block nextBlock(){
Block ret;
ret.nodes=nodes;
for(auto &p:changes){
flip(ret.nodes,p.second);
}
return ret;
}
vector<int> query(int day){
vector<int>touch2;
for(auto &x:nodes)memo[x]=1;
for(auto &p:changes){
if(p.first<=day){
if(memo[p.second]==0){
touch2.pb(p.second);
}
memo[p.second]++;
}else break;
}
vector<int>h1,h2;
for(auto &p:heights){
if(memo[p.second]%2==1){
h1.pb(p.first);
}
}
for(auto &x:touch2){
if(memo[x]%2==1){
h2.pb(h[x]);
}
}
sort(all(h2));
vector<int>ret;
ret.reserve(sz(h1)+sz(h2));
merge(all(h1),all(h2),back_inserter(ret));
for(auto &x:touch2)memo[x]=0;
for(auto &x:nodes)memo[x]=0;
return ret;
}
};
struct Sqrt{
vector<Block>blocks;
void add(int day,int x){
if(blocks.empty()){
blocks.push_back(Block{0,{},{},{}});
}
if(sz(blocks.back().changes)>600){
blocks.push_back(blocks.back().nextBlock());
blocks.back().start=day;
flip(blocks.back().nodes,x);
for(auto x:blocks.back().nodes){
blocks.back().heights.pb({h[x],x});
}
sort(all(blocks.back().heights));
return;
}
blocks.back().add(day,x);
}
};
vector<int> get_nodes(vector<Block>&blocks,int day){
if(blocks.empty())return {};
int l=0,r=sz(blocks);
while(r-l>1){
int m=(r+l)/2;
if(blocks[m].start<=day){
l=m;
}else{
r=m;
}
}
return blocks[l].query(day);
}
bool cmp(int &a,int &b){
return h[a]<h[b];
}
int main(){
cin>>n>>d>>u>>q;
L(i,0,n-1)cin>>h[i];
vector<Sqrt>His(n);
L(i,1,u){
cin>>a[i]>>b[i];
His[a[i]].add(i,b[i]);
His[b[i]].add(i,a[i]);
}
while(q--){
int x,y,v;cin>>x>>y>>v;
auto v1=get_nodes(His[x].blocks,v);
auto v2=get_nodes(His[y].blocks,v);
int i=0,j=0;
int ans=INF;
while(i<sz(v1)&&j<sz(v2)){
ans=min(ans,abs(v1[i]-v2[j]));
if(v1[i]>=v2[j]){
j++;
}else i++;
}
cout<<ans<<endl;
}
}
