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:
1 v x — 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⊕y.
2 u v — 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 a1,a2,...,ak, then the answer to this query is minimum in this sequence.
The first line contains two integers n (1≤n≤3∗104) — the number of vertices in the tree, and q (1≤q≤3∗104) is the number of queries.
The second line contains a sequence of n integers a1,a2,…,an (0≤ai<220) — the numbers written on vertices.
Then follow n−1 lines, describing the tree edges. Each line contains a pair of integers xi,yi (1≤xi,yi≤n,xi=yi) — 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 typei — the type of the i-th query. If typei=1, then follows two integers vi and xi (1≤vi≤n, 0≤xi<220), otherwise it follows with two integer numbers ui and vi (1≤ui,vi≤n). All input numbers are integers.
For each query of 2nd type print one integer — the answer to the query, each answer on a separate line.
⊕ is an exclusive OR, e.g. 3⊕5=6.