F. Trees and XOR Queries Again
time limit per test
6.5 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

You are given a tree consisting of $$$n$$$ vertices. There is an integer written on each vertex; the $$$i$$$-th vertex has integer $$$a_i$$$ written on it.

You have to process $$$q$$$ queries. The $$$i$$$-th query consists of three integers $$$x_i$$$, $$$y_i$$$ and $$$k_i$$$. For this query, you have to answer if it is possible to choose a set of vertices $$$v_1, v_2, \dots, v_m$$$ (possibly empty) such that:

  • every vertex $$$v_j$$$ is on the simple path between $$$x_i$$$ and $$$y_i$$$ (endpoints can be used as well);
  • $$$a_{v_1} \oplus a_{v_2} \oplus \dots \oplus a_{v_m} = k_i$$$, where $$$\oplus$$$ denotes the bitwise XOR operator.
Input

The first line contains one integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$).

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 2^{20} - 1$$$).

Then $$$n-1$$$ lines follow. Each of them contains two integers $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le n$$$; $$$u \ne v$$$) denoting an edge of the tree.

The next line contains one integer $$$q$$$ ($$$1 \le q \le 2 \cdot 10^5$$$) — the number of queries.

Then $$$q$$$ lines follow. The $$$i$$$-th of them contains three integers $$$x_i$$$, $$$y_i$$$ and $$$k_i$$$ ($$$1 \le x_i, y_i \le n$$$; $$$0 \le k_i \le 2^{20} - 1$$$).

Output

For each query, print YES if it is possible to form a set of vertices meeting the constraints. Otherwise, print NO.

You can print each letter in any case.

Example
Input
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
Output
YES
YES
NO
YES
YES
NO
YES
YES