Minimizing Height Difference between Trusted Shamans

Long ago on Shaman Island, all inhabitants lived on beanstalks high as the sky. Each shaman has a unique ID in the range \(0\) to \(N-1\) and lives at a height \(H_i\). The distance between two shamans is defined as the absolute difference of their heights.

When a formula for a powerful potion was stolen, a curse was cast over the island. Initially, at the moment the curse took effect, no shaman trusted any other. However, at the end of each day (precisely at midnight), exactly one pair of shamans had their mutual trust status toggled (if they trusted each other then they would stop, and vice versa). Note that at any moment a shaman can trust at most \(D\) other shamans.

It is suspected that the thief leaked the formula, via a remote message between two shamans: one being the thief and the other evil. For the leak, each of them visited the home of a shaman they trusted (it might be that they visited each other’s houses) and the message was transmitted through the window. Since the shamans’ hearing is limited and sound does not travel far, the two friends (one trusted by the thief and the other trusted by the evil shaman) must be as close as possible in height.

Your task is: Given a query specifying the thief \(x\), the evil shaman \(y\), and a day \(v\), determine the minimum possible absolute difference \( |H_{x'} - H_{y'}| \) between any pair of shamans \(x'\) and \(y'\) such that at day \(v\) (after applying all trust changes up to that day) \(x'\) is among those whom \(x\) trusts and \(y'\) is among those whom \(y\) trusts.

If either \(x\) or \(y\) trusts no one at that time, output -1.

Note: The trust relationships change daily according to a log of events. Initially (day 0) no pair of shamans trusts each other. On each day from 1 to \(E\), exactly one trust relationship toggles. It is guaranteed that the input events will never cause a shaman to trust more than \(D\) others.

inputFormat

The first line contains three integers \(N\), \(D\), and \(E\) \( (1 \leq N, D, E \leq 200)\): the number of shamans, the maximum number of shamans one can trust at any time, and the number of trust change events.

The second line contains \(N\) integers \(H_0, H_1, \dots, H_{N-1}\) representing the heights of the shamans.

The following \(E\) lines each contain two integers \(a\) and \(b\) (\(0 \leq a, b < N\), \(a \neq b\)), representing that at the end of the corresponding day, the trust between shaman \(a\) and shaman \(b\) is toggled.

Next, a line containing an integer \(Q\) (number of queries, \(1 \le Q \le 200\)).

Each of the following \(Q\) lines contains three integers: \(v\), \(x\), and \(y\) (with \(0 \le v \le E\) and \(0 \le x, y < N\)). Here, \(v\) indicates the day (i.e. number of events applied) at which the query is made, \(x\) is the thief shaman, and \(y\) is the evil shaman.

outputFormat

For each query, output a single integer: the minimum possible absolute difference between the heights of a shaman trusted by \(x\) and a shaman trusted by \(y\) at day \(v\). If either \(x\) or \(y\) trusts no one at that time, output \(-1\).

sample

5 2 4
10 20 30 40 50
0 1
2 3
1 2
0 1
5
0 0 2
1 0 1
2 0 3
3 1 2
4 1 3

-1
10
10
10
0