给你一棵包含 $N$ 个节点的无向树，树上的每条边都分配了权值。你需要执行以下两种类型的询问：

1. 将节点 $v_i$ 到节点 $u_i$ 路径上的所有边的权值加上给定的值 $a_i$。输入中此类询问的数量不超过 500 次。
2. 计算所有满足“两个端点到节点 $v_i$ 的距离均不超过 $k_i$”的边的权值之和。两个节点之间的距离是指它们之间路径上的边数。

你需要按照给定的顺序执行这些操作，并对于每个第二类询问，输出计算出的值。

输入格式

输入的第一行包含两个整数 $N$ 和 $Q$（$1 \le N \le 1000$，$0 \le Q \le 500\,000$），分别表示树中的节点数和询问次数。

接下来的 $N - 1$ 行包含树的描述：其中第 $i$ 行包含三个整数 $v_i$、$u_i$ 和 $w_i$（$1 \le v_i, u_i \le N$，$1 \le w_i \le 100\,000$），分别表示该边连接的两个节点编号以及它的权值。保证给定的图是一棵树。

接下来的 $Q$ 行包含询问的描述。在这些行中，每行的第一个整数 $t_i$ 是询问的类型（$1 \le t_i \le 2$）。如果 $t_i = 1$，后面会跟着三个整数 $v_i$、$u_i$ 和 $a_i$（$1 \le v_i, u_i \le N$，$1 \le a_i \le 100\,000$），表示你需要将节点 $v_i$ 到 $u_i$ 路径上的所有边的权值加上 $a_i$。如果 $t_i = 2$，后面会跟着两个整数 $v_i$ 和 $k_i$（$1 \le v_i \le N$，$1 \le k_i \le N$），表示你需要求出所有满足“两个端点到节点 $v_i$ 的距离均不超过 $k_i$”的边的权值之和。保证第一类询问的数量不会超过 500 次。

输出格式

对于每个第二类询问，在单独的一行中输出恰好一个整数：即该询问的答案。

样例

样例输入 1

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

样例输出 1

3
6
7
13