题目描述

给你一棵 $n$ 个点的树，每个结点有颜色。

你从一个点 $u$ 出发，可以走到相邻的点 $v$，当且仅当 $(c_u + 1) \ \% C \ = c_v$，其中 $C$ 是给定的。

有以下两种操作：

• 1 u c 将 $u$ 的颜色修改为 $c$。
• 2 u 查询从点 $u$ 出发，能够到达多少个点。

输入格式

第一行三个数，$n, q, C$。分别表示点数，操作数，和颜色数。
第二行 $n$ 个数，第 $i$ 个数表示 $c_i$。
接下来 $n - 1$ 行，每行两个数 $u_i, v_i$，表示一条树边。
接下来 $q$ 行。每行描述一个操作。

输出格式

对于每个 2 操作，输出一个整数，表示对于这个操作的回答。

10 10 2
1 0 0 1 1 1 0 1 1 0
8 6
4 8
7 2
3 8
10 2
9 5
4 5
1 3
2 1
2 10
2 8
1 5 1
1 10 0
1 1 0
1 4 0
1 4 0
1 1 0
2 8
2 8

1 
4 
4 
4

10 10 3
2 0 2 0 1 0 2 2 0 1
3 9
5 2
7 5
6 2
8 3
2 4
2 1
10 6
6 8
1 7 0
1 9 1
1 7 0
1 8 2
2 1
1 7 1
2 7
2 4
1 9 1
1 9 1

3 
1 
1

数据规模与约定

对于 $100\%$ 的数据，$n \leq 10 ^5$，$q \leq 3 \times 10 ^5$，$C \leq 100$。