В стране Гомера есть \(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\) или скажите, что его нет.
Выходные данные
Выведите \(q\) строк, \(i\)-я из которых содержит целое число \(c_i\), такое, что
- \(c_i = {-1}\), если нет такого минерального ресурса, который соответствовал бы требуемому условию; или
- \(c_i\) — это номер выбранного минерального ресурса в \(i\)-м году. Выбранный минеральный ресурс \(c_i\) должен удовлетворять условиям \(i\)-го года, описанным выше в условии задачи. Если есть несколько подходящих \(c_i\), вы можете вывести любой из них.
Примечание
В первых трех запросах четыре города находятся между городом \(3\) и городом \(5\), а именно: город \(1\), город \(2\), город \(3\) и город \(5\). В них представлены минеральные ресурсы \(1\) (появляется в городах \(3\) и \(5\)), \(2\) (появляется в городе \(2\)) и \(3\) (появляется в городе \(1\)). Следует отметить, что
- Первый запрос заключается только в том, чтобы проверить, появляется ли минеральный источник \(1\) нечетное количество раз между городом \(3\) и городом \(5\). Ответ — нет, потому что минеральный источник \(1\) появляется дважды (четное число раз) между городом \(3\) и городом \(5\).
- Второй и третий запросы одинаковы, но они могут выбирать разные минеральные ресурсы. Вы можете выбрать любой из \(2\) и \(3\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|