codeforces#P1479D. Odd Mineral Resource

    ID: 31794 远端评测题 5000ms 1024MiB 尝试: 0 已通过: 0 难度: 10 上传者: 标签>binary searchbitmasksbrute forcedata structuresprobabilitiestrees*2900

Odd Mineral Resource

Description

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.

Input

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.

Output

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.

Samples

6 8
3 2 1 3 1 3
1 2
1 3
2 4
2 5
4 6
3 5 1 1
3 5 1 3
3 5 1 3
1 1 2 2
1 1 3 3
1 4 1 5
1 6 1 3
1 6 1 3
-1
2
3
-1
3
2
2
3

Note

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.