Aisultan 和 Batyr 决定参加 KazHackStan 会议。他们遇到了一个计算机网络问题。给定 $N$ 台不同的计算机和 $N - 1$ 条双向连接，两台相连的计算机称为邻居。计算机编号从 $1$ 到 $N$。保证从任意一台计算机都可以通过连接到达其他任何一台计算机。

有时一些计算机可能会感染病毒，病毒会传播给邻居计算机。每种病毒在每一秒钟都会感染所有邻居计算机。给定 $Q$ 次查询。每种查询属于以下两种类型之一：

1. 新病毒出现：给定计算机编号 $v$ 和病毒出现的时间 $t$，新病毒的 ID 将是之前未用作病毒 ID 的最小正整数。
2. 对于给定的 $l, r, t$，他们需要计算到时间 $t$ 为止，所有 ID 在 $l$ 到 $r$（包含）范围内的病毒所感染的不同计算机的总数。保证所有 ID 从 $l$ 到 $r$ 的病毒都存在。

在所有查询中，$t$ 不一定是有序的。为了更好地理解，请参阅样例测试的说明。Aisultan 和 Batyr 无法解决这个问题。请帮助他们解决。

输入格式

输入的第一行包含两个正整数 $N, Q$ ($1 \le N, Q \le 10^5$)，表示网络中的计算机数量和查询数量。接下来的 $N - 1$ 行，每行包含两个整数 $u_i, v_i$ ($1 \le u_i, v_i \le N, u_i \neq v_i$)，表示第 $i$ 条连接。接下来的 $Q$ 行给出了查询的描述。查询以整数 $type$ 开头。如果 $type = 1$，则给定两个整数 $v, t$ ($1 \le v \le N, 1 \le t \le 10^9$)，表示感染新病毒的计算机 ID 和该病毒出现的时间，新病毒的 ID 将是之前未用作病毒 ID 的最小正整数。如果 $type = 2$，则给定三个整数 $l, r, t$ ($1 \le l \le r, 1 \le t \le 10^9$)，表示病毒 ID 的起始和结束范围，以及需要计算感染计算机数量的时间点。保证 ID 从 $l$ 到 $r$ 的病毒均存在。同时保证至少有一个 $type = 2$ 的查询。

输出格式

对于每个 $type = 2$ 的查询，输出一个整数，即问题的答案。

子任务

本题包含 8 个子任务：

1. $1 \le N, Q \le 100$。分值 8 分。
2. $1 \le N, Q \le 1000$。分值 7 分。
3. $1 \le N, Q \le 10^4$，$t_i \le t_{i+1}$ 对于所有 $1 \le i \le Q - 1$ 成立 —— 所有时间按非递减顺序给出。分值 9 分。
4. $u_i = 1, v_i = i + 1$ 对于所有 $1 \le i \le N - 1$ 成立。分值 11 分。
5. $u_i = i, v_i = i + 1$ 对于所有 $1 \le i \le N - 1$ 成立。分值 20 分。
6. 所有病毒都出现在计算机 1。分值 10 分。
7. $1 \le N, Q \le 10^4$。分值 15 分。
8. 满足题目中的数据范围。分值 20 分。

样例

输入 1

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

输出 1

4
1
0

说明

在第一次查询中，新病毒在第 5 秒出现在计算机 1。之前未用作病毒 ID 的最小正整数为 1。第一种病毒将感染： 计算机 1 在第 5 秒被感染 计算机 2 在第 6 秒被感染 计算机 3 在第 7 秒被感染 计算机 4 在第 7 秒被感染 * 计算机 5 在第 8 秒被感染

第二次查询：我们需要计算在第 7 秒被病毒 1 感染的计算机数量。总共有 4 台不同的计算机，编号为：1, 2, 3, 4。

在第三次查询中，新病毒在第 5 秒出现在计算机 4。之前未用作病毒 ID 的最小正整数为 2。第二种病毒将感染： 计算机 4 在第 5 秒被感染 计算机 5 在第 6 秒被感染 计算机 2 在第 6 秒被感染 计算机 1 在第 7 秒被感染 * 计算机 3 在第 7 秒被感染

第四次查询：我们需要计算在第 6 秒被病毒 1 和病毒 2 感染的计算机数量。总共有 1 台不同的计算机，编号为：2。

第五次查询：我们需要计算在第 1 秒被病毒 1 和病毒 2 感染的计算机数量。在第 1 秒没有计算机被感染。