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/A

N/A

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.