In a tree $T$ with $N$ nodes, each node has a value $A[i]$. You are given $Q$ queries of the form $u \ \ v$. For each query, we need to find the value of function $F$.

Function $F$ is defined as the sum of the Bitwise OR and XOR operations on the values of nodes in a simple path between nodes $u$ and $v$.

To simplify, you need to calculate the sum of OR and XOR of the values of nodes on the path between $u$ and $v$ for each query.

Input Format:

• The first line contains two space-separated integers $N$ and $Q$.
• The next $N-1$ lines contain two space-separated integers $u \ \ v$ denoting the edge between node $u$ and node $v$.
• The next line contains $N$ space-separated integers denoting the value of nodes.
• The next $Q$ lines contain two space-separated integers, $u \ \ v$.

Output Format:
For every query output the value of function $F$

Constraints:

$1 \le N \le 2 \times 10^5 \\ 1 \le Q, A[i] \le 10^5 \\ 1 \leq u,v \leq N$