From XOR with love

Again XOR, again query, again tree — романтика (с) Ануар Сериков

Where XOR there is no place for words. So, let's move on with problem.

Given a rooted tree with $n$ vertices, all vertices numbered from $1$ up to $n$. Each vertex of the tree has a single number written on it, value of vertex. The root of the tree is vertex $1$.

In this problem you must process $q$ queries. Each query is one the following 2 types:

• $1vx$ — change all numbers written on the vertices of the subtree of the vertex $v$, i.e. if the number written on some vertex is $y$, substitute it with $x\oplus y$.

• $2uv$ — print the minimum of the numbers written on the vertices of the simple path from the vertex $u$ to the vertex $v$, i.e. more formally let's numbers on path from vertex $u$ to vertex $v$ will be $a_1,a_2,...,a_k$, then the answer to this query is minimum in this sequence.

Input

The first line contains two integers $n(1\le n\le 3\ast 10^4)$ — the number of vertices in the tree, and $q$ $(1\le q\le 3\ast 10^4)$ is the number of queries.

The second line contains a sequence of $n$ integers $a_1,a_2,\dots ,a_n(0\le a_i<2^{20})$ — the numbers written on vertices.

Then follow $n-1$ lines, describing the tree edges. Each line contains a pair of integers $x_i,y_i(1\le x_i,y_i\le n,x_i\ne y_i)$ — the vertices connected by an edge, it's guaranteed that graph is a connected tree.

The last $q$ lines describe the queries. The first number on $i$-th line is $typ{e}_i$ — the type of the $i$-th query. If $typ{e}_i=1$, then follows two integers $v_i$ and $x_i(1\le v_i\le n$, $0\le x_i<2^{20})$, otherwise it follows with two integer numbers $u_i$ and $v_i(1\le u_i,v_i\le n)$. All input numbers are integers.

Output

For each query of 2nd type print one integer — the answer to the query, each answer on a separate line.

Examples

$\oplus$ is an exclusive OR, e.g. $3\oplus 5=6$.