CF1851G Vlad and the Mountains

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?

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 $ .

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.