Problem Description

Xsonia has a rooted tree with root vertex $1$ and $n$ vertices. Each vertex has a number written on it. The number written on vertex $i$ is $a_i$.

Recall that a tree is a connected graph with no cycles. A rooted tree means choosing one vertex in the tree as the root.

In a rooted tree, the ancestors of a vertex $v$ are all vertices on the path from $v$ to the root (excluding $v$ itself). The subtree of a vertex $v$ is the set of all vertices that have $v$ as an ancestor, including $v$ itself.

The XOR sum of a set $S = (u_1, u_2, u_3, \dots, u_k)$ is defined as $u_1 \oplus u_2 \oplus u_3 \oplus \dots \oplus u_k$, where $\oplus$ is the bitwise XOR operation, written as xor in Pascal, and as ^ in C++/Java/Python.

For a set of numbers $S$, consider the set of XOR sums of all its possible subsets. Call this set $F(S)$.

Xsonia’s friends keep asking her questions like this: “If we consider the multiset of all numbers in the subtree of vertex $v$ (denoted as $U_v$), what is the $k$-th smallest number in the set $F(U_v)$?” In other words, if we take all numbers in the subtree of vertex $v$ and consider the XOR sums of all their subsets, what is the $k$-th smallest number in the resulting set? If such a number does not exist (i.e., $k > |F(U_v)|$), then Xsonia answers $-1$. Note that $F(U_v)$ is a set, not a multiset. That is, even if a number appears multiple times, it is counted only once.

In addition, Xsonia’s friends sometimes ask her to modify a number on the tree.

Input Format

The first line contains two integers $n, g$ ($2 \leq n \leq 5 \cdot 10^4$, $0 \leq g \leq 7$), representing the number of vertices in the tree and the test group ID, respectively.

The next $n - 1$ lines each contain two integers $x_i, y_i$ ($1 \leq x_i, y_i \leq n$), indicating that there is an edge between vertices $x_i$ and $y_i$. It is guaranteed that the graph is a tree.

The next line contains $n$ integers $a_1, a_2, \dots, a_n$ ($0 \leq a_i < 2^{20}$), representing the initial array $a$ of numbers on the vertices.

The next line contains an integer $q$ ($1 \leq q \leq 5 \cdot 10^4$), representing the number of queries.

Each of the next $q$ lines describes one query.

A query that modifies a number has the format $1 \ x_i \ y_i$ ($1 \leq x_i \leq n$, $0 \leq y_i < 2^{20}$). This means the number on vertex $x_i$ becomes $y_i$.

The other type of query has the format $2 \ v_i \ k_i$ ($1 \leq v_i \leq n$, $1 \leq k_i \leq 10^9$). This query asks for the $k_i$-th smallest number in the set $F(U_{v_i})$, where $U_{v_i}$ is the set of numbers in the subtree of vertex $v_i$, and $F(U_{v_i})$ is the set of XOR sums of all its subsets. If $k_i > |F(U_{v_i})|$, output $-1$.

Output Format

For each query of the second type, output the answer on a separate line.

5 0
1 2
1 5
2 3
2 4
4 2 3 1 2
7
2 2 4
2 1 2
2 2 3
1 3 4
2 5 1
2 2 8
2 1 5

3
1
2
0
7
4

Hint

Sample Explanation

Explanation for the first sample. The number next to each vertex is $a_i$.

:::align{center} :::

In the first query, consider the subtree of vertex $2$. It contains the numbers $1, 2, 3$.

$F([1,2,3]) = [0, 1, 2, 3]$.

In the second query, consider the whole subtree. $F([1, 2, 3, 4]) = [0,1,2,3,4,5,6,7]$.

After modifying one number, the tree becomes:

:::align{center} :::

Now, the subtree of vertex $2$ contains the numbers $1, 2, 4$.

$F([1,2,4]) = [0,1,2,3,4,5,6,7]$.

Scoring

• (6 points): $q, n \leq 15$.
• (16 points): $q, n \leq 500$.
• (18 points): $q, n \leq 2000$.
• (7 points): In all second-type queries, $v_i = 1$.
• (13 points): There are no modification queries.
• (11 points): All $a_i, y_i$ are powers of $2$.
• (29 points): No additional constraints.

Translated by DeepSeek V3.

Translated by ChatGPT 5