XOR, Sets, Trees, and Queries

For a finite set $S$ of positive integers, $f(S)$ is defined as the smallest finite set that satisfies the following conditions. Exactly one such set exists.

• $S \subseteq f(S)$.
• For any positive integers $x$ and $y$, if $x, y \in f(S)$ and $x \neq y$, then $x \oplus y \in f(S)$. Here $\oplus$ is the bitwise XOR.
• For any positive integer $x$, if $x \in f(S)$ and $x < 2^{1000}$, then $2x \in f(S)$.
• For any positive integer $x$, if $2x \in f(S)$ and $x < 2^{1000}$, then $x \in f(S)$.

A tree has $N$ vertices. For every $i$ ($1 \le i \le N$), vertex $i$ has a positive integer $A_i$ written on it. You must process $Q$ queries.

For a query $u, v$, let $P$ be the set of vertices on the shortest path from vertex $u$ to vertex $v$. Output the minimum element of the set $f(\{A_r \mid r \in P\})$.

The first line contains the number of vertices $N$ and the number of queries $Q$, separated by a space.

The second line contains the positive integers $A_1, A_2, \ldots, A_N$ written on the vertices, separated by spaces.

From the third line, the next $N - 1$ lines each contain two vertex numbers $a$ and $b$, separated by a space, that are connected by an edge of the tree.

From line $N + 2$, the next $Q$ lines each contain two integers $u$ and $v$, separated by a space, that describe a query.

For each query, print the answer on its own line. Print $Q$ lines in total.

• $1 \le N, Q \le 100{,}000$
• $0 < A_i < 2^{30}$ ($1 \le i \le N$)
• In every query, $1 \le u, v \le N$