Dexter has recently constructed a random generator. This generator works on a tree of N nodes. The information about the tree has to be fed into the generator in order for it to start working.

Each node, u of the tree has a value $A[u]$ associated with it. The generator works as follows:

It takes as input two integers, u and v. It then outputs two integers X and Y. X can be either $A[u]$ or $A[v]$, with equal probability. Now, the generator selects a node i randomly and with equal probability from the path $u-v$ (including u and v) in the tree and outputs the value of Y as $A[i]$.

Let the above process be denoted by: $Process(u,v)$, which takes input a pair of integers and outputs a pair of integers $(X,Y)$.

Now, Hannah has been invited to test the random generator constructed by Dexter. Hannah has Q questions. Each question is as follows:

Hannah selects two nodes u and v of the tree. She wants to know the maximum value of $Query(u,v)$.

$Query(u,v)$ is defined below:

Query(u,v):
    (X1,Y1) = Process(u,v)
    (X2,Y2) = Process(u,v)
    A = X1 ^ Y1
    B = X2 ^ Y2
    return abs(A-B)

Dexter needs your help in answering the questions of Hannah.

Input

First line of the input contains two integers N and Q, the number of nodes in the tree and the number of questions that Hannah asks from Dexter, respectively.
Next line contains N space separated positive integers, where i^$th$ integer denotes the value at i^$th$ node, i.e., $A[i]$.
Next $N-1$ lines describe the structure of the tree. Each of these lines contain two space separated integers p and q. There is an undirected edge between p and q.
Next Q lines, each line denoting a question from Hannah, which contains two space separated integers u and v, which means that Hannah has chosen these two nodes for that query.

Output

You are supposed to output Q lines. The i^$th$ line contains the answer for the i^$th$ query.

Constraints

$1 \le N \le 10$⁵
$1 \le Q \le 10$⁵
$1 \le A[i] \le 10$⁹
$1 \le p , q \le N$
$1 \le u , v \le N$