Вам дано дерево, состоящее из \(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\) обозначает оператор побитового исключающего ИЛИ.
Выходные данные
Для каждого запроса выведите YES, если возможно сформировать набор вершин, удовлетворяющий ограничениям. В противном случае выведите NO.
Каждую букву можно выводить в любом регистре.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|