Problem Background

I once heard you in the melody of strings,

The clapper breaks, half a scene from a play.

The dance hall and stage are blown away by the wind,

Deep in the years, a faint echo remains...

Gty, the deity (xian) and master (chong), is never short of admirers...

He came to a tree of admirers, where each has a beauty rating...

Since Gty is philosophical, he is only interested in admirers with beauty ratings greater than a certain value.

He wants to know the number of admirers with beauty ratings greater than $k$ in a certain subtree.

The beauty rating of an admirer may change...

A new admirer may appear on the tree...

Problem Description

Maintain a rooted tree that initially has $n$ nodes (with the root node being $1$), where the node numbers range from $1$ to $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 Change the weight of node $u$ to $x$.

• 2 u x Add a node with the number "current number of nodes in the tree + 1", whose parent node is $u$ and whose weight is $x$.

This problem is strictly online.
All inputs of $u, x$ need to be XORed with $\text{last}$ to get the actual input.
Where $\text{last}$ is the answer to the previous query, defined initially as $\text{last} = 0$.

Input Format

The first line contains a positive integer $n$, representing 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$, representing the initial weights of each node.

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

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

Output Format

For each operation where $\text{op} = 0$, output a line containing an integer, as described in the problem statement.

Sample Input and Output

Input Sample #1

2
1 2
10 20
1
0 1 5

Output Sample #1

2

Input Sample #2

2
1 2
10 20
1
0 1 10

Output Sample #2

1

Notes

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

见题面 Input 部分

见题面 Output 部分