Description

Maintain a rooted tree with $n$ nodes initially (the root is $1$), with node labels $1 \sim n$, and each node has a weight $w_i$.

Support the following operations:

• 0 u x Query the number of values strictly greater than $x$ in the subtree rooted at $u$.
• 1 u x Set the weight of node $u$ to $x$.
• 2 u x Add a node whose index is "current number of nodes in the tree + 1", with parent $u$ and weight $x$.

This problem is strictly online.
All input $u, x$ must be XORed with $\text{last}$ to obtain the actual input.
Here $\text{last}$ is the answer to the previous query, with initial $\text{last} = 0$.

Input Format

The first line contains a positive integer $n$, the initial number of nodes.

The next $n-1$ lines each contain two integers $u, v$, representing an undirected edge in the tree.

The next line contains $n$ integers $w_i$, the initial weight of each node.

The next line contains a positive integer $m$, the number of operations.

The next $m$ lines each contain three integers $\text{op}, u, x$, describing one operation.

Output Format

For each operation with $\text{op} = 0$, output one line containing an integer, as described above.

2
1 2
10 20
1
0 1 5

2

2
1 2
10 20
1
0 1 10

1

Hint

Constraints
For $100\%$ of the testdata, $1 \le n, m \le 30000$, $1 \le u \le n$, $0 \le w_i, x < 2^{31}$.

Translated by ChatGPT 5