#include<bits/stdc++.h>
using namespace std;

int n,d,u,*f;

void init(int N, int D, int F[]) {
	n=N;
	d=D;
	f=&F[0];
}

vector<int> evs[100001];

vector<vector<int>> trs[100001];

void insert(int from, int ind, int L, int R, int i, int j, int to) {
	if(R<i || j<L) return ;
	if(i<=L && R<=j) {
		trs[from][ind].push_back(f[to]);
		return ;
	}
	insert(from, 2*ind, L, (L+R)/2, i, j, to);
	insert(from, 2*ind+1, (L+R)/2+1, R, i, j, to);
}

void get(int from, int ind, int L, int R, int i, vector<int>& res) {
	while(1) {
		for(auto j:trs[from][ind]) {
			res.push_back(j);
		}
		
		if(L==R) {
			break ;
		}
		
		if(i<=(L+R)/2) {
			R=(L+R)/2;
			ind=2*ind;
		}else {
			L=(L+R)/2+1;
			ind=2*ind+1;
		}		
	}
}

vector<int> egyik, masik;
void curseChanges(int U, int A[], int B[]) {
	u=U;
	for(int i=0;i<n;++i) {
		evs[i].push_back(0);
	}
	for(int i=0; i<U; i++) {
		evs[A[i]].push_back(i+1);
		evs[B[i]].push_back(i+1);
	}
	for(int i=0;i<n;++i) {
		trs[i].resize(4*evs[i].size());
	}
	map<pair<int,int>,int> since;
	auto add=[&](int from, int L, int R, int to) {
		
		int pos1=lower_bound(evs[from].begin(), evs[from].end(), L)-evs[from].begin();
		int pos2=prev(lower_bound(evs[from].begin(), evs[from].end(), R))-evs[from].begin();

		insert(from, 1, 0, (int)evs[from].size()-1, pos1, pos2, to);
	};
	
	for(int i=0;i<U;++i) {
		if(A[i]>B[i]) swap(A[i], B[i]);
		if(since.count(make_pair(A[i], B[i]))) {
			add(A[i], since[make_pair(A[i], B[i])], i+1, B[i]);
			add(B[i], since[make_pair(A[i], B[i])], i+1, A[i]);
			since.erase(make_pair(A[i], B[i]));
		}else {
			since[make_pair(A[i], B[i])]=i+1;
		}
	}
	
	for(auto i:since) {
		add(i.first.first, i.second, U+1, i.first.second);
		add(i.first.second, i.second, U+1, i.first.first);
	}
	
	egyik.reserve(500);
	masik.reserve(500);
}

void get_all(int x, int v, vector<int>& to) {
	to.clear();
	auto itx=upper_bound(evs[x].begin(), evs[x].end(), v);
	if(itx==evs[x].begin() || evs[x].empty()) return ;
	
	int posx=prev(itx)-evs[x].begin();

	get(x, 1,0,(int)evs[x].size()-1, posx, to);
}

int question(int X, int Y, int V) {
	get_all(X,V,egyik);
	get_all(Y,V,masik);
	if(egyik.empty() || masik.empty()) return 1e9;
	
	sort(egyik.begin(), egyik.end());
	
	sort(masik.begin(), masik.end());
	
	int ans=1e9;
	int i=0, j=0;
	while(i<(int)egyik.size() && j<(int)masik.size()) {
		ans=min(ans, abs(egyik[i]-masik[j]));
		if(egyik[i]<masik[j]) {
			i++;
		}else {
			j++;
		}
	}	
	
	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;
	}
}

Index the columns from $$$0\ldots C-1$$$ rather than $$$1\ldots C$$$ and fix $$$R$$$. As mentioned above, for all $$$(i,j)$$$ satisfying $$$0<i,0<j,i+j\le C-1$$$, we want to show that

or

A king path can be described by a sequence

such that $$$p_x\in [0,C-1]$$$, and $$$|p_x-p_{x+1}|\le 1$$$.

Define

• $$$path[i][j]$$$: the set of all king paths from $$$(0,i)\to (R-1,j)$$$
• $$$zero[i][j]$$$: the set of all king paths from $$$(0,i)\to (R-1,j)$$$ such that $$$p_x=0$$$ for some $$$x$$$.

We can rewrite the condition we want to show as

(Note: You should first convince yourself that this holds for $$$C>R$$$. In this case, the rightmost term simply disappears.)

It suffices to biject paths on the LHS to paths on the RHS. We can do this by splitting paths into pieces, rearranging them, flipping some of them horizontally or vertically, and finally concatenating them. Define

• horizontal flip — $$$flipx(p)=[(0,p_{R-1}), (1,p_{R-2}),\ldots,(R-1,p_0)]$$$
• vertical flip — $$$flipy(p)=[(0,-p_0), (1,-p_1),\ldots,(R-1,-p_{R-1})]$$$
• concatenating two paths — $$$p_1+p_2$$$.
  • We'll need to translate the paths horizontally and vertically as necessary such that the right endpoint of $$$p_1$$$ matches up with the left endpoint of $$$p_2$$$.

First we transform each path $$$p$$$ on the LHS as follows:

• Let $$$a$$$ be the maximum $$$x$$$ such that $$$p_x=0$$$.
• Set $$$p\leftarrow flipx(p_{[0,a]})+p_{[a,R-1]}$$$

$$$p_{[0,a]}$$$ originally was a path from $$$(0,i)\to (a,0)$$$; now $$$flipx(p_{[0,a]})$$$ is a path from $$$(0,0)\to (a,i)$$$ and $$$p_{[a,R-1]}$$$ is a path from $$$(a,i)\to (R-1,i+j)$$$. The LHS now consists of all $$$p$$$ that satisfy the following:

• Let $$$a$$$ be the maximum $$$x$$$ such that $$$p_x=i$$$.
• $$$p_x\in [0,C-1]$$$ when $$$x \in [0,a]$$$
• $$$p_x\in [i+1,C-1+i]$$$ when $$$x\in [a+1,R-1]$$$.

This includes all elements of $$$path[0][i+j]$$$. Each LHS path $$$p$$$ not contained within $$$path[0][i+j]$$$ satisfies $$$p_x=C$$$ for some $$$x$$$. Let $$$b$$$ be the maximum $$$x$$$ such that $$$p_x=C$$$, and set

We claim that this corresponds uniquely to an element of $$$zero[C-i][C-j]$$$, since

• $$$flipx(p_{[a,b]})$$$ is a path from $$$(0,C-i)\to (b-a,0)$$$. The $$$y$$$-coordinates are all in the range $$$[0,C-1]$$$, and $$$y$$$-coordinate $$$0$$$ appears only at the right end of the path.
• $$$p_{[0,a]}$$$ is a path from $$$(b-a,0)\to (b,i)$$$. Its $$$y$$$-coordinates are all in the range $$$[0,C-1]$$$
• $$$flipy(p_{[b,R-1]})$$$ is a path from $$$(b,i)\to (R-1,C-j)$$$, Its $$$y$$$-coordinates are all in the range $$$[0,C-1]$$$ and $$$y$$$-coordinate $$$i$$$ appears only at the left end of the path

The transformations we mentioned are all reversible, so the bijections hold and we're done.

Notate the number of ways when advancing $$$R-1$$$ rows, starting at column $$$i$$$ and arriving at column $$$j$$$, by $$$a_{i,j}$$$ (in terms of matrices, these $$$a_{i,j}$$$-s are the entries of $$$A^{R-1}$$$). We are proving the statement for these values.

Now, imagine we are advancing one additional row forward. The corresponding numbers of ways starting at column $$$i$$$ and arriving at column $$$j$$$ (a.k.a. the entries of $$$A^R$$$) are then

Observe that the number of ways when going $$$i\to j$$$ columnwise is the same as the number of ways for $$$j\to i$$$ (there is a simple bijection defined as taking any path of the first type and reversing it), irrespective of the number of traversed rows. So on one hand, we have $$$a_{i,j} = a_{j,i}$$$ for any $$$1\leq i,j\leq C$$$ as $$$A^{R-1}$$$ is symmetric. On the other hand, $$$A^R$$$ is symmetric too, so starting from the first row/column pair, we derive (using the previous symmetry)

etc up to $$$a_{2,n}$$$, then advance to the second row/column pair

etc up to $$$a_{3,n}$$$. Here the relations from the first row/column were used for the underlined entries. Proceeding this way completes the proof.