题目描述

送你一棵$n$个点的树，树根为$1$。一开始每个点上有一个$1\sim n$ 的颜色$c_i$，不同点颜色可以相同。 现在有 $q$ 次操作, 分为两种类型： $1\;u\;l\;r$：询问子树 $u$ 中有多少种在 $l$ 到 $r$ 之间的颜色至少出现了一次； $2\;u\;c$：将 $u$ 的颜色修改为 $c$。 部分测试点要求强制在线。

输入

第一行三个整数$n,q,t$，分别表示树的点数，操作的个数和是否强制在线。 $t=0$表示不强制在线，$t=1$表示强制在线。 接下来一行$n$个整数 $c_i$，表示每个点的初始颜色。 接下来$n-1$行，每行两个整数$u_i$;$v_i$表示一条$u_i$到$v_i$的边。 接下来$q$行，每行四个或三个整数，表示一个操作。 当$t=1$时，需要对第一个数以外的其他数异或上一次询问的答案$lastans$，初始时 $lastans=0$。

输出

对于每个询问输出一行一个整数，表示答案。

输入样例

5 5 0
5 5 2 5 5
5 1
2 5
4 2
3 5
1 2 2 3
2 5 1
1 1 1 5
2 3 2
1 3 1 5

输出样例

0
3
1

提示

5 5 1
4 1 1 5 4
5 1
3 5
2 3
4 3
2 5 4
2 2 2
1 3 1 5
2 1 2
1 1 2 7

3
1

数据规模和约定

对于前20%的数据，$n,q≤5000$。 对于前40%的数据，$n,q≤50000$。 对于另20%的数据，没有修改操作。 对于另20%的数据，$t=0$。 对于100%的数据，$1≤n,q≤100000$。

评测数据说明

本题使用按题意独立构造、以独立程序核对的训练数据及公开样例，共6个测试点，非原站或官方原始数据。总分100分。