409481: GYM103577 G Matematical Transformation

G. Matematical Transformationtime limit per test5 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

When Diego tells Osman a problem about maths, Osman always tries to turn it into a graph problem. This is because it is easier for him to think about graph problems.

On this occasion Diego asked Osman about the Birch and Swinnerton-Dyer conjecture, this conjecture says that an elliptic curve (a type of cubic curve, or algebraic curve of order three, confined to a region known as a torus) has either an infinite number of rational points (solutions) or a finite number of rational points, according to whether an associated function is equal to zero or not equal to zero, respectively. In the following image we can see a related scientific diagram:

Quickly Osman turned this statement into a graph challenge. More specifically he thinks about an undirected graph rooted at node 1 in which every pair of nodes has a unique path. Each node will have a value associated, which initially is $$$0$$$. And he will have two types of queries he needs to perform to the tree.

• The first query is simple: get the sum of the values in the nodes in the path between two given nodes.
• The second query is even simpler. You will be given three integers $$$u$$$, $$$v$$$ and $$$k$$$ and you have to add $$$v + k\times d$$$ to each node in the subtree of $$$u$$$, where $$$d$$$ is the distance of each node to $$$u$$$.

Can you solve the new version of the original problem?Input

The first line contains an integer $$$n$$$ ($$$1 \le n \le 3 \times 10^5$$$) — The number of nodes in the tree.

The following $$$n-1$$$ lines contains two integers $$$u$$$, $$$v$$$ ($$$1 \le u, v \le n$$$) that means there is an edge between nodes $$$u$$$ and $$$v$$$.

The next line will contain integer $$$q$$$ ($$$1 \le q \le 3 \times 10^5$$$) — The number of queries to process.

The following $$$q$$$ lines of input will describe the information of each query. The $$$i$$$-th line starts with the type of query $$$type_i \in \{0, 1\}$$$, then the rest of the line goes as follows:

• if $$$type_i = 0$$$, it will be followed by two integers $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le n$$$), meaning that you want to compute the sum of the values in the nodes in the path from $$$u$$$ to $$$v$$$
• if $$$type_i = 1$$$, it will be followed by three integers $$$u$$$, $$$v$$$ and $$$k$$$ ($$$1 \le u \le n$$$, $$$1 \le v, k \le 5 \times 10^5$$$), meaning that you want to add $$$v + k\times d$$$ to each node in the subtree of $$$u$$$, where $$$d$$$ is the distance of each node to $$$u$$$.

Output

For each query of type $$$0$$$ print the corresponding answer. The answer for each query should be in a separate line.

ExamplesInput

6
6 1
6 2
6 3
6 4
6 5
6
1 6 1 1
0 3 5
1 3 4 9
0 2 1
1 3 4 3
0 3 2

Output

5
3
13

Input

6
6 3
1 6
2 5
5 3
2 4
6
0 5 2
1 3 4 10
0 2 4
1 3 5 9
0 5 6
1 6 0 9

Output

0
58
37

Input

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

Output

22

Input

4
1 2
2 3
3 4
4
1 4 5 6
0 2 4
1 3 4 9
0 3 2

Output

5
4