D. Странный источник минералов
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

В стране Гомера есть $$$n$$$ городов с номерами от $$$1$$$ до $$$n$$$, которые образуют дерево. Иначе говоря, между этими $$$n$$$ городами есть $$$(n-1)$$$ неориентированных дорог, и с каждого города можно попасть в любой другой по этим дорогам.

Страна Гомера — индустриальная страна, и каждый из $$$n$$$ городов в ней содержит некоторый минеральный ресурс. Минеральный ресурс города $$$i$$$ обозначен как $$$a_i$$$.

Гомеру даны планы страны на $$$q$$$ следующих лет. План $$$i$$$-го года описывается четырьмя параметрами $$$u_i, v_i, l_i$$$ и $$$r_i$$$, и он должен найти любой такой минеральный ресурс $$$c_i$$$ такой, что выполняются два условия:

  • минеральный ресурс $$$c_i$$$ встречается нечетное количество раз между городами $$$u_i$$$ и $$$v_i$$$;
  • $$$l_i \leq c_i \leq r_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$$$, такое, что

  • $$$c_i = {-1}$$$, если нет такого минерального ресурса, который соответствовал бы требуемому условию; или
  • $$$c_i$$$ — это номер выбранного минерального ресурса в $$$i$$$-м году. Выбранный минеральный ресурс $$$c_i$$$ должен удовлетворять условиям $$$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$$$). Следует отметить, что

  • Первый запрос заключается только в том, чтобы проверить, появляется ли минеральный источник $$$1$$$ нечетное количество раз между городом $$$3$$$ и городом $$$5$$$. Ответ — нет, потому что минеральный источник $$$1$$$ появляется дважды (четное число раз) между городом $$$3$$$ и городом $$$5$$$.
  • Второй и третий запросы одинаковы, но они могут выбирать разные минеральные ресурсы. Вы можете выбрать любой из $$$2$$$ и $$$3$$$.