Codeforces Round 888 (Div. 3) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

binary search

data structures

dsu

graphs

implementation

sortings

trees

two pointers

*2000

No tag edit access

The problem statement has recently been changed. View the changes.

×
G. Vlad and the Mountains

time limit per test

5 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputVlad 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.

Examples

Input

27 71 5 3 4 2 4 11 44 33 63 22 55 65 751 1 36 2 04 7 01 7 41 7 26 54 7 6 2 5 11 35 31 52 46 251 5 11 3 11 2 10006 2 66 2 5

Output

YES NO YES YES NO YES NO NO YES NO

Input

23 21 3 91 22 351 1 13 2 21 1 23 3 01 2 13 31 4 11 22 31 353 3 91 3 61 1 23 3 63 3 4

Output

YES YES YES YES NO YES YES YES YES YES

Input

16 107 9 2 10 8 64 26 14 53 56 41 32 66 51 23 654 4 83 3 15 5 92 1 76 6 10

Output

YES YES YES YES YES

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/26/2024 00:27:52 (h2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|