Данo дерево из $N$ вершин. Вершины пронумерованы от $1$ до $N$, вершина $1$ является корнем. В каждой вершине $i$ хранится целое число $A[i]$. Изначально $A[i] = 0$.

Необходимо обработать следующие запросы:

• 1 u: добавить $1$ ко всем вершинам $i$ поддерева с корнем в вершине $u$.
• 2 u v: добавить $1$ ко всем вершинам $i$ на единственном кратчайшем пути из $u$ в $v$. $u$ и $v$ могут совпадать.

После каждого запроса выведите вершину $x$, которая минимизирует значение $\sum_{y = 1}^{N} A[y] \times dist(x, y)$, где $dist(x, y)$ — количество рёбер на пути из $x$ в $y$. Если есть несколько подходящих вершин $x$, выведите ту, расстояние от которой до корня минимально. Можно доказать, что такая вершина всегда единственна.

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

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

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

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

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

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

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

Выведите $Q$ строк — по одному значению (номеру вершины) после каждого запроса.

Примеры

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

7
1 6
1 7
7 3
3 2
7 5
5 4
4
1 2
1 4
1 6
2 6 7

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

2
7
7
1