У вас есть дерево из $N$ вершин. Вершины пронумерованы целыми числами от $1$ до $N$, и каждая вершина $i$ содержит переменную $A_i$. Изначально $A_i = 0$ ($1 \le i \le N$).

Вам необходимо обработать $Q$ запросов. Каждый запрос имеет один из следующих видов:

• «1 $u$ $v$»: Сделать вершину $u$ корнем дерева, рассмотреть поддерево вершины $v$ и для каждой вершины $i$ в поддереве $v$ увеличить $A_i$ на единицу.
• «2 $u$ $v$»: Для каждой вершины $i$ на единственном простом пути от $u$ до $v$ увеличить $A_i$ на единицу.
• «3 $v$»: Вывести $\sum_{i=1}^{N} \text{dist}(v, i) \cdot A_i$, где $\text{dist}(x, y)$ — количество ребер на пути между вершинами $x$ и $y$.

Входные данные

Первая строка содержит целое число $N$ — количество вершин ($1 \le N \le 2 \cdot 10^5$).

Следующие $N - 1$ строк содержат описание дерева. Каждая такая строка содержит два целых числа $u$ и $v$, разделенных пробелом, что означает наличие ребра между $u$ и $v$ ($1 \le u, v \le N$). Гарантируется, что полученный граф является деревом.

Следующая строка содержит целое число $Q$ — количество запросов ($1 \le Q \le 2 \cdot 10^5$).

Следующие $Q$ строк содержат запросы, по одному в строке. Каждый запрос задан в одном из форматов, описанных выше ($1 \le u, v \le N$). Можно считать, что будет выполнен хотя бы один запрос типа «3».

Выходные данные

Для каждого запроса типа «3» выведите результат на отдельной строке.

Примеры

Входные данные 1

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

Выходные данные 1

1
5