#include<bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
int SSZ=20;
vector<pair<int,int>>C[100100];
map<int,set<int>> temps[100100], prooc[100100];
set<int>cur[100100];
int h[100100],ord[100100],rev[100100],CC;
void init(int N, int D, int H[]) {
vector<int>v;
for(int i=0;i<N;i++) h[i]=H[i],
v.push_back(i),temps[i][-1];
sort(v.begin(),v.end(),[](int a,int b){return h[a]<h[b];});
for(int i=0;i<N;i++)
rev[ord[v[i]]=i]=v[i];
}
void curseChanges(int U, int A[], int B[]) {
for(int i=0;i<U;i++){
A[i]=ord[A[i]];
B[i]=ord[B[i]];
if(cur[A[i]].count(B[i]))
cur[A[i]].erase(B[i]),
cur[B[i]].erase(A[i]);
else cur[A[i]].insert(B[i]),
cur[B[i]].insert(A[i]);
C[A[i]].push_back({i,B[i]});
C[B[i]].push_back({i,A[i]});
if(C[A[i]].size()%SSZ==0)
temps[A[i]][i]=cur[A[i]];
if(C[B[i]].size()%SSZ==0)
temps[B[i]][i]=cur[B[i]];
}
for(auto&i:cur)
i.clear();
}
int calc(vector<int>A,vector<int>B){
int l=0,r=0,ans=1e9;
while(l<A.size()&&r<B.size()){
ans=min(ans,abs(A[l]-B[r]));
if(A[l]<B[r])l++;
else r++;
}
return ans;
}
int question(int x, int y, int v) {
x=ord[x],y=ord[y];
vector<int>A,B;
auto it=--temps[x].lower_bound(v);
set<int>X;
swap(X,it->second);
auto it2=lower_bound(C[x].begin(),C[x].end(),make_pair(it->first+1,0));
int I=it2-C[x].begin(),begI=I;
for(;I<C[x].size()&&C[x][I].first<v;I++)
if(X.count(C[x][I].second))
X.erase(C[x][I].second);
else X.insert(C[x][I].second);
for(auto i:X)A.push_back(h[rev[i]]);
while(--I>=begI)if(X.count(C[x][I].second))
X.erase(C[x][I].second);
else X.insert(C[x][I].second);
swap(X,it->second);
it=--temps[y].lower_bound(v);
swap(X,it->second);
it2=lower_bound(C[y].begin(),C[y].end(),make_pair(it->first+1,0));
I=it2-C[y].begin(),begI=I;
for(;I<C[y].size()&&C[y][I].first<v;I++)
if(X.count(C[y][I].second))
X.erase(C[y][I].second);
else X.insert(C[y][I].second);
for(auto i:X)B.push_back(h[rev[i]]);
while(--I>=begI)if(X.count(C[y][I].second))
X.erase(C[y][I].second);
else X.insert(C[y][I].second);
swap(X,it->second);
return calc(A,B);
}
#ifdef ONLINE_JUDGE
int main() {
int N, D, U, Q;
std::ios::sync_with_stdio(false); std::cin.tie(NULL);
std::cin >> N >> D >> U >> Q;
int *F = new int[N];
for (int i=0; i<N; i++)
std::cin >> F[i];
init(N, D, F);
int *A = new int[U], *B = new int[U];
for (int i=0; i<U; i++) {
std::cin >> A[i] >> B[i];
}
curseChanges(U, A, B);
bool correct = true;
for (int i=0; i<Q; i++) {
int X,Y,V;
std::cin >> X >> Y >> V;
cout<<question(X,Y,V)<<endl;
}
return 0;
}
#endif
