#include "bits/stdc++.h"
using namespace std;
#define vec vector
#define all(x) (x).begin(), (x).end()
const int inf = 1e9;
using pii = pair<int, int>;
int n, d, u;
vec<int> h, a, b;
void init(int N, int D, int H[]) {
n = N, d = D;
h.resize(n);
for (int i = 0; i < n; i++) h[i] = H[i];
}
void curseChanges(int U, int A[], int B[]) {
u = U;
a.resize(U);
b.resize(U);
for (int i = 0; i < U; i++) a[i] = A[i], b[i] = B[i];
}
int question(int x, int y, int v) {
vec<vec<bool>> dist(n, vec<bool>(n, false));
for (int i = 0; i < v; i++) {
if (i == u) continue;
int x = a[i], y = b[i];
if (x > y) swap(x, y);
dist[x][y] = !dist[x][y];
dist[y][x] = !dist[y][x];
}
int ans = inf;
for (int i = 0; i < n; i++) for (int j = 0; j < n; j++)
if ((i != j || (i != x && j != y)) && dist[x][i] && dist[j][y]) {
int dist = abs(h[i] - h[j]);
if (dist < ans) ans = dist;
}
return ans;
}
#ifdef debug
int main() {
int n, d, u, q;
cin >> n >> d >> u >> q;
vec<int> h(n);
for (int i = 0; i < n; i++) cin >> h[i];
init(n, d, h.data());
vec<int> a(u), b(u);
for (int i = 0; i < u; i++) cin >> a[i] >> b[i];
curseChanges(u, a.data(), b.data());
while (q--) {
int x, y, v, ans; cin >> x >> y >> v >> ans;
if (question(x, y, v) != ans) {
cout << "wrong answer for " << x << ' ' << y << ' ' << v << endl;
cout << question(x, y, v) << ' ' << ans << endl;
return 0;
} else cout << "correct answer for " << x << ' ' << y << ' ' << v << endl;
}
return 0;
}
#endif
