Vlad and the Mountains
Contest: Codeforces Round 888 (Div. 3)
Difficulty rating: 2000
Tags: binary search, data structures, dsu, graphs, implementation, sortings, trees, two pointers

Vlad decided to go on a trip to the mountains. He plans to move between $$$n$$$ mountains, some of which are connected by roads. The $$$i$$$-th mountain has a height of $$$h_i$$$.

If there is a road between mountains $$$i$$$ and $$$j$$$, Vlad can move from mountain $$$i$$$ to mountain $$$j$$$ by spending $$$h_j - h_i$$$ units of energy. If his energy drops below zero during the transition, he will not be able to move from mountain $$$i$$$ to mountain $$$j$$$. Note that $$$h_j - h_i$$$ can be negative and then the energy will be restored.

Vlad wants to consider different route options, so he asks you to answer the following queries: is it possible to construct some route starting at mountain $$$a$$$ and ending at mountain $$$b$$$, given that he initially has $$$e$$$ units of energy?

Input format:
The first line of the input contains an integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The descriptions of the test cases follow.

The first line of each test case contains two numbers $$$n$$$ and $$$m$$$ ($$$2 \le n \le 2 \cdot 10^5$$$, $$$1 \le m \le \min(\frac{n\cdot(n - 1)}{2}, 2 \cdot 10^5)$$$) — the number of mountains and the number of roads between them, respectively.

The second line contains $$$n$$$ integers $$$h_1, h_2, h_3, \dots, h_n$$$ ($$$1 \le h_i \le 10^9$$$) — the heights of the mountains.

The next $$$m$$$ lines contain two integers $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le n$$$, $$$u \ne v$$$) — the numbers of the mountains connected by a road. It is guaranteed that no road appears twice.

The next line contains an integer $$$q$$$ ($$$1 \le q \le 2 \cdot 10^5$$$) — the number of queries.

The following $$$q$$$ lines contain three numbers $$$a$$$, $$$b$$$, and $$$e$$$ ($$$1 \le a, b \le n$$$, $$$0 \le e \le 10^9$$$) — the initial and final mountains of the route, and the amount of energy, respectively.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$. The same guarantee applies to $$$m$$$ and $$$q$$$.

Output format:
For each query, output "YES" if Vlad can construct a route from mountain $$$a$$$ to mountain $$$b$$$, and "NO" otherwise.

You can output the answer in any case (for example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as a positive answer).

In the examples below, the answers for different test cases are separated by an empty line, which you do not need to output.

Constraints:
Time limit: 5.0 s
Memory limit: 256.0 MB

Example input:
2
7 7
1 5 3 4 2 4 1
1 4
4 3
3 6
3 2
2 5
5 6
5 7
5
1 1 3
6 2 0
4 7 0
1 7 4
1 7 2
6 5
4 7 6 2 5 1
1 3
5 3
1 5
2 4
6 2
5
1 5 1
1 3 1
1 2 1000
6 2 6
6 2 5

Example output:
YES
NO
YES
YES
NO

YES
NO
NO
YES
NO

Example input:
2
3 2
1 3 9
1 2
2 3
5
1 1 1
3 2 2
1 1 2
3 3 0
1 2 1
3 3
1 4 1
1 2
2 3
1 3
5
3 3 9
1 3 6
1 1 2
3 3 6
3 3 4

Example output:
YES
YES
YES
YES
NO

YES
YES
YES
YES
YES

Editorial:
Let's consider the change in energy when traveling from $$$i \rightarrow j \rightarrow k$$$, $$$h_i - h_j + h_j - h_k = h_i - h_k$$$, it can be seen that this is the difference between the heights of the first and last mountains on the path. In other words, from vertex $$$a$$$, it is possible to reach any vertex for which there is a path that does not pass through vertices with a height greater than $$$h_a+e$$$.
Therefore, for each query, it is necessary to construct a component from vertex $$$a$$$, in which all vertices with a height not greater than $$$h_a + e$$$ are included, and check if vertex $$$b$$$ lies within it. To do this efficiently, let's sort the queries by $$$h_a + e$$$, and the edges of the graph by $$$\max(h_u, h_v)$$$, and maintain a disjoint set data structure (DSU).
Before each query, add all edges that have not been added yet and their $$$\max(h_u, h_v)$$$ is not greater than $$$h_a+e$$$ for that specific query. After this, it remains to only check if vertices $$$a$$$ and $$$b$$$ belong to the same connected component.