弗拉德决定去山里旅行。他计划在 $$$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 \le t \le 10^4$$$) — 测试用例的数量。
测试用例的描述如下。
每个测试用例的第一行包含两个数字 $$$n$$$ 和 $$$m$$$ ($$$2 \le n \le 2 \cdot 10^5$$$, $$$1 \le m \le \min(\frac{n\cdot(n - 1)}{2}, 2 \cdot 10^5)$$$) — 山脉数量和山脉之间的道路数量他们分别。
第二行包含 $$$n$$$ 整数 $$$h_1, h_2, h_3, \dots, h_n$$$ ($$$1 \le h_i \le 10^9$$$) — 山脉的高度。
接下来的 $$$m$$$ 行包含两个整数 $$$u$$$ 和 $$$v$$$ ($$$1 \le u, v \le n$$$, $$$u \ne v$$$) — 由道路连接的山脉的数量。保证没有道路出现两次。
下一行包含一个整数 $$$q$$$ ($$$1 \le q \le 2 \cdot 10^5$$$) — 查询数。
以下 $$$q$$$ 行包含三个数字 $$$a$$$、$$$b$$$ 和 $$$e$$$ ($$$1 \le a, b \le n$$$, $$$0 \le e \le 10^9$$$) - 分别是路线的初始和最终山脉以及能量值。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。同样的保证适用于 $$$m$$$ 和 $$$q$$$。
输出
对于每个查询,如果 Vlad 可以构建从山 $$$a$$$ 到山 $$$b$$$ 的路线,则输出“YES”,否则输出“NO”。
您可以在任何情况下输出答案(例如,字符串“yEs”、“yes”、“Yes”和“YES”将被识别为肯定答案)。
在下面的示例中,不同测试用例的答案用空行分隔,您不需要输出。
示例
输入 #1
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
输出 #1
YES NO YES YES NO YES NO NO YES NO
输入 #2
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
输出 #2
YES YES YES YES NO YES YES YES YES YES
输入 #3
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
输出 #3
YES YES YES YES YES