#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5;
const int MAXQ = 2e5 + 5;
const int C = 50;
int N, D, H[MAXN], pos[MAXN];
vector<int> modified_time[MAXN];
vector<pair<int, int>> modification[MAXN];
vector<vector<int>> blocks[MAXN];
void init(int _N, int _D, int _H[]){
N = _N;
D = _D;
copy(_H, _H + N, H);
vector<pair<int, int>> v;
for(int i = 0; i < N; ++i){
v.emplace_back(H[i], i);
}
sort(v.begin(), v.end());
sort(H, H + N);
for(int i = 0; i < N; ++i){
pos[v[i].second] = i;
}
}
bool on[MAXN], used[MAXN];
void merge_vector(vector<int>& A, const vector<int>& B){
vector<int> result;
int i = 0, j = 0;
while(i < (int)A.size() || j < (int)B.size()){
if(i == (int)A.size()) result.emplace_back(B[j++]);
else if(j == (int)B.size()) result.emplace_back(A[i++]);
else if(A[i] < B[j]) result.emplace_back(A[i++]);
else result.emplace_back(B[j++]);
}
swap(result, A);
}
bool duplicated(const vector<int>& A){
for(int i = 0; i + 1 < (int)A.size(); ++i) if(A[i] == A[i + 1]) return true;
return false;
}
bool intersect(const vector<int>& A, const vector<int>& B){
//just for assertion
for(auto x : A) if(binary_search(B.begin(), B.end(), x)) return true;
return false;
}
void addBlock(int u){
for(int v : blocks[u].back()) on[v] = 1, used[v] = true;
int sz = (int)modification[u].size();
vector<int> cur;
for(int i = sz - C; i < sz; ++i){
assert(i >= 0);
int type, v;
tie(type, v) = modification[u][i];
if(!used[v]) used[v] = true, cur.push_back(v);
if(type == -1) on[v] = false;
if(type == +1) on[v] = true;
}
vector<int> old_candidates, new_candidates;
for(int v : blocks[u].back()) {
if(on[v]) old_candidates.emplace_back(v);
on[v] = used[v] = false;
}
for(int v : cur) {
if(on[v]) new_candidates.emplace_back(v);
on[v] = used[v] = false;
}
assert(!duplicated(old_candidates));
assert(!duplicated(new_candidates));
assert(!intersect(old_candidates, new_candidates));
sort(new_candidates.begin(), new_candidates.end());
blocks[u].emplace_back(old_candidates);
merge_vector(blocks[u].back(), new_candidates);
// cout << "addBlock " << u << '\n';
// for(int i = sz - C; i < sz; ++i) cout << "(" << modification[u][i].first << ' ' << modification[u][i].second << ")\n";
// for(int v : blocks[u].back()) cout << v << ' '; cout << '\n';
// cout << '\n';
}
void curseChanges(int U, int A[], int B[]){
for(int i = 0; i < N; ++i){
modified_time[i].emplace_back(0);
blocks[i].emplace_back();
}
set<pair<int, int>> pairs;
for(int i = 0; i < U; ++i){
int u = A[i], v = B[i];
u = pos[u]; v = pos[v];
modified_time[u].emplace_back(i + 1);
modified_time[v].emplace_back(i + 1);
if(u > v) swap(u, v);
if(pairs.count({u, v})){
modification[u].emplace_back(-1, v);
modification[v].emplace_back(-1, u);
pairs.erase({u, v});
} else{
modification[u].emplace_back(+1, v);
modification[v].emplace_back(+1, u);
pairs.insert({u, v});
}
if((int)modification[u].size() % C == 0) addBlock(u);
if((int)modification[v].size() % C == 0) addBlock(v);
}
}
vector<int> A, B;
void replay(vector<int>& result, int u, int n_version){
if(modification[u].empty()) return;
int B = (n_version) / C;
int mod = (n_version) % C;
for(int v : blocks[u][B]){
on[v] = true;
used[v] = true;
}
vector<int> cur;
for(int t = 0; t < mod; ++t){
int i = B * C + t;
int type, v;
tie(type, v) = modification[u][i];
if(!used[v]){
cur.emplace_back(v);
used[v] = true;
}
if(type == -1) on[v] = false;
if(type == +1) on[v] = true;
}
vector<int> old_candidates, new_candidates;
for(int v : blocks[u][B]){
if(on[v]) old_candidates.push_back(v);
on[v] = used[v] = false;
}
for(int v : cur){
if(on[v]) new_candidates.push_back(v);
on[v] = used[v] = false;
}
sort(new_candidates.begin(), new_candidates.end());
result = old_candidates;
merge_vector(result, new_candidates);
}
int question(int x, int y, int v){
x = pos[x]; y = pos[y];
int p = upper_bound(modified_time[x].begin(), modified_time[x].end(), v) - modified_time[x].begin() - 1;
int q = upper_bound(modified_time[y].begin(), modified_time[y].end(), v) - modified_time[y].begin() - 1;
assert(p >= 0 && q >= 0);
vector<int>().swap(A);
vector<int>().swap(B);
replay(A, x, p);
replay(B, y, q);
// cout << x << ' ' << y << '\n';
// cout << "A : ";
// for(auto it : A) cout << it << ' '; cout << '\n';
//
// cout << "B : ";
// for(auto it : B) cout << it << ' '; cout << '\n';
if(A.empty() && B.empty()) return (int)1e9;
int ans = (int)1e9;
int ptr = 0;
for(int i = 0; i < (int)A.size(); ++i){
while(ptr < (int)B.size() && B[ptr] < A[i]) ++ptr;
if(ptr < (int)B.size()) ans = min(ans, abs(H[A[i]] - H[B[ptr]]));
if(ptr - 1 >= 0) ans = min(ans, abs(H[A[i]] - H[B[ptr - 1]]));
}
return ans;
}
#ifdef LOCAL
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
if(fopen("task.inp", "r")){
freopen("task.inp", "r", stdin);
freopen("task.out", "w", stdout);
}
int N, D, U, Q;
cin >> N >> D >> U >> Q;
int H[N];
for(int i = 0; i < N; ++i) cin >> H[i];
int A[U], B[U];
for(int i = 0; i < U; ++i) cin >> A[i] >> B[i];
init(N, D, H);
curseChanges(U, A, B);
for(int i = 0; i < Q; ++i){
int x, y, v;
cin >> x >> y >> v;
cout << question(x, y, v) << '\n';
}
return 0;
}
#endif //LOCAL
