310561: CF1851G. Vlad and the Mountains

G. Vlad and the Mountainstime limit per test5 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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

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

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.

ExamplesInput

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

Output

YES
NO
YES
YES
NO

YES
NO
NO
YES
NO

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

Output

YES
YES
YES
YES
NO

YES
YES
YES
YES
YES

Input

1
6 10
7 9 2 10 8 6
4 2
6 1
4 5
3 5
6 4
1 3
2 6
6 5
1 2
3 6
5
4 4 8
3 3 1
5 5 9
2 1 7
6 6 10

Output

YES
YES
YES
YES
YES

**题目大意：**

Vlad决定去山上旅行。他计划在n座山之间移动，其中一些山通过道路相连。第i座山的高度为h_i。

如果第i座山和第j座山之间有道路，Vlad可以通过消耗h_j - h_i单位的能量从第i座山移动到第j座山。如果他在过渡期间能量下降到零以下，他将无法从第i座山移动到第j座山。注意，h_j - h_i可以是负数，此时能量将得到恢复。

Vlad想要考虑不同的路线选项，所以他请你回答以下查询：在初始有e单位能量的情况下，是否可以构造从山a开始到山b结束的路线？

**输入数据格式：**

第一行包含一个整数t（1 ≤ t ≤ 10^4）——测试用例的数量。

接下来是t个测试用例的描述。

每个测试用例的第一行包含两个数字n和m（2 ≤ n ≤ 2 * 10^5，1 ≤ m ≤ min(n(n - 1)/2, 2 * 10^5)）——山的数量和山之间的道路数量。

第二行包含n个整数h_1, h_2, h_3, …, h_n（1 ≤ h_i ≤ 10^9）——山的高度。

接下来的m行每行包含两个整数u和v（1 ≤ u, v ≤ n，u ≠ v）——通过道路连接的山编号。保证没有重复的道路。

接下来一行包含一个整数q（1 ≤ q ≤ 2 * 10^5）——查询的数量。

接下来的q行每行包含三个数字a、b和e（1 ≤ a, b ≤ n，0 ≤ e ≤ 10^9）——路线的初始和最终山以及能量数量。

**输出数据格式：**

对于每个查询，如果Vlad可以构造从山a到山b的路线，输出“YES”，否则输出“NO”。

输出答案时大小写不敏感，即“yEs”、“yes”、“Yes”和“YES”都会被视为肯定答案。

测试用例之间输出的答案用空行分隔，但你不需输出这些空行。**题目大意：** Vlad决定去山上旅行。他计划在n座山之间移动，其中一些山通过道路相连。第i座山的高度为h_i。 如果第i座山和第j座山之间有道路，Vlad可以通过消耗h_j - h_i单位的能量从第i座山移动到第j座山。如果他在过渡期间能量下降到零以下，他将无法从第i座山移动到第j座山。注意，h_j - h_i可以是负数，此时能量将得到恢复。 Vlad想要考虑不同的路线选项，所以他请你回答以下查询：在初始有e单位能量的情况下，是否可以构造从山a开始到山b结束的路线？ **输入数据格式：** 第一行包含一个整数t（1 ≤ t ≤ 10^4）——测试用例的数量。 接下来是t个测试用例的描述。 每个测试用例的第一行包含两个数字n和m（2 ≤ n ≤ 2 * 10^5，1 ≤ m ≤ min(n(n - 1)/2, 2 * 10^5)）——山的数量和山之间的道路数量。 第二行包含n个整数h_1, h_2, h_3, …, h_n（1 ≤ h_i ≤ 10^9）——山的高度。 接下来的m行每行包含两个整数u和v（1 ≤ u, v ≤ n，u ≠ v）——通过道路连接的山编号。保证没有重复的道路。 接下来一行包含一个整数q（1 ≤ q ≤ 2 * 10^5）——查询的数量。 接下来的q行每行包含三个数字a、b和e（1 ≤ a, b ≤ n，0 ≤ e ≤ 10^9）——路线的初始和最终山以及能量数量。 **输出数据格式：** 对于每个查询，如果Vlad可以构造从山a到山b的路线，输出“YES”，否则输出“NO”。 输出答案时大小写不敏感，即“yEs”、“yes”、“Yes”和“YES”都会被视为肯定答案。 测试用例之间输出的答案用空行分隔，但你不需输出这些空行。