冬天到了，雪花飘落在农场上。和往年冬天一样，Bessie 正在堆雪牛！大多数时候，Bessie 努力让她的雕塑看起来尽可能像一头真正的牛。然而，今年她灵感迸发，决定走抽象路线，堆一个树状的雕塑。该雕塑由 $N$ 个雪球 $(1\le N\le 10^5)$ 和 $N-1$ 条树枝组成，每条树枝连接一对雪球，使得任意两个雪球之间都有唯一的路径。

Bessie 在其中一个雪球上装了一个鼻子，作为这头抽象雪牛的头部。她将其指定为 1 号雪球。为了增加视觉趣味，她计划用装满彩色染料的旧奶桶泼洒雕塑，以艺术的方式为一些雪球染色。颜色由 $1 \ldots 10^5$ 范围内的整数标识，Bessie 有无限供应的各种颜色的染料桶。

当 Bessie 用一桶染料泼洒一个雪球时，该雪球子树中的所有雪球也会被染上相同的颜色（如果 $x$ 位于 $y$ 到头部雪球的路径上，则称雪球 $y$ 在雪球 $x$ 的子树中）。通过小心地泼洒每种颜色，Bessie 确保雪球被泼洒过的所有颜色都保持可见。例如，如果一个雪球已经有了颜色 $[1,2,3]$，而 Bessie 又用颜色 $4$ 泼洒它，那么该雪球现在将拥有颜色 $[1,2,3,4]$。

在进行若干次泼洒操作后，Bessie 可能还想知道她的雪牛某一部分的“多彩程度”。雪球 $x$ 的“多彩程度”等于雪球 $x$ 所拥有的不同颜色 $c$ 的数量。如果 Bessie 向你询问关于雪球 $x$ 的信息，你应该回答 $x$ 的子树中所有雪球的多彩程度之和。

请帮助 Bessie 计算在特定时间点她雪牛的多彩程度。

子任务

$Q$ 的定义如下。

• 测试点 2-3 满足 $N\le 10^2, Q\le 2\cdot 10^2$。
• 测试点 4-6 满足 $N\le 10^3, Q\le 2\cdot 10^3$。

输入格式

第一行包含 $N$ 和查询次数 $Q$ ($1\le Q\le 10^5$)。

接下来的 $N-1$ 行，每行包含两个空格分隔的整数 $a$ 和 $b$，描述连接雪球 $a$ 和 $b$ 的一条树枝 ($1 \le a, b \le N$)。

最后，$Q$ 行，每行包含一个查询。格式为 1 x c 的查询表示 Bessie 用颜色 $c$ 的染料桶泼洒了雪球 $x$，给 $x$ 子树中的所有雪球染色。格式为 2 x 的查询要求计算 $x$ 子树中所有雪球的多彩程度之和。当然，$1\le x\le N$ 且 $1\le c\le 10^5$。

输出格式

对于每个类型为 2 的查询，输出对应子树内的多彩程度之和。

注意：请使用 64 位整数以避免溢出。

样例

样例输入 1

5 18
1 2
1 3
3 4
3 5
1 4 1
2 1
2 2
2 3
2 4
2 5
1 5 1
2 1
2 2
2 3
2 4
2 5
1 1 1
2 1
2 2
2 3
2 4
2 5

样例输出 1

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

说明

在第一次类型 1 查询后，雪球 4 被染上颜色 1。

在第二次类型 1 查询后，雪球 4 和 5 被染上颜色 1。

在第三次类型 1 查询后，所有雪球都被染上颜色 1。

题目来源：Michael Cao 和 Benjamin Qi