Migrated from Lutece 2529 熊上树

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

UESTC 的集训室门前有一排树，其中第一棵是线段树，第二棵是平衡树，第三棵是动态树……

这天，无敌的熊爷爷 AK 了 CCCC，他觉得这次的题目太无趣了，做题不如爬树，于是他就爬上了其中一棵树。

这棵树有 $n$ 个结点，编号为 $1$ 到 $n$，$1$ 号结点是它的根。编号为 $i$ 的结点有点权 $a_i$。在熊爬上这棵树之前，所有的 $a_i$ 都为 $0$。

熊在树上玩得很开心。有时，他会从结点 $u$ 走到结点 $v$（经过最短路径），并将经过的结点权值都加上 $x$。有时，他会走遍以结点 $u$ 为根的整个子树，并将经过的结点权值都加上 $x$。

不过，一直在树上走也挺无趣的，熊觉得还是问你些什么比较好。于是他站在结点 $u$ 上，随手写了个式子让你求值：

$\sum_{v = 1} ^n a_v \cdot \mathrm{dis}(u, v)$

其中 $\mathrm{dis}(u, v)$ 是结点 $u$ 到 $v$ 的最短路径的长度。

Input

输入的第一行包含一个正整数 $T\ (1 \leq T \leq 10^5)$，表示熊这天一共爬了 $T$ 棵树（即有 $T$ 组测试数据）。

每组测试数据的第一行包含两个正整数 $n, m\ (1 \leq n, m \leq 10^5)$，表示这颗树共有 $n$ 个结点，熊在树上进行了 $m$ 次操作或询问。

接下来的 $n - 1$ 行每行包含两个正整数 $u, v\ (1 \leq u, v \leq n)$，表示结点 $u, v$ 之间有一条长度为 $1$ 的边相连。保证数据给出的是一棵树。

接下来的 $m$ 行，每行包含若干正整数（$1 \leq u, v \leq n, 1 \leq x \leq 10^3$），格式是下列三种之一：

• 1 u v x 表示熊从结点 $u$ 走到了结点 $v$，并将经过的结点权值都加上 $x$。
• 2 u x 表示熊走遍了以结点 $u$ 为根的整个子树，并将经过的结点权值都加上 $x$。
• 3 u 表示熊站在结点 $u$，向你提出了询问，询问的式子见上文。

保证对于所有的 $T$ 组数据，有 $\sum n \leq 10^5, \sum m \leq 10^5$。

Output

对熊提出的所有询问，按提问顺序输出答案，每个答案一行。

Samples

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

2
96
108

Resources

2021 UESTC ICPC Training for Data Structures