Изменения рейтингов за последние раунды временно удалены. Скоро они будут возвращены. ×

A. Another Tree Queries Problem
time limit per test
6 seconds
memory limit per test
1024 mebibytes
input
standard input
output
standard output

You have a tree of $$$N$$$ vertices. Vertices are enumerated by sequential integers from 1 to $$$N$$$, and the $$$i$$$-th vertex contains the variable $$$A_i$$$. Initially $$$A_i$$$ = 0 ($$$1 \le i \le N$$$).

You have to process $$$Q$$$ queries. Each query is one of the following:

  • "1 $$$u$$$ $$$v$$$": Root the tree at vertex $$$u$$$, consider the subtree of vertex $$$v$$$, and for each vertex $$$i$$$ in the subtree of $$$v$$$, increase $$$A_i$$$ by one.
  • "2 $$$u$$$ $$$v$$$": For each vertex $$$i$$$ in the unique simple path from $$$u$$$ to $$$v$$$, increase $$$A_i$$$ by one.
  • "3 $$$v$$$": Print $$$\displaystyle \sum\limits_{i=1}^N \mathrm{dist} (v, i) \cdot A_i$$$, where $$$\mathrm{dist} (x, y)$$$ is the number of edges in the path from vertex $$$x$$$ to vertex $$$y$$$.
Input

The first line contains an integer $$$N$$$, the number of vertices ($$$1 \le N \le 2 \cdot 10^5$$$).

The next $$$N - 1$$$ lines contain the description of the tree. Each such line contains two integers $$$u$$$ and $$$v$$$ separated by a space, meaning that there is an edge connecting $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le N$$$). It is guaranteed that the resulting graph is a tree.

The next line contains an integer $$$Q$$$, the number of queries ($$$1 \le Q \le 2 \cdot 10^5$$$).

The next $$$Q$$$ lines contain queries, one per line. Each query is given in one of the formats described above ($$$1 \le u, v \le N$$$). You may assume that there is at least one query of type "3".

Output

For each query of type "3", print the result on a separate line.

Example
Input
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
5