Description

维护一棵初始有 $n$ 个节点的有根树（根节点为 $1$），树上节点编号为 $1 \sim n$，每个点有一个权值 $w_i$。

支持以下操作：

• 0 u x 询问以 $u$ 为根的子树中，严格大于 $x$ 的值的个数。

• 1 u x 把 $u$ 节点的权值改成 $x$。

• 2 u x 添加一个编号为“当前树中节点数+1”的节点，其父节点为 $u$，其权值为 $x$。

本题强制在线。
所有输入的 $u,x$ 都需要异或 $\text{last}$ 才是真正的输入。
其中 $\text{last}$ 为上一次询问的答案，定义初始 $\text{last} = 0$。

Input Format

第一行一个正整数 $n$，表示初始节点数。

接下来 $n-1$ 行，每行两个整数 $u,v$，为树上的一条无向边。

接下来一行 $n$ 个整数 $w_i$，表示初始时每个节点的权值。

接着一行一个正整数 $m$，表示操作个数。

接下来 $m$ 行，每行三个整数 $\text{op},u,x$，表示一次操作。

Output Format

对每个 $\text{op}=0$ 的操作，输出一行，包括一个整数，意义见题目描述。

2
1 2
10 20
1
0 1 5

2

2
1 2
10 20
1
0 1 10

1

Hint

【数据范围】
对于 $100\%$ 的数据，$1\le n,m \le 30000$，$1\le u \le n$，$0 \le w_i,x < 2^{31}$。