Codeforces Round 700 (Div. 1) |
---|
Закончено |
В стране Гомера есть $$$n$$$ городов с номерами от $$$1$$$ до $$$n$$$, которые образуют дерево. Иначе говоря, между этими $$$n$$$ городами есть $$$(n-1)$$$ неориентированных дорог, и с каждого города можно попасть в любой другой по этим дорогам.
Страна Гомера — индустриальная страна, и каждый из $$$n$$$ городов в ней содержит некоторый минеральный ресурс. Минеральный ресурс города $$$i$$$ обозначен как $$$a_i$$$.
Гомеру даны планы страны на $$$q$$$ следующих лет. План $$$i$$$-го года описывается четырьмя параметрами $$$u_i, v_i, l_i$$$ и $$$r_i$$$, и он должен найти любой такой минеральный ресурс $$$c_i$$$ такой, что выполняются два условия:
Так как вы лучший друг Гомера, он просит вас о помощи. Для каждого плана найдите любой такой минерал $$$c_i$$$ или скажите, что его нет.
Первая строка содержит два целых числа $$$n$$$ ($$$1 \leq n \leq 3 \cdot 10^5$$$) и $$$q$$$ ($$$1 \leq q \leq 3 \cdot 10^5$$$) — количество городов и количество планов соответственно.
Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \leq a_i \leq n$$$).
$$$i$$$-я строка из следующих $$$(n-1)$$$ строк содержит два целых числа $$$x_i$$$ и $$$y_i$$$ ($$$1 \leq x_i, y_i \leq n$$$) с $$$x_i \neq y_i$$$, обозначающие дорогу между городами $$$x_i$$$ и $$$y_i$$$. Гарантируется, что данные дороги образуют дерево.
$$$i$$$-я строка из следующих $$$q$$$ строк содержит четыре целых числа $$$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$$$), указывающие на план города в $$$i$$$-й год.
Выведите $$$q$$$ строк, $$$i$$$-я из которых содержит целое число $$$c_i$$$, такое, что
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
В первых трех запросах четыре города находятся между городом $$$3$$$ и городом $$$5$$$, а именно: город $$$1$$$, город $$$2$$$, город $$$3$$$ и город $$$5$$$. В них представлены минеральные ресурсы $$$1$$$ (появляется в городах $$$3$$$ и $$$5$$$), $$$2$$$ (появляется в городе $$$2$$$) и $$$3$$$ (появляется в городе $$$1$$$). Следует отметить, что
Название |
---|