Description

Please note the unusual space constraints for this problem.

Given $\textbf{an operation sequence}$ $A$ and a rooted tree $T$, each operation in $A$ is like ''add $x$ to all point weights on the simple path from $u$ to $v$ in $T$.'' The simple path from $u$ to $v$ is defined as a path starting from $u$ and ending at $v$ that does not repeatedly visit any nodes or edges.

Initially, the root of $T$ is $1$, and all point weights are $0$.

You need to perform three operations:

• Given an interval $[l,r]$, perform operations from $A_l, A_{l+1}\dots$ to $A_r$ in sequence;
• Query the sum of the subtrees of $T$ with $x$ as the root;
• Change the root of $T$ to $y$ (If the current root is $y$, no operation will be performed).

Input Format

The first line contains three positive integers $n_1$, $n_2$, and $m$ ($1\le n_1,n_2,m \le 1\times 10^5$), separated by a space, representing the length of $A$, the total number of points in $T$, and the number of inquiries and operations.

The next $n_1$ lines, the $i$-th line contains three integers $u_i$, $v_i$, and $x_i$ ($1\le u_i,v_i\le n_2, 1\le x_i\le 1\times 10^2$), separated by a space, representing the operation $A_i$ as ''add $x_i$ to all point weights on the simple path from $u_i$ to $v_i$ in $T$.''

Next, there are $n_2-1$ lines, each containing two positive integers $u$ and $v$ ($1\le u,v \le n_2$), separated by a space, representing an edge of the tree. It is guaranteed that the $n_2-1$ edges form a tree.

Next, there are $m$ lines. The first number $op$ ($op\in \{1,2,3\}$) in each line indicates the operation number, followed by:

• If $op$ is $1$, it is followed by two positive integers $l$ and $r$ ($1\le l\le r\le n_1$), separated by a space, indicating that the operations of $A_l, A_{l+1} \dots A_r$ are executed in sequence;
• If $op$ is $2$, it is followed by a positive integer $x$ ($1\le x\le n_2$), indicating that the sum of the subtrees of $T$ with $x$ as the root is queried;
• If $op$ is $3$, it is followed by a positive integer $y$ ($1\le y\le n_2$), indicating that the root of $T$ is changed to $y$ (If the current root is $y$, no operation will be performed).

Output Format

For each operation $2$, output one line of one integer, representing the sum of the subtrees of $T$ with $x$ as the root.

The data ensures that the answer is within the range expressed by a signed long long integer.

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