G. Влад и горы
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Влад решил отправиться в путешествие в горы. Всего он планирует перемещаться по $$$n$$$ горам, между некоторыми из которых есть дороги. Горы имеют высоты, высота $$$i$$$-й горы равна $$$h_i$$$.

Если между горами $$$i$$$ и $$$j$$$ есть дорога, то Влад может перейти с горы $$$i$$$ на гору $$$j$$$, потратив при этом $$$h_j - h_i$$$ единиц энергии. Если при переходе его энергия должна опуститься ниже нуля, он не сможет перейти с горы $$$i$$$ на гору $$$j$$$. Обратите внимание, что $$$h_j - h_i$$$ может быть отрицательным и тогда энергия восстановится.

Влад хочет рассмотреть разные варианты маршрута, поэтому просит вас ответить на следующие запросы: можно ли построить какой-либо маршрут, начинающийся на горе $$$a$$$ и заканчивающийся на горе $$$b$$$, если изначально у него есть $$$e$$$ единиц энергии?

Входные данные

В первой строке входных данных содержится целое число $$$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$$$.

Выходные данные

Для каждого запроса выведите «YES», если Влад может составить маршрут от горы $$$a$$$ до горы $$$b$$$, и «NO» в противном случае.

Вы можете выводить ответ в любом регистре (например, строки «yEs», «yes», «Yes» и «YES» будут распознаны как положительный ответ).

В примерах ниже ответы на разные наборы данных разделены пустой строкой, вы можете её не выводить.

Примеры
Входные данные
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
Выходные данные
YES
NO
YES
YES
NO

YES
NO
NO
YES
NO
Входные данные
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
Выходные данные
YES
YES
YES
YES
NO

YES
YES
YES
YES
YES
Входные данные
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
Выходные данные
YES
YES
YES
YES
YES