In a distant kingdom, there are $n$ towns, numbered $1$ to $n$, where town $1$ is the capital. There are $n-1$ bidirectional roads connecting the towns, all of equal length, forming a rooted tree structure where any two towns are reachable from each other.

The people of the kingdom belong to several families. Due to historical reasons, they live in a peculiar way: for each family, all members live at the same distance from the capital; furthermore, for any set of towns at the same distance from the capital, all towns in that set are inhabited by members of the same family. Consequently, the number of families in the kingdom is equal to the depth of the tree, and each family occupies all towns at a specific depth.

This is a kingdom rich in gems, and gem export is the pillar industry. However, gem mining requires luck, so the people invented a divination ritual to predict gem production using the current gem inventory in each town. The ritual is initiated by a town $x$. All towns in the subtree of $x$ that are at a distance of at most $L$ from $x$ send a representative, carrying all the gems from their town, to town $x$. Here, the gem inventories of each family are piled together, forming at most $L+1$ piles of gems. Then, two priests representing luck and misfortune take turns, each removing at least one gem from a non-empty pile until the last gem is removed. The priest who takes the last gem wins, and the power they represent will determine the harvest for the coming period. The priests are extremely intelligent and act according to their optimal strategies. After the ritual, all gems are returned to their original towns.

As anyone with common sense would realize, this is actually a game of Nim, and the final result is determined by the XOR sum of the number of gems in all piles. Being clever, you have received a total of $m$ messages, each indicating either a divination ritual performed in a town or a change in the gem inventory of a town. You need to calculate this XOR sum for each divination ritual.

Input

The first line contains two positive integers $n$ and $m$, representing the number of towns and the number of messages to process.

The second line contains $n$ non-negative integers $c_1, c_2, \ldots, c_n$, where $c_i$ is the initial gem inventory of town $i$.

The next $n-1$ lines each contain two positive integers $x$ and $y$, describing a bidirectional road between town $x$ and town $y$.

The last $m$ lines each describe a message, which is one of the following two types:

• 1 x v, indicating that the gem inventory of town $x$ becomes $v$.
• 2 x L, indicating that town $x$ holds a divination ritual, and all towns in its subtree at a distance of at most $L$ participate.

Output

For each message of type 2, output a single non-negative integer on a new line, representing the corresponding XOR sum.

Examples

Input 1

7 5
1 2 3 4 5 6 7
3 1
2 4
3 7
6 7
5 4
4 1
2 1 1
2 4 0
2 7 2
1 6 0
2 7 1

Output 1

6
4
1
7

Subtasks

• Subtask 1 (7 points): $n, m \leq 10^3$.
• Subtask 2 (13 points): $L \leq 20$.
• Subtask 3 (15 points): The number of leaves in the tree is at most $20$.
• Subtask 4 (15 points): Gem inventories do not change (only messages of type 2).
• Subtask 5 (20 points): $n, m \leq 30000$.
• Subtask 6 (30 points): No special restrictions.

For all data, $1 \leq n, m \leq 10^5, 0 \leq L < n, 0 \leq c_i, v \leq 10^9$.