A11127 | In a Trap

Lech got into a tree consisting of $n$ vertices with a root in vertex number $1$ . At each vertex $i$ written integer $a_{i}$ . He will not get out until he answers $q$ queries of the form $u$ $v$ . Answer for the query is maximal value  among all vertices $i$ on path from $u$ to $v$ including $u$ and $v$ , where $dist(i,v)$ is number of edges on path from $i$ to $v$ . Also guaranteed that vertex $u$ is ancestor of vertex $v$ . Leha's tastes are very singular: he believes that vertex is ancestor of itself.

Help Leha to get out.

The expression  means the bitwise exclusive OR to the numbers $x$ and $y$ .

Note that vertex $u$ is ancestor of vertex $v$ if vertex $u$ lies on the path from root to the vertex $v$ .

First line of input data contains two integers $n$ and $q$ ( $1<=n<=5·10^{4}$ , $1<=q<=150000$ ) — number of vertices in the tree and number of queries respectively.

Next line contains $n$ integers $a_{1},a_{2},...,a_{n}$ ( $0<=a_{i}<=n$ ) — numbers on vertices.

Each of next $n-1$ lines contains two integers $u$ and $v$ ( $1<=u,v<=n$ ) — description of the edges in tree.

Guaranteed that given graph is a tree.

Each of next $q$ lines contains two integers $u$ and $v$ ( $1<=u,v<=n$ ) — description of queries. Guaranteed that vertex $u$ is ancestor of vertex $v$ .

Output $q$ lines — answers for a queries.