Description

Country A has $n$ cities connected by $n - 1$ roads, so that any two cities are mutually reachable and the path between them is unique. Each city has a lucky number, which stands at the very center of the city in the form of a monument, serving as the symbol of the city.

Some travelers want to tour Country A. A traveler plans to land in city $x$, travel along the unique path from city $x$ to city $y$, and finally depart from city $y$. When passing through each city, the traveler has a chance to take a photo with that city's lucky number, thereby keeping this luck. However, luck cannot be simply stacked, and the traveler knows this well. They believe that luck is kept on them via xor.

For example, if a traveler takes $3$ photos with lucky values $5, 7, 11$, then the lucky value finally kept is $5 \operatorname{xor} 7 \operatorname{xor} 11 = 9$.

Some smart travelers have found that by selectively taking photos, they can obtain a larger lucky value. For instance, among the three lucky values above, if they only choose $5$ and $11$, the lucky value kept is $14$. Now, some travelers have come to you for help. Given their itineraries, please compute the maximum lucky value they can keep.

Input Format

The first line contains $2$ positive integers $n, q$, denoting the number of cities and the number of travelers.

The second line contains $n$ non-negative integers, where the $i$-th integer $G_i$ denotes the lucky value of city $i$.

The next $n - 1$ lines each contain two positive integers $x, y$, indicating that there is a road between city $x$ and city $y$.

The next $q$ lines each contain two positive integers $x, y$, indicating that this traveler’s plan is to go from city $x$ to city $y$.

Output Format

Output $q$ lines. Each line contains one non-negative integer, the maximum lucky value that this traveler can keep.

4 2
11 5 7 9
1 2
1 3
1 4
2 3
1 4

14 
11

Hint

For $100\%$ of the testdata, it is guaranteed that $n \leq 2 \times 10^4$, $q \leq 2 \times 10^5$, $G_i \leq 2^{60}$.

Translated by ChatGPT 5