题面描述

马修在喝下今天的第五杯咖啡后，开始看到对面树上的颜色在不断变化。就在这时，他觉得从树上的一个点走到另一个点会是一件很有趣的事。由于他现在的状态并不适合自己完成这件事，于是他把任务交给了你。

马修的树有 $N$ 个点，编号为 $1$ 到 $N$，根节点为 $1$。每个点一开始都被染成 $1$ 到 $N$ 中的某个颜色（允许多个点颜色相同）。

接下来有 $Q$ 个操作，分为三种类型：

1. 将从 $U_i$ 到 $V_i$ 的简单路径上的所有点染成颜色 $C_i$；
2. 将点 $U_i$ 的整棵子树中的所有点染成颜色 $C_i$；
3. 询问从 $U_i$ 到 $V_i$ 的路径上，颜色发生变化的次数。

对于第 3 类询问，若 $U_i=V_i$，答案视为 $0$。更正式地，若从 $U_i$ 到 $V_i$ 的路径为：

$$U_i=P_1,P_2,\dots,P_k=V_i$$

则答案为满足下式的 $j$ 的个数：

$$1 \le j < k,\quad \text{color}(P_j) \ne \text{color}(P_{j+1})$$

这里，点 $U_i$ 的子树指的是：所有从该点到根的路径经过 $U_i$ 的点所组成的集合（含 $U_i$ 自身）。

输入格式

第一行一个整数 $N$，表示树上的点数。
接下来 $N-1$ 行，每行两个整数 $A_i,B_i$，表示树的一条边。
第 $N+1$ 行包含 $N$ 个整数 $S_1,S_2,\dots,S_N$，表示每个点的初始颜色。
接下来一行一个整数 $Q$，表示操作数。
随后 $Q$ 行描述操作，格式如下：

• 1 Ui Vi Ci：将路径 $U_i \to V_i$ 上所有点染成颜色 $C_i$；
• 2 Ui Ci：将 $U_i$ 的整棵子树染成颜色 $C_i$；
• 3 Ui Vi：询问路径 $U_i \to V_i$ 上颜色变化的次数。

输出格式

对于每个 3 类操作，输出一行一个整数表示答案。

数据范围

$$1 \le N,Q \le 10^5$$ $$1 \le A_i,B_i \le N$$ $$1 \le U_i,V_i,C_i \le N$$

子任务与评分

子任务	分值	$N,Q \le$	操作类型
1	5	1000	1,2,3
2	15	$10^5$	3
3	25		2,3
4	45		1,3
5	10		1,2,3

样例

输入

6
1 2
2 6
2 3
3 4
3 5
1 1 3 1 2 1
5
3 6 4
1 6 4 2
3 1 5
2 2 4
3 3 5

输出

2
1
0