小安妮非常喜欢画画。今天在学校，她听听说过图和树。回到家后，她决定画一棵树。但她觉得自己的树不够漂亮。于是安妮拿来颜料，给树的所有节点都涂上了颜色。但过了一段时间，她对这种涂色感到厌倦了，于是决定重新给节点染色。

安妮定义，节点 $v$ 的半径为 $k$ 的区域是指从节点 $v$ 出发，通过移动最多 $k$ 条边可以到达的节点集合。树是无向的，因此每条边都可以双向通行。有时在不忙于重新染色时，她会想知道某个区域内有多少种不同的颜色。但对她来说，回答这些问题非常困难，所以安妮请求你来帮助她。

输入格式

第一行包含三个整数 $N$、$K$ 和 $C$（$1 \le N \le 50\,000$，$0 \le K \le 50$，$1 \le C \le 50$）：树中的节点数、区域的最大半径，以及安妮调色盘中不同颜色的数量（颜色从 $1$ 到 $C$ 编号）。

第二行包含 $N$ 个整数 $c_i$（$1 \le c_i \le C$），表示节点最初被涂上的颜色。

接下来的 $N - 1$ 行包含树的描述：其中第 $i$ 行包含两个整数 $a_i$ 和 $b_i$（$1 \le a_i, b_i \le N$）——由第 $i$ 条边连接的顶点索引。保证给定的图是一棵树。

下一行包含一个整数 $Q$（$1 \le Q \le 100\,000$）：安妮的询问次数。

接下来的 $Q$ 行按以下格式包含询问的描述。第一个整数 $d_i$ 是询问的类型（$1 \le d_i \le 2$）。

• 如果 $d_i = 1$，则后面跟着两个整数 $v_i$ 和 $w_i$（$1 \le v_i \le N$，$1 \le w_i \le C$）：表示被重新染色的节点编号及其新颜色。
• 如果 $d_i = 2$，则后面跟着两个整数 $v_i$ 和 $k_i$（$1 \le v_i \le N$，$0 \le k_i \le K$）：表示区域的中心节点编号及其半径。

输出格式

对于每个第二种类型的询问，在单独的一行中输出给定区域内不同颜色的数量。

样例

输入格式 1

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

输出格式 1

2
3
2
1