#include <vector>
#include <iostream>
#include <algorithm>
#include <set>

using namespace std;
///DIF > 4
const int INF = 1000000000;
const int DIF = 50;
int NN, tart, megy, last, hol, vv, a, b, ans;
int FF[100000];
int kik[2][DIF];
int step[2];
int id[2];
int db[2];
int st[2];
int p[2][100000];
bool bent[100000];
bool kiv[2][100000];
struct pont{
    int a, ido, id;
    bool be;
};
vector<pair<int,int> > par[100000];
vector<pont> sor[100000];
vector<pair<int,int> > vec[100000];
set<pair<int,int> > szet;
set<int> meg[2];
int el[2][DIF];

void init(int N, int D, int F[]) {
    NN = N; tart = 1;
    for(int i=0; i<N; i++) FF[i] = F[i];
}

void curseChanges(int U, int A[], int B[]) {
    for(int i=0; i<U; i++) {
        par[A[i]].push_back({B[i],i+1});
        par[B[i]].push_back({A[i],i+1});
    }
    for(int i=0; i<NN; i++){
        sor[i].resize(par[i].size()+1); sor[i][0].ido = 0; sor[i][0].id = 0; megy = 1;
        szet.clear();
        for(pair<int,int> j:par[i]){
            bent[j.first] = !bent[j.first];
            sor[i][megy].be = bent[j.first];
            sor[i][megy].a = j.first;
            sor[i][megy].ido = j.second;
            if(bent[j.first]){
                szet.insert({FF[j.first],j.first});
            } else {
                szet.erase({FF[j.first],j.first});
            }
            if(megy%DIF==0){
                vec[tart].resize(szet.size()); hol = 0;
                for(pair<int,int> k:szet) vec[tart][hol++] = k;
                sor[i][megy].id = tart++;
            } else {
                sor[i][megy].id = -1;
            }
            megy++;
        }
        for(pair<int,int> j:szet) bent[j.second] = false;
    }
}

int bi(int x, int y){
    if(x==y) return x;
    int fel = (x+y+1)/2;
    if(sor[hol][fel].ido<=vv) return bi(fel,y);
    return bi(x,fel-1);
}
void keres(int x, int y){
    hol = x; hol = bi(0,sor[x].size()-1);
    step[y] = 0; db[y] = 0;
    while(sor[x][hol].id==-1){
        a = sor[x][hol].a;
        if(!bent[a]){
            bent[a] = true;
            if(sor[x][hol].be){
                el[y][db[y]++] = FF[a];
            } else {
                kiv[y][a] = true;
            }
        }
        kik[y][step[y]++] = a;
        hol--;
    }
    sort(el[y],el[y]+db[y]);
    for(int i=0; i<step[y]; i++) {bent[kik[y][i]] = false;}
    id[y] = sor[x][hol].id;
}
int question(int x, int y, int v) {
    vv = v;
    keres(x,0); keres(y,1);
    ans = INF;
    /*for(int i=0; i<2; i++){
        meg[i].clear();
        for(pair<int,int> j:vec[id[i]]) if(!kiv[i][j.second]) meg[i].insert(j.first);
        for(int j=0; j<db[i]; j++) meg[i].insert(el[i][j]);
    }
    auto it = meg[1].begin();
    for(int i:meg[0]){
        while(it!=meg[1].end() && (*it)<i){
            ans = min(ans,abs((*it)-i)); it++;
        }
        if(it==meg[1].end()) break;
        ans = min(ans,abs((*it)-i));
    }*/
    for(int i=0; i<2; i++){
        int aa = 0, bb = 0; st[i] = 0;
        while(aa<vec[id[i]].size() || bb<db[i]){
            if(aa==vec[id[i]].size()){
                p[i][st[i]++] = el[i][bb++];
            } else if(bb==db[i]){
                if(!kiv[i][vec[id[i]][aa].second]) p[i][st[i]++] = vec[id[i]][aa].first;
                aa++;
            } else if(vec[id[i]][aa].first<el[i][bb]){
                if(!kiv[i][vec[id[i]][aa].second]) p[i][st[i]++] = vec[id[i]][aa].first;
                aa++;
            } else {
                p[i][st[i]++] = el[i][bb++];
            }
        }
    }
    int g = 0;
    for(int i=0; i<st[0]; i++){
        while(g<st[1] && p[1][g]<p[0][i]){
            ans = min(ans,p[0][i] - p[1][g++]);
        }
        if(g==st[1]) break;
        ans = min(ans,p[1][g] - p[0][i]);
    }


    for(int i=0; i<2; i++){
        for(int j=0; j<step[i]; j++) kiv[i][kik[i][j]] = false;
    }
    return ans;
}

int main() {
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	int n,d,u,q;
	cin>>n>>d>>u>>q;
	int *f=new int[n];
	for(int i=0;i<n;++i) cin>>f[i];
	int *a=new int[u], *b=new int[u];
	for(int i=0;i<u;++i) cin>>a[i]>>b[i];
	
	init(n,d,f);
	curseChanges(u,a,b);
	while(q--) {
		int x,y,v;
		cin>>x>>y>>v;
		cout<<question(x,y,v)<<endl;
	}
}