题目背景

我曾在青山之中遇过你，
新竹做杖，鬓插紫茱萸。
跣足踏过无边丝雨，
又拾起燕川雪片片落如席……

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

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

由于Gty很 哲♂学 也很 机♂智，他只对美丽度大于某个值的妹子感兴趣。
他想知道某个子树中美丽度大于 $x$ 的妹子个数。

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

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

但是……树枝可能会断裂，于是，Gty 惊讶地发现，他的面前变成了一片妹子树组成的森林……

题目描述

维护一棵初始有 $n$ 个节点的有根树（根节点为 $1$），树上节点编号为 $1 \sim n$，每个点有一个权值 $w_i$，它可能会变成森林。

支持以下操作：

• 0 u x 询问以 $u$ 为根的子树中，严格大于 $x$ 的值的个数。
• 1 u x 把 $u$ 节点的权值改成 $x$。
• 2 u x 添加一个编号为“当前树中节点数+1”的节点，其父节点为 $u$，其权值为 $x$。
• 3 u 删除 $u$ 与其父亲的边，并使 $u$ 变为其所在连通块的根。

本题强制在线。

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

输入格式

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

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

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

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

接下来 $m$ 行，每行若干个整数，表示一次操作。

输出格式

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

2
1 2
10 20
1
0 1 5

2

提示

数据范围及约定

对于 $100\%$ 的数据，$1\le n,m \le 10^5$，$1\le u \le n$，$0 \le w_i,x < 2^{31}$。