Hile likes XOR and trees very much.
She will give you a rooted tree with $$$n$$$ vertices. The root is $$$1$$$. The vertices are numbered from $$$1$$$ to $$$n$$$. Each vertex has a weight $$$a_i$$$.
Then she will give you $$$q$$$ queries. Each query consists of two numbers $$$u,v$$$. You need to find a vertex $$$i$$$ in the subtree of $$$v$$$ to maximize the bitwise XOR of $$$a_u$$$ and $$$a_i$$$ and tell Hile the maximum value.
The first line contains one integer $$$n$$$ $$$(1 \le n \le 2 \times 10^5)$$$ — the number of vertices.
The second line contains $$$n$$$ integers $$$a_1, a_2, \dots , a_n$$$ $$$(1 \le a_i \lt 2^{30})$$$ — the weight of each vertex.
Then $$$n - 1$$$ lines follow, each containing two integers $$$u,v$$$ $$$(1 \le u,v \le n, u \ne v)$$$ denoting an edge connecting vertex $$$u$$$ with vertex $$$v$$$. It is guaranteed that these edges form a tree.
The following line contains one integer $$$q$$$ $$$(1 \le q \le 2 \times 10^5)$$$ — the number of queries.
Then $$$q$$$ lines follow, each containing two integers $$$u,v$$$ $$$(1 \le u,v \le n)$$$ denoting a query.
For each query, print a single integer in a line — the maximum value of XOR.
5 1 3 3 2 1 1 2 1 3 2 4 2 5 3 2 3 3 2 1 2
0 2 3
1 114514 1 1 1
0
This is the tree of the first sample:
For the first query, we can only choose $$$3$$$ as $$$i$$$ because it is the only vertex of the subtree of $$$3$$$. $$$a_2 \oplus a_3 = 0$$$.
For the second query, we can choose $$$2,4,5$$$ because they are in the subtree of $$$2$$$. We choose $$$5$$$ as $$$i$$$ to maximize $$$a_i \oplus a_u$$$, $$$a_5 \oplus a_3 = 2$$$.
For the last query, we choose $$$4$$$ as $$$i$$$, $$$a_4 \oplus a_1 = 3$$$.
