AT_kupc2018_m.整数と根付き木

整数与有根树

现有一棵有根树 $T$，由顶点 $1$ 至 $N$ 编号而成。最初的根是 $1$ 号点。
树 $T$ 上有 $N-1$ 条边，第 $i$ 条边连接了顶点 $a_i$ 和 $b_i$。
每个顶点 $v$ 都有自己的整数数组 $A_v$。最初它们都是空的。
这棵有根树 $T$ 被查询了 $Q$ 次。共有 $3$ 种不同的查询操作，每种操作如下：

• 1 v x k - 为顶点 $v$ 的子树中的任意顶点（包括顶点 $v$）$u$ 添加 $k$ 值 $x$ 至 $A_u$。
• 2 v y z - 求顶点 $v$ 处的数组 $A_v$ 中满足 $val$ $xor$ $y$ $\leq$ $z$ 且值为 $val$ 的元素个数。其中 $s$ $xor$ $t$ 是指 $s$ 和 $t$ 的位排中或。
• 3 v - 将根节点改为顶点 $v$。

您必须编写一个程序来依次处理这些查询。

输入通过标准输入，格式如下。

$N$
$a_1$ $b_1$
$a_2$ $b_2$
.
.
$a_{N-1}$ $b_{N-1}$
$Q$
$Query_1$
$Query_2$
.
.
$Query_Q$

• $Query_i$ 以1 v x k
  ,2 v y z或3 v的形式逐行输入。

对于形式为2 v y z的查询，按给定的顺序输出答案。

样例解释

样例1：

• $1$ $1$ 第二次查询将 $1$ 的值 $1$ 添加到 $A_1$ 、 $A_2$ 、 $A_3$ 和 $A_4$ 中。
• $2$ 第二次查询将 {800266674} 的值 $1$ 添加到 $A_2$ 中。
• $3$ $3$ 第二次查询将 $3$ 值 $1$ 分别添加到 $A_3$ 和 $A_4$ 中。
• $4$ $4$ 第二次查询将顶点 $1$ 的根更改为顶点 $4$ 。
• $5$ $5$ 第二次查询的结果是 $1$ ，即低于 $4$ 的值的个数，因为 $A_1 = \{1\}$ 和 $1$ $xor$ $0 = 1$ 的值都低于 $4$ 。
• $6$ 第二个查询输出 $2$ ，即 $A_2 = \{1,2\}$ 和 $1$ $xor$ $1 = 0$ 和 $2$ $xor$ $1 = 3$ ，所以 $3$ 或更少 $7$
• $7$ 第二次查询输出 $2$ ，这是低于 $2$ 的数值个数，因为 $A_4 = \{1,3\}$ 、 $1$ $xor$ $3 = 2$ 、 $3$ $xor$ $3 = 0$ 。 $2$
• $8$ 第二次查询将 $1$ 值 $3$ 添加到 $A_1$ 、 $A_2$ 和 $A_3$ 。
• 第 $9$ 次查询将 $A_1$ 和 $A_2$ 以及 $A_3$ 和 $A_4$ 的值 $4$ 添加到 $1$ 中。
• 第二个查询 $10$ 通过 $1$ 将 $1$ 的值添加到 $A_1$ 和 $A_2$ 中。
• $11$ 第二次查询通过 $1$ 将 $2$ 的值添加到 $A_2$ 中。
• $12$ $A_1 = \{1,3,4,1\}$ 查询添加了 $1$ $xor$ $0 = 1$ 、 $3$ $xor$ $0 = 3$ 、 $4$ $xor$ $0 = 4$ 、 $4$ $xor$ $0 = 4$ 、 $4$ $4$ $xor$ $0 = 4$ 。 $1$ $xor$ $0 = 1$ ，因此输出 $4$ ，即低于 $4$ 的数值个数。
• 第 $13$ 次查询会产生 $A_2 = \{1,2,3,4,1,2\}$ 和 $1$ $xor$ $1 = 0$ , $2$ $xor$ $1 = 3$ , $3$ $xor$ $1 = 2$ , $4$ $xor$ $1 = 5$ , $1$ $xor$ $1 = 0$ , $2$ $xor$ $1 = 3$ 所以输出 $5$ ，这是低于 $3$ 的值的个数。 $5$
• $14$ ，即 $A_4 = \{1,3,4\}$ 和 $1$ $xor$ $3 = 2$ , $3$ $xor$ $3 = 0$ , $4$ $xor$ $3 = 7$ , 所以 $5$ 是 $3$ $5$ 下面的数值。 $2$ ，即低于 $2$ 的数值个数。

样例3：

输出不一定适合 $32$ 位整数类型。

• 所有输入均为整数。
• $1 \leq N \leq 1.4 \times 10^5$
• $1 \leq Q \leq 1.4 \times 10^5$
• $1 \leq a_i,b_i \leq N$
• $1 \leq v \leq N$
• $0 \leq x,y,z < 2^{30}$
• $1 \leq k \leq 10^9$
• 给定图形是一棵树。