#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,SQRT=100,INF=1e9;
int act,n,u,h[MAXN],A[MAXN],B[MAXN];
struct Block{
int tim,op;
unordered_map<int,set<int>>aristas;
Block(){
tim=INF;
op=0;
}
void ins(int u,int a,int b){
op++;
if(aristas[a].count(b)){
aristas[a].erase(b);
}else{
aristas[a].insert(b);
}
if(aristas[b].count(a)){
aristas[b].erase(a);
}else{
aristas[b].insert(a);
}
}
}blk[200];
int question(int x, int y, int v) {
v--;
int l=-1,r=act+1;
while(r-l>1){
int m=(r+l)/2;
if(blk[m].tim<=v){
l=m;
}else{
r=m;
}
}
set<int>nx,ny;
int ini=0;
if(l!=-1){
nx=blk[l].aristas[x];
ny=blk[l].aristas[y];
ini=blk[l].tim+1;
}
L(i,ini,v){
int a=A[i],b=B[i];
if(a==x||b==x){
int z=(a==x?b:a);
if(nx.count(z))nx.erase(z);
else nx.insert(z);
}
if(a==y||b==y){
int z=(a==y?b:a);
if(ny.count(z))ny.erase(z);
else ny.insert(z);
}
}
int ans=INF;
for(auto i:nx){
for(auto j:ny){
ans=min(ans,abs(h[i]-h[j]));
}
}
return ans;
}
int main(){
int d,q;cin>>n>>d>>u>>q;
L(i,0,n-1)cin>>h[i];
L(i,0,u-1){
cin>>A[i]>>B[i];
if(blk[act].op>=SQRT){
act++;
blk[act-1].tim=i-1;
blk[act].aristas=blk[act-1].aristas;
}
blk[act].ins(i,A[i],B[i]);
}
blk[act].tim=u-1;
while(q--){
int x,y,v;cin>>x>>y>>v;
cout<<question(x,y,v)<<endl;
}
}
