Dynamic Tree

Problem Description

Do not forget that this is a dynamic tree — it is dynamic at every moment. Xiao Ming asks you to maintain two kinds of events on this tree.

1. 0 u delta: the tree grows some fruits, i.e. every node in the subtree rooted at $u$ grows $delta$ fruits.
2. 1 k u1 v1 ... uk vk: Xiao Ming wants you to compute the number of fruits on several branches. A branch is a segment of a path from some node to the root. Each time Xiao Ming selects several branches and asks for the sum of the fruits on the nodes belonging to these branches. Note that branches may overlap; in that case the fruits on the overlapping part of the nodes are counted only once.

Input Format

The first line contains one integer $n$ ($1 \leq n\leq 2\times 10^5$), the number of nodes.

The next $n - 1$ lines each contain two numbers $u, v$, indicating a direct edge between fruit $u$ and fruit $v$. Nodes are numbered starting from $1$.

Then one integer $q$ ($1\leq q\leq 2\times 10^5$) follows, the number of events.

The last $q$ lines each begin with either $0$ or $1$.

• If it is $0$, this is event $0$. The next two integers on this line are $u, delta$ ($1\leq delta\leq 10 ^ 9$), meaning every node in the subtree rooted at $u$ grows $delta$ fruits.
• If it is $1$, this is event $1$. The next integer on this line is $k$ ($1\leq k \leq 5$), the number of branches involved in this query, followed by $k$ pairs of integers $u_k, v_k$; each branch goes from node $u_k$ to node $v_k$.

Since the number of fruits may be very large, output the result modulo $2^{31}$.

Output Format

For each event $1$, output the queried number of fruits.

Sample Input

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

Sample Output

13