given the plans of the country in the accompanying q years. The arrangement of the I-th year is portrayed by four boundaries ui,vi,li and ri, and he is approached to track down any mineral asset ci to such an extent that the accompanying two conditions hold: mineral asset ci seems an odd number of times between city ui and city vi; and
Correct answer will be upvoted else downvoted. Computer science.
Homer is given the plans of the country in the accompanying q years. The arrangement of the I-th year is portrayed by four boundaries ui,vi,li and ri, and he is approached to track down any mineral asset ci to such an extent that the accompanying two conditions hold:
mineral asset ci seems an odd number of times between city ui and city vi; and
li≤ci≤ri.
As the closest companion of Homer, he asks you for help. For each arrangement, track down any such mineral asset ci, or let him know that there doesn't exist one.
Input
The main line contains two integers n (1≤n≤3⋅105) and q (1≤q≤3⋅105), demonstrating the number of urban areas and the number of plans.
The subsequent line contains n integers a1,a2,… ,an (1≤
Then, at that point, the I-th line of the accompanying (n−1) lines contains two integers xi and yi (1≤xi,yi≤n) with xi≠yi, demonstrating that there is a bidirectional street between city xi and city yi. It is ensured that the given streets structure a tree.
Then, at that point, the I-th line of the accompanying q lines contains four integers ui, vi, li, ri (1≤ui≤n, 1≤vi≤n, 1≤li≤ri≤n), showing the arrangement of the I-th year.
Output
Print q lines, the I-th of which contains an integer ci to such an extent that
ci=−1 in case there is no such mineral asset that meets the necessary condition; or
ci is the mark of the picked mineral asset of the I-th year. The picked mineral asset ci should meet those conditions in the I-th year depicted above in the issue articulation.
Step by step
Solved in 3 steps with 1 images
