E. В ловушке
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Леха попал в дерево из n вершин с корнем в вершине под номером 1. На каждой вершине i написано целое число ai. Его не выпустят пока он не ответит на q запросов вида u v. Ответ на запрос это максимальное значение , среди всех вершин i на пути от u до v, включая u и v, где dist(i, v) — количество рёбер на пути от i до v. Так же гарантируется, что вершина u является предком вершины v. Лехины вкусы очень специфичны: Он считает, что вершина является предком самой себя.

Помогите Лехе выйти.

Выражение означает применение побитового исключающего ИЛИ к числам x и y.

Напомним, что вершина u является предком вершины v, если вершина u лежит на пути от корня до вершины v.

Входные данные

В первой строке содержится два целых числа n и q (1 ≤ n ≤ 5·104, 1 ≤ q ≤ 150 000) — количество вершин в дереве и количество запросов соответственно.

Следующая строка содержит n целых чисел a1, a2, ..., an (0 ≤ ai ≤ n) — числа на вершинах.

Каждая из следующих n - 1 строк содержит по два целых числа u и v (1 ≤ u, v ≤ n) — описание очередного ребра дерева.

Гарантируется, что данный граф является деревом.

Следующие q строк содержат по два целых числа u и v (1 ≤ u, v ≤ n) — описание очередного запроса. Гарантируется, что вершина u является предком вершины v.

Выходные данные

Выведите q строк — ответы на запросы.

Примеры
Входные данные
5 3
0 3 2 1 4
1 2
2 3
3 4
3 5
1 4
1 5
2 4
Выходные данные
3
4
3
Входные данные
5 4
1 2 3 4 5
1 2
2 3
3 4
4 5
1 5
2 5
1 4
3 3
Выходные данные
5
5
4
3