暂无测试数据。

古代地下都市有很多奇异的植物与水果，其中，$\text{brz}$ 树就是一种奇妙的树。

这种树是以 $1$ 为根的树，每条边有一个权值，所有边的权值合起来是 $1\sim n-1$ 的一个排列。它在很短的时间内可以结出很多果实，经过 $\text{Mira}$ 的研究，果实的生长含有一定的规律。

$\text{Mira}$ 曾经看到过有根二叉树，她也知道有根二叉树的后序遍历是什么，类似的，她定义出适用于 $\text{brz}$ 树的广义后序遍历：对于一个节点，先遍历它的所有儿子中，父子边权值最小的那个，遍历完后遍历第二小的，以此类推，最后将自己放入后序遍历序列的末尾。

类似的，$\text{Mira}$ 相对于 dfs 序，定义出逆 dfs 序：对于一个节点，先将自己放入逆 dfs 序序列的末尾，然后遍历所有儿子中父子边权值最大的那个，然后遍历第二大，以此类推。

$\text{Mira}$ 发现，$\text{brz}$ 树每次生长水果的节点，一定是广义后序遍历序列的一个区间或逆 dfs 序的一个区间，一开始树上没有水果。

而 $\text{Mira}$ 又有若干次询问，每次她会询问广义后序遍历序列的一个区间内的节点上的水果总数，或者是逆 dfs 序上某个区间内的水果总数。

由于 $\text{Mira}$ 忙着采水果，所以这个问题就交给你了。

输入格式

第一行两个整数 $n,q$，表示 $\text{brz}$ 树的节点数目以及操作数量。

下面 $n-1$ 行描述这棵树，每行有三个整数 $x_i,y_i,z_i$，表示 $x_i,y_i$ 之间有一条边，权值为 $z_i$。

下面 $q$ 行每行描述一个操作，第一个整数表示操作种类，操作是下面四种之一：

• $op = 1$，继续输入三个正整数 $x,y,c$。表示广义后序遍历序列 $[x,y]$ 区间内的每个节点长出了 $c$ 个果子。
• $op=2$，继续输入三个正整数 $x,y,c$。表示逆 dfs 序 $[x,y]$ 区间内的每个节点长出了 $c$ 个果子。
• $op=3$，继续输入两个正整数 $x,y$。表示询问广义后序遍历序列中 $[x,y]$ 区间内所有节点上有多少个果子。
• $op = 4$，继续输入两个正整数 $x,y$。表示询问逆 dfs 序 $[x,y]$ 区间内的所有节点上有多少个果子。

输出格式

对于每个 $3,4$ 操作，输出一个整数表示答案。

数据范围

对于 $20\%$ 的数据，有 $n,q\leq 2\times 10^3$。

对于另外 $20\%$ 的数据，保证所有 $1,2$ 操作都在 $3,4$ 操作之前。

对于 $100\%$ 的数据，有 $1\leq n,q\leq 10^5,1\leq x,y\leq n,1\leq c\leq 10^3$，保证 $z_1\sim z_{n-1}$ 为 $1\sim n-1$ 的一个排列。

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

2

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

24
28