Description

A long time ago, on the Island of Shamans, everyone lived on a beanstalk as tall as the sky. Each shaman has a unique ID in the range from $0$ to $N-1$. The height where shaman $i$ lives is denoted by $H_i$. The distance between two shamans is defined as the absolute value of the difference of their heights.

All shamans originally lived in harmony, until one day the recipe of the Power Potion was stolen. To cover up his actions, the thief cast a curse on the whole island, and most residents no longer trusted each other.

Although the situation is very complex, after investigation, an organization obtained the following information:

• When the curse first took effect, all shamans stopped trusting each other.
• The curse itself is unstable. At the end of each day (to be exact, at midnight), a certain pair of shamans will either start trusting each other or stop trusting each other.
• Unfortunately, at any moment, a shaman trusts at most $D$ other shamans.

The organization also reconstructed the trust-change log between shamans. The log records, at each midnight, which pair of shamans had their trust relationship changed (from not trusting to trusting, or from trusting to not trusting).

The organization members believe that the thief also leaked the recipe to an evil shaman via a “remote whisper” (pinyin: gekong chuanhua). To avoid being discovered, they each visited the home of one shaman they trusted. During the visit, the thief leaked the recipe to the evil shaman through the window. Note that the trusted friend did not have to be at home at that time; in fact, the two shamans might even visit each other’s homes. After all, shamans are strange.

Luckily, because shamans have limited hearing, sound cannot travel too far. This means the distance between the two friends (the thief’s friend and the evil shaman’s friend) must be as small as possible.

Now the organization asks you to help with the investigation. They want to verify their guess: when the thief is $x$, the evil shaman is $y$, and the leak happened on day $v$, what is the minimum distance the whisper needs to travel? That is, on day $v$, you need to find a shaman $x'$ among all shamans trusted by $x$, and a shaman $y'$ among all shamans trusted by $y$, such that the distance between $x'$ and $y'$ is minimized.

You have obtained all information needed to compute the answers, but you must answer each query online.

Input Format

Interactive IO only.

The first line contains four integers $N, D, U, Q$, representing the number of shamans, the maximum number of friends a shaman can trust, the number of days included in the log, and the number of queries.

The next line contains $N$ integers separated by single spaces. The $i$-th integer represents the height $H_{i-1}$ where shaman $i-1$ lives.

The next $U$ lines: the $i$-th line contains two integers $A_i, B_i$, meaning that at the end of day $i-1$, the trust status between shamans with IDs $A_i$ and $B_i$ changes. That is, if $A_i$ and $B_i$ trusted each other on day $i-1$, then starting from day $i$ they no longer trust each other, and vice versa.

Then you need to answer $Q$ queries. Queries must be answered online, i.e., you must finish answering one query before you can read the next one.

Each query contains three integers $x, y, v$, meaning the thief is $x$, the evil shaman is $y$, and the leak happens on day $v$.

Output Format

For each query, on day $v$, find a shaman $x'$ among all shamans trusted by $x$, and a shaman $y'$ among all shamans trusted by $y$, such that the distance between $x'$ and $y'$ is minimized, and output this minimum value.

In particular:

• If there exists a shaman trusted by both $x$ and $y$, output $0$.
• If $x$ or $y$ has no trusted friends on day $v$, output $1000000000$ ($10^9$).

After answering a query, you must flush the buffer immediately.

For C++ users, you can flush the buffer using fflush(stdout); or cout.flush().

6 5 11 4
2 42 1000 54 68 234
0 1
2 0
3 4
3 5
3 5
1 3
5 3
0 5
3 0
1 3
3 5
0 3 4
3 0 8
0 5 5
3 0 11

26
0
1000000000
14

Hint

Sample Explanation

Below are the queries:

Below is how the trust relationships change each day:

Subtasks

All testdata satisfy: $2 \leq N \leq 10^5$, $1 \leq D \leq 500$, $0 \leq U \leq 2 \times 10^5$, $1 \leq Q \leq 5 \times 10^4$.

The constraints for each subtask are as follows:

Translated by ChatGPT 5