暂无测试数据。

小 Z 是一个很菜的 oi 选手。他很喜欢动态树。于是有一天他出了一道动态树水题：

给定一棵初始有 $n$ 个点的有根树，点编号为 $1\ldots n$，其中 $1$ 是树根。

定义两点 $u,v$ 间的距离为 $u,v$ 之间最短路径上的边数。

有 $m$ 次操作，每个操作是以下两种之一：

• $1$ $f$ 表示在树上添加一个编号为当前点数 $+1$ 的点，这个点在树上的父亲是 $f$。保证 $f$ 是在树上存在的点。
• $2$ $u$ $l$ $r$ 表示询问以 $u$ 为根的子树中，所有编号在 $[l,r]$ 中的点到 $u$ 的距离之和。

然而神仙小 T 看到这道题后几分钟就秒掉了，代码只有 3K，小 Z 十分惊讶。

于是他找到了你，希望你能教他怎么在三分钟内 A 掉这道题。

提示：读入量非常大，请采用较快的输入输出方式。

注意内存限制，以免因为超出空间限制而失分。

输入格式

第一行包括两个正整数 $n$ 和 $m$，表示初始点数和操作数。

接下来的 $n-1$ 行，每行包含两个正整数 $u,v$，表示初始时 $u$ 和 $v$ 在树上有一条边。

接下来的 $m$ 行，每行包含若干个整数。第一个整数 $op$ 表示操作种类。如果 $op=1$，随后会输入一个正整数 $f$；如果 $op = 2$，随后会输入三个正整数 $u,l,r$。意义如题目描述所述。

保证 $op=2$ 的操作中的 $u$，$op=1$ 的操作中的 $f$ 不超过当前已有的点数。

保证 $op=2$ 的操作中 $1 \le l \le r \le n+m$。

输出格式

对每个 $op=2$ 的操作，输出一行表示答案。

数据范围

对于前 $16\%$ 的数据，$n \le 10^3$，$m \le 10^3$。

对于另外 $32\%$ 的数据，保证对于所有 $op = 2$ 的操作，$l=1$。

对于前 $64\%$ 的数据，$n\le 2\times10^5, m \le 2\times10^5$。

对于 $100\%$ 的数据，$n \le 7\times10^5, m\le 7\times 10^5$。

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

1
6
3
1

10 8
7 1
4 7
1 6
1 8
9 4
5 4
6 2
6 3
8 10
2 6 2 2
1 3
1 2
1 3
1 12
1 2
1 3
2 1 3 7

1
9