Codeforces Round 700 (Div. 1) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

binary search

bitmasks

brute force

data structures

probabilities

trees

*2900

No tag edit access

The problem statement has recently been changed. View the changes.

×
D. Odd Mineral Resource

time limit per test

5 secondsmemory limit per test

1024 megabytesinput

standard inputoutput

standard 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.

Input

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.

Output

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.

Example

Input

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 3

Note

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.

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/01/2023 12:24:02 (l1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|