给定一棵包含 $n$ 个顶点的树，每条边都有一个权值 $w_i$。

现有 $q$ 次操作，操作分为以下两种类型：

• $1\ i\ c$：将第 $i$ 条边的权值修改为 $c$。
• $2\ x\ d$：统计满足 $1 \le y \le n$ 且 $x$ 与 $y$ 之间的最短路径长度不超过 $d$ 的顶点 $y$ 的数量。

输入格式

第一行包含两个整数 $n$ 和 $q$ ($2 \le n \le 2 \times 10^5, 1 \le q \le 2 \times 10^5$)。

接下来的 $n-1$ 行，每行包含三个整数 $x_i, y_i, w_i$ ($1 \le x_i, y_i \le n, 1 \le w_i \le 10^9$)，表示一条连接 $x_i$ 和 $y_i$ 且权值为 $w_i$ 的边。

接下来的 $q$ 行，每行包含三个整数 $1\ i\ c$ ($1 \le i \le n - 1, 1 \le c \le 10^9$) 或 $2\ x\ d$ ($1 \le x \le n, 0 \le d \le 2 \times 10^{14}$)，表示一次操作。

输出格式

对于每个类型为 2 的操作，输出一行，包含一个整数，表示答案。

样例

输入格式 1

3 7
1 2 3
2 3 1
2 2 1
2 1 3
2 3 4
1 1 1
2 2 1
2 1 0
2 3 1

输出格式 1

2
2
3
3
1
2