CF1479D.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.

In the first three queries, there are four cities between city $3$ and city $5$ , which are city $1$ , city $2$ , city $3$ and city $5$ . The mineral resources appear in them are mineral resources $1$ (appears in city $3$ and city $5$ ), $2$ (appears in city $2$ ) and $3$ (appears in city $1$ ). It is noted that

• The first query is only to check whether mineral source $1$ appears an odd number of times between city $3$ and city $5$ . The answer is no, because mineral source $1$ appears twice (an even number of times) between city $3$ and city $5$ .
• The second and the third queries are the same but they can choose different mineral resources. Both mineral resources $2$ and $3$ are available.