Jontrona of Liakot

Liakot, the king of Cox's Bazar, is currently in a dire situation. His own younger sister Ayesha is conspiring with a surfer named Sohel to dethrone Liakot.

It all started from when they were mere children. Ayesha and Sohel would team up to bully poor little Liakot. Often, they would give Liakot a programming problem and laugh at his failure.

In the problem, Sohel would make a tree of $N$ nodes where the $i$-th node contains a number $A_i$. The root of the tree is the node number 1. Then Ayesha would give Liakot $Q$ queries to answer.

In each query, Ayesha would choose two nodes of the tree $U$ and $V$ ($V$ will always be in the subtree of $U$). Ayesha takes the subtree rooted at $U$ and then from that subtree, she removes the subtree rooted at $V$.

Ayesha takes all the numbers from the tree segment she made this way and does a XOR operation with $Z$ on all of these numbers (XOR is exclusive-or operation). She chooses another number $K$ in that query, and Liakot has to answer the $K$-th smallest number among Ayesha's XOR'ed numbers.

Can you help Liakot by finding the $K$-th smallest number after XOR-ing $Z$ to all the numbers which are in the subtree rooted at $U$ but not in the subtree rooted at $V$?

Input

Input starts with two space-separated integers $N$ and $Q$, representing respectively the number of nodes in the tree and the number of queries.

In the next line, $N$ space-separated integers are given, the $i$-th integer representing the number $A_i$ of the node $i$.

In the following $N-1$ lines, two integers $X$ and $Y$ are given representing an edge between nodes $X$ and $Y$ in the tree. It is guaranteed that the given tree will be a valid one.

Finally, in each of the last $Q$ lines of input, four space-separated integers $U$, $V$, $Z$ and $K$ will be given representing the queries.

Constraints:

$1 \leq N \leq 10^5$
$1 \leq Q \leq 10^6$
$1 \leq A_i, Z, K \leq 10^9$
$1 \leq X, Y \leq N$
$1 \leq U, V \leq N$

It is guaranteed that the tree will always be a valid one. In each query, $V$ will always be within the subtree rooted at $U$.

Output

For each query, print the answer in a single line. If the answer does not exist for a query, print “-1” (w/o quotes) instead in the corresponding line.

Sample

Input	Output
8 6 3 7 10 10 5 8 8 1 4 2 7 3 4 5 8 6 4 7 1 4 1 8 4 2 2 3 7 3 2 2 3 3 2 9 8 6 8 1 1 7 3 4 1 5 3 4	8 -1 -1 9 6 9
In the first query, Ayesha takes the subtree rooted at node 4 and removes the subtree rooted at node 2 from it. So, the remaining segment has the nodes 3, 4, 5 and 7 in it. The numbers in these nodes are 10, 10, 5 and 8 respectively. In the first query, $Z$ = 2. After XOR-ing $Z$ with these numbers (10, 10, 5 and 8), they become 8, 8, 7 and 10 respectively. The 3rd smallest number among them is 8, thus the answer.

Dataset is big, use fast I/O.