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.

在荷马的国家中，有 $n$ 座城市，编号为 $1$ 到 $n$，它们构成一棵树。也就是说，这 $n$ 座城市之间有 $(n-1)$ 条无向道路，且任意两座城市均可通过这些道路相互到达。

荷马的国家是一个工业国，其中每座城市都蕴藏某种矿产资源。城市 $i$ 的矿产资源标记为 $a_i$。

荷马获得了该国未来 $q$ 年的发展规划。第 $i$ 年的规划由四个参数 $u_i, v_i, l_i$ 和 $r_i$ 描述，他需要找出任意一种矿产资源 $c_i$，使得以下两个条件同时成立：

• 矿产资源 $c_i$ 在城市 $u_i$ 与城市 $v_i$ 之间的路径上出现奇数次；
• $l_i \leq c_i \leq r_i$。

作为荷马最好的朋友，他向你求助。对每一项规划，请找出满足条件的任意一个矿产资源 $c_i$；若不存在这样的资源，则告知他不存在。

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.

第一行包含两个整数 $n$（$1 \leq n \leq 3 \cdot 10^5$）和 $q$（$1 \leq q \leq 3 \cdot 10^5$），分别表示城市的数量和计划的数量。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \leq a_i \leq n$）。

接下来的 $(n-1)$ 行中，第 $i$ 行包含两个整数 $x_i$ 和 $y_i$（$1 \leq x_i, y_i \leq n$），满足 $x_i \neq y_i$，表示城市 $x_i$ 与城市 $y_i$ 之间存在一条双向道路。保证所给道路构成一棵树。

再接下来的 $q$ 行中，第 $i$ 行包含四个整数 $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$），表示第 $i$ 年的计划。

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.

输出 $q$ 行，其中第 $i$ 行包含一个整数 $c_i$，满足以下条件：

• 若不存在满足要求的矿产资源，则 $c_i = {-1}$；
• 否则，$c_i$ 为第 $i$ 年所选矿产资源的编号。所选矿产资源 $c_i$ 必须满足题目描述中第 $i$ 年所规定的上述条件。若存在多个满足条件的 $c_i$，可任选其一输出。

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.

在前三次查询中，城市 $3$ 与城市 $5$ 之间共有四座城市，即城市 $1$、城市 $2$、城市 $3$ 和城市 $5$。这些城市中出现的矿产资源包括：矿产资源 $1$（出现在城市 $3$ 和城市 $5$ 中）、矿产资源 $2$（出现在城市 $2$ 中）以及矿产资源 $3$（出现在城市 $1$ 中）。需注意：

• 第一次查询仅需判断矿产资源 $1$ 在城市 $3$ 与城市 $5$ 之间是否出现了奇数次。答案是否定的，因为矿产资源 $1$ 在城市 $3$ 与城市 $5$ 之间共出现了两次（偶数次）。
• 第二次与第三次查询内容相同，但可选择不同的矿产资源。矿产资源 $2$ 与矿产资源 $3$ 均可选用。