D. Odd Mineral Resourcetime limit per test5 secondsmemory limit per test1024 megabytesinputstandard inputoutputstandard outputIn 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.InputThe 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.OutputPrint 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. ExampleInput
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
Output
-1
2
3
-1
3
2
2
3NoteIn 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. 
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
['binary search', 'bitmasks', 'brute force', 'data structures', 'probabilities', 'trees', '*2900']