From XOR with love#11546
Again XOR, again query, again tree — romantika (c) Anuar Serikov
Where there is XOR, there is no place for words. So, let's move on to the problem.
You are given a rooted tree with vertices, all vertices numbered from up to . Each vertex of the tree has a single number written on it, value of vertex. The root of the tree is vertex .
In this problem you must process queries. Each query is one of the following 2 types:
— change all numbers written on the vertices of the subtree of the vertex , i.e. if the number written on some vertex is , substitute it with x\oplus y.
— print the minimum of the numbers written on the vertices of the simple path from the vertex to the vertex , i.e. more formally let the numbers on the path from vertex to vertex be a_1, a_2, ... , a_k, then the answer to this query is minimum in this sequence.
The first line contains two integers n~(1 \le n \le 3\cdot10^4) — the number of vertices in the tree, and (1 \le q \le 3\cdot10^4) is the number of queries.
The second line contains a sequence of 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 \leq x_i,y_i \leq n, x_i \ne y_i) — the vertices connected by an edge, it's guaranteed that graph is a connected tree.
The last lines describe the queries. The first number on -th line is type_i — the type of the -th query. If type_i = 1, then follows two integers v_i and x_i~(1 \le v_i \le n, 0 \le x_i < 2^{20}), otherwise two integers follow u_i and v_i~(1 \le u_i, v_i \le 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\oplus 5 = 6.
Example 1