Có một cây gồm $N$ đỉnh. Các đỉnh được đánh số từ 1 đến $N$, và đỉnh 1 là gốc. Mỗi đỉnh $i$ có một số nguyên $A[i]$ được lưu trữ. Ban đầu, $A[i]=0$.

Cần thực hiện các truy vấn sau:

• 1 u: Cộng 1 vào $A[i]$ của tất cả các đỉnh $i$ trong cây con gốc $u$.
• 2 u v: Cộng 1 vào $A[i]$ của tất cả các đỉnh $i$ nằm trên đường đi duy nhất ngắn nhất từ $u$ đến $v$. $u$ và $v$ có thể trùng nhau.

Sau mỗi truy vấn, hãy đưa ra đỉnh $x$ làm cho giá trị $\sum_{y = 1}^{N} A[y] \times dist(x, y)$ là nhỏ nhất. $dist(x, y)$ là số cạnh trên đường đi từ $x$ đến $y$. Nếu có nhiều đỉnh $x$ thỏa mãn, hãy đưa ra đỉnh có khoảng cách tới gốc là gần nhất. Có thể chứng minh rằng đỉnh đó luôn duy nhất.

Dữ liệu vào

Dòng đầu tiên chứa $N$ ($2 \le N \le 100\,000$).

$N-1$ dòng tiếp theo mô tả các cạnh của cây. Mỗi dòng chứa hai số nguyên $u$ và $v$ cách nhau bởi dấu cách, biểu diễn một cạnh nối đỉnh $u$ và $v$ ($1 \le u, v \le N$, $u \neq v$).

Dòng tiếp theo chứa số lượng truy vấn $Q$ ($1 \le Q \le 100\,000$).

$Q$ dòng tiếp theo, mỗi dòng chứa một truy vấn có một trong hai dạng sau:

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

Dữ liệu ra

In ra $Q$ dòng, mỗi dòng là giá trị cần đưa ra sau khi thực hiện mỗi truy vấn theo thứ tự.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

2
7
7
1