Изменения рейтингов за последние раунды временно удалены. Скоро они будут возвращены. ×

F. Снова деревья и XOR-запросы
ограничение по времени на тест
6.5 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дано дерево, состоящее из $$$n$$$ вершин. На каждой вершине написано целое число; на $$$i$$$-й вершине написано число $$$a_i$$$.

Вам необходимо обработать $$$q$$$ запросов. $$$i$$$-й запрос состоит из трех целых чисел $$$x_i$$$, $$$y_i$$$ и $$$k_i$$$. Для этого запроса вы должны ответить, возможно ли выбрать набор вершин $$$v_1, v_2, \dots, v_m$$$ (возможно, пустой) так, чтобы:

  • каждая вершина $$$v_j$$$ находилась на простом пути между $$$x_i$$$ и $$$y_i$$$ (в том числе можно использовать концы пути);
  • $$$a_{v_1} \oplus a_{v_2} \oplus \dots \oplus a_{v_m} = k_i$$$, где $$$\oplus$$$ обозначает оператор побитового исключающего ИЛИ.
Входные данные

Первая строка содержит одно целое число $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$).

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 2^{20} - 1$$$).

Затем следуют $$$n-1$$$ строк. Каждая из них содержит два целых числа $$$u$$$ и $$$v$$$ ($$$1 \le u, v \le n$$$; $$$u \ne v$$$), обозначающие ребро дерева.

Следующая строка содержит одно целое число $$$q$$$ ($$$1 \le q \le 2 \cdot 10^5$$$) — количество запросов.

Затем следуют $$$q$$$ строк. В $$$i$$$-й из них содержатся три целых числа $$$x_i$$$, $$$y_i$$$ и $$$k_i$$$ ($$$1 \le x_i, y_i \le n$$$; $$$0 \le k_i \le 2^{20} - 1$$$).

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

Для каждого запроса выведите YES, если возможно сформировать набор вершин, удовлетворяющий ограничениям. В противном случае выведите NO.

Каждую букву можно выводить в любом регистре.

Пример
Входные данные
4
0 1 2 10
2 1
3 2
4 2
8
3 3 0
3 4 1
3 4 7
1 3 1
1 3 2
1 3 10
1 4 10
1 4 11
Выходные данные
YES
YES
NO
YES
YES
NO
YES
YES