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\)