B'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 <= t <= 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 <= n <= 2 cdot 10^5 , 1 <= m <= 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, ... , h_n ( 1 <= h_i <= 10^9 ) -- the heights of the mountains. The next m lines contain two integers u and v ( 1 <= u, v <= 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 <= q <= 2 cdot 10^5 ) -- the number of queries. The following q lines contain three numbers a , b , and e ( 1 <= a, b <= n , 0 <= e <= 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 $'...