题目背景

我曾在弦歌之中听过你，

檀板声碎，半出折子戏。

舞榭歌台被风吹去，

岁月深处尚有余音一缕……

Gty 神(xian)犇(chong)从来不缺妹子……

他来到了一棵妹子树下，发现每个妹子有一个美丽度……

由于Gty很哲♂学，他只对美丽度大于某个值的妹子感兴趣。

他想知道某个子树中美丽度大于 $k$ 的妹子个数。

某个妹子的美丽度可能发生变化……

树上可能会出现一只新的妹子……

题目描述

维护一棵初始有 $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$。

输入格式

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

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

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

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

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

输出格式

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

2
1 2
10 20
1
0 1 5

2

2
1 2
10 20
1
0 1 10

1

提示

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