In a Trap

有一颗以1为根的树，每个点上有一个点权ai，每次询问路径u到v上最大的 $ai \bigoplus dist(i,v) $，保证u为v的祖先

Lech got into a tree consisting of $ n $ vertices with a root in vertex number $ 1 $ . At each vertex $ i $ written integer $ a_{i} $ . He will not get out until he answers $ q $ queries of the form $ u $ $ v $ . Answer for the query is maximal value  among all vertices $ i $ on path from $ u $ to $ v $ including $ u $ and $ v $ , where $ dist(i,v) $ is number of edges on path from $ i $ to $ v $ . Also guaranteed that vertex $ u $ is ancestor of vertex $ v $ . Leha's tastes are very singular: he believes that vertex is ancestor of itself. Help Leha to get out. The expression  means the bitwise exclusive OR to the numbers $ x $ and $ y $ . Note that vertex $ u $ is ancestor of vertex $ v $ if vertex $ u $ lies on the path from root to the vertex $ v $ .

First line of input data contains two integers $ n $ and $ q $ ( $ 1<=n<=5·10^{4} $ , $ 1<=q<=150000 $ ) — number of vertices in the tree and number of queries respectively. Next line contains $ n $ integers $ a_{1},a_{2},...,a_{n} $ ( $ 0<=a_{i}<=n $ ) — numbers on vertices. Each of next $ n-1 $ lines contains two integers $ u $ and $ v $ ( $ 1<=u,v<=n $ ) — description of the edges in tree. Guaranteed that given graph is a tree. Each of next $ q $ lines contains two integers $ u $ and $ v $ ( $ 1<=u,v<=n $ ) — description of queries. Guaranteed that vertex $ u $ is ancestor of vertex $ v $ .

Output $ q $ lines — answers for a queries.

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