#include <bits/stdc++.h>
using namespace std;
struct segTree{
struct node{
map<int,vector<int>>mp;
};
node *st;
segTree(int n){
int x = ceil(log2(n));
x++;
st = new node[(1<<x)];
}
void update(int l, int r, int s, int e, int ind, int x, int y){
if(e<l||s>r){
return;
}
if(s<=l&&r<=e){
st[ind].mp[x].push_back(y);
st[ind].mp[y].push_back(x);
return;
}
int mid = (l+r)/2;
update(l,mid,s,e,ind*2+1,x,y);
update(mid+1,r,s,e,ind*2+2,x,y);
}
void query(int l, int r, int i, int ind, int x, int y, vector<int>&sx, vector<int>&sy, int h[]){
for(int i : st[ind].mp[x]){
sx.push_back(h[i]);
}
for(int i : st[ind].mp[y]){
sy.push_back(h[i]);
}
if(l==r)
return;
int mid = (l+r)/2;
if(i<=mid){
query(l,mid,i,ind*2+1,x,y,sx,sy,h);
}
else{
query(mid+1,r,i,ind*2+2,x,y,sx,sy,h);
}
}
};
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n,d,u,q;
cin >> n >> d >> u >> q;
int h[n];
for(int &i : h){
cin >> i;
}
segTree st(u+1);
set<array<int,3>>s;
for(int i = 0;i<u;i++){
int a,b;
cin >> a >> b;
if(a>b){
swap(a,b);
}
auto it = (s.lower_bound({a,b,-1}));
if(it!=s.end()&&(*it)[0]==a&&(*it)[1]==b){
///stop trust
st.update(0,u,(*it)[2]+1,i,0,a,b);
s.erase(it);
}
else{
///begin
s.insert({a,b,i});
}
}
for(array<int,3>a:s){
st.update(0,u,a[2]+1,u,0,a[0],a[1]);
}
while(q--){
int x,y,d;
cin >> x >> y >> d;
vector<int>xarr,yarr;
st.query(0,u,d,0,x,y,xarr,yarr,h);
sort(xarr.begin(),xarr.end());
int ans = 1e9;
if(xarr.size()){
for(int i : yarr){
auto it = lower_bound(xarr.begin(),xarr.end(),i);
if(it!=xarr.end()){
ans=min(ans,(*it)-i);
}
if(it!=xarr.begin()){
it--;
ans=min(ans,i-(*it));
}
}
}
cout << ans << endl;
}
return 0;
}
