There is a tree consisting of $N$ vertices. The vertices are numbered from $1$ to $N$, and each vertex $i$ stores an integer $A_i$. Initially, $A_i = 0$ for all $i$ ($1 \le i \le N$).

You need to process a total of $Q$ queries of the following types:

• 1 u v: When the root of the tree is vertex $u$, add $1$ to $A_i$ for every vertex $i$ in the subtree rooted at vertex $v$.
• 2 u v: Add $1$ to $A_i$ for every vertex $i$ on the unique path from vertex $u$ to vertex $v$.
• 3 v: Output $\sum_{i = 1}^{N} A_i \times dist(v, i)$. Here, $dist(x, y)$ denotes the number of edges on the path from vertex $x$ to vertex $y$.

Input

The first line contains $N$ ($1 \le N \le 200{,}000$).

The next $N-1$ lines describe the edges of the tree. Each line contains two space-separated integers $u$ and $v$, indicating an edge connecting $u$ and $v$ ($1 \le u, v \le N$).

The next line contains the number of queries $Q$ ($1 \le Q \le 200{,}000$).

The next $Q$ lines each contain one query in one of the following formats:

• 1 u v ($1 \le u, v \le N$)
• 2 u v ($1 \le u, v \le N$)
• 3 v ($1 \le v \le N$)

At least one type‑3 query is given.

Output

For each type‑3 query, output the result on a separate line in order.

Examples

Input 1

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

Output 1

1
5