A14161 | Odd Mineral Resource

In Homer's country, there are $n$ cities numbered $1$ to $n$ and they form a tree. That is, there are $(n-1)$ undirected roads between these $n$ cities and every two cities can reach each other through these roads.

Homer's country is an industrial country, and each of the $n$ cities in it contains some mineral resource. The mineral resource of city $i$ is labeled $a_i$ .

Homer is given the plans of the country in the following $q$ years. The plan of the $i$ -th year is described by four parameters $u_i, v_i, l_i$ and $r_i$ , and he is asked to find any mineral resource $c_i$ such that the following two conditions hold:

- mineral resource $c_i$ appears an odd number of times between city $u_i$ and city $v_i$ ; and
- $l_i \leq c_i \leq r_i$ .

As the best friend of Homer, he asks you for help. For every plan, find any such mineral resource $c_i$ , or tell him that there doesn't exist one.

The first line contains two integers $n$ ( $1 \leq n \leq 3 \cdot 10^5$ ) and $q$ ( $1 \leq q \leq 3 \cdot 10^5$ ), indicating the number of cities and the number of plans.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ( $1 \leq a_i \leq n$ ).

Then the $i$ -th line of the following $(n-1)$ lines contains two integers $x_i$ and $y_i$ ( $1 \leq x_i, y_i \leq n$ ) with $x_i \neq y_i$ , indicating that there is a bidirectional road between city $x_i$ and city $y_i$ . It is guaranteed that the given roads form a tree.

Then the $i$ -th line of the following $q$ lines contains four integers $u_i$ , $v_i$ , $l_i$ , $r_i$ ( $1 \leq u_i \leq n$ , $1 \leq v_i \leq n$ , $1 \leq l_i \leq r_i \leq n$ ), indicating the plan of the $i$ -th year.

Print $q$ lines, the $i$ -th of which contains an integer $c_i$ such that

- $c_i = {-1}$ if there is no such mineral resource that meets the required condition; or
- $c_i$ is the label of the chosen mineral resource of the $i$ -th year. The chosen mineral resource $c_i$ should meet those conditions in the $i$ -th year described above in the problem statement. If there are multiple choices of $c_i$ , you can print any of them.