题目描述

请注意本题不同寻常的空间限制。

给定 操作序列 $A$ 和一棵有根树 $T$，$A$ 中的每个操作都形如「给 $T$ 中 $u$ 到 $v$ 的简单路径上的所有点权增加 $x$」。其中，$u$ 到 $v$ 的简单路径定义为：从 $u$ 开始到 $v$ 结束的一条不重复访问任何节点和边的路径。

初始时 $T$ 的根为 $1$，所有点权皆为 $0$。

你需要执行三种操作：

• 给定区间 $[l,r]$，依次执行 $A_l, A_{l+1}\dots$ 到 $A_r$ 的操作；
• 查询 $T$ 以 $x$ 为根的子树和；
• 换 $T$ 的根到 $y$（若当前根为 $y$，则不进行操作）。

输入格式

第一行包含三个正整数 $n_1$, $n_2$ 和 $m$ ($1\le n_1,n_2,m \le 1\times 10^5$)，用一个空格分隔，分别表示 $A$ 的长度、$T$ 的总点数、询问与操作的次数。

接下来 $n_1$ 行，第 $i$ 行包含三个整数 $u_i$, $v_i$ 和 $x_i$ ($1\le u_i,v_i\le n_2, 1\le x_i\le 1\times 10^2$)，用一个空格分隔，表示操作 $A_i$ 为「给 $T$ 中 $u_i$ 到 $v_i$ 的简单路径上的所有点权增加 $x_i$」。

接下来 $n_2-1$ 行，每行包含两个正整数 $u$ 和 $v$ ($1\le u,v \le n_2$)，用一个空格分隔，表示树的一条边。保证该 $n_2-1$ 条边构成树。

接下来 $m$ 行，每行的第一个数 $op$ ($op\in \{1,2,3\}$) 表示操作编号，随后：

• 若 $op$ 为 $1$，则后面跟随两个正整数 $l$ 和 $r$ ($1\le l\le r\le n_1$)，用一个空格分隔，表示依次执行 $A_l, A_{l+1} \dots A_r$ 的操作；
• 若 $op$ 为 $2$，则后面跟随一个正整数 $x$ ($1\le x\le n_2$)，表示查询 $T$ 以 $x$ 为根的子树和；
• 若 $op$ 为 $3$，则后面跟随一个正整数 $y$ ($1\le y\le n_2$)，表示换 $T$ 的根到 $y$（若当前根为 $y$，则不进行操作）。

输出格式

对于每个操作 $2$，输出一行一个整数，表示 $T$ 以 $x$ 为根的子树和。

数据保证答案在有符号超长整型所表达的范围内。

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

29
25
63