Consider a state with $N$ cities (numbered from $1$ to $N$) and $N-1$ roads (bidirectional). A road connects two cities. Using these roads, we can reach any city from any city. 

Each city has a single player, who has a set of cards. Each card has a non-negative number written on it. Also, the player living in the city has a non-negative number assigned. The set bits in this number, (numbered as 0, 1, 2.. from right to left) define the set of cards the player has i.e. if the $i^{th}$ bit is set, the player has the card with number $i$.(for number 7, the player will have 0th,1st and the 2nd card, because the binary representation of 7 is 111)

Now, Yashwanth (our protagonist), is planning a battle journey. Consider the following details about the expedition:
1) Initially Yashwant, doesn't have any cards.
2) He will start at city $X$ and travel along the simple path to reach city $Y$.
3)The Winner of a battle will have the $i^{th}$ card, if and only if, EXACTLY ONE of the players battling, has the $i^{th}$ card.

In order to plan correctly, and earn as many cards as possible, Yashwant wants to know the cards he will have at the end of each journey.
ASSUMING that Yashwanth wins at each city, answer the queries below. 
NOTE: The answer to each query is a number, $i^{th}$ bit of which will be set if Yashwant will have the $i^{th}$ card at the end of the journey.
NOTE: Queries are independent and don't affect the cards of the losing player.

Input:
The first line of input will have $N$ and $Q$(number of cities and queries respectively) ($1 \leq N,Q \leq10^5$)
The second line will have $N$ numbers, representing the number of city $i$ . ($1 \leq a[i] < 2^{30}$)
The next $N-1$ lines will have two cities $A$ and $B$, connecting $A$ and $B$
Then we will have $Q$ queries, each query will have two cities $A$ and $B$ .. the starting point and the ending point

Output:
Print $Q$ lines, the $i^{th}$ line should have the answer for the $i^{th}$ query