E. XOR on Tree
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

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.

Input

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.

Output

For each query, print a single integer in a line — the maximum value of XOR.

Examples
Input
5
1 3 3 2 1
1 2
1 3
2 4
2 5
3
2 3
3 2
1 2
Output
0
2
3
Input
1
114514
1
1 1
Output
0
Note

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$$$.