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.