Леха попал в дерево из 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.
Выходные данные
Выведите q строк — ответы на запросы.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 3
0 3 2 1 4
1 2
2 3
3 4
3 5
1 4
1 5
2 4
|
3
4
3
|
|
2
|
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
|