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

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

• 1 u v: Когда корень дерева находится в вершине $u$, прибавить 1 к $A_i$ для всех вершин $i$ в поддереве с корнем $v$.
• 2 u v: Прибавить 1 к $A_i$ для всех вершин $i$ на единственном пути от вершины $u$ до вершины $v$.
• 3 v: Вывести $\sum_{i = 1}^{N} A_i \times dist(v, i)$. Здесь $dist(x, y)$ обозначает количество рёбер на пути от вершины $x$ до вершины $y$.

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

Первая строка содержит $N$. ($1 \le N \le 200\,000$)

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

Следующая строка содержит количество запросов $Q$. ($1 \le Q \le 200\,000$)

Следующие $Q$ строк содержат по одному запросу в одной из следующих форм:

• 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$)

Запросы типа 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