Cho một cây gồm $N$ đỉnh. Các đỉnh được đánh số từ 1 đến $N$, và đỉnh $i$ chứa một số nguyên $A_i$. Ban đầu, $A_i = 0$ với mọi $i$ ($1 \le i \le N$).

Bạn cần thực hiện tổng cộng $Q$ truy vấn sau:

• 1 u v: Khi coi gốc của cây là đỉnh $u$, cộng 1 vào $A_i$ của tất cả các đỉnh $i$ trong cây con có gốc là $v$.
• 2 u v: Cộng 1 vào $A_i$ của tất cả các đỉnh $i$ trên đường đi duy nhất từ $u$ đến $v$.
• 3 v: In ra $\sum_{i = 1}^{N} A_i \times dist(v, i)$. $dist(x, y)$ là số cạnh trên đường đi từ $x$ đến $y$.

Dữ liệu vào

Dòng đầu tiên chứa $N$ ($1 \le N \le 200{,}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ố $u$ và $v$ cách nhau bởi dấu cách, cho biết có một cạnh nối $u$ và $v$ ($1 \le u, v \le N$).

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

$Q$ dòng tiếp theo, mỗi dòng là một truy vấn có một trong các dạng sau:

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

Luôn có ít nhất một truy vấn loại 3.

Dữ liệu ra

Với mỗi truy vấn loại 3, in ra kết quả trên một dòng riêng biệt, theo thứ tự xuất hiện.

Ví dụ

Dữ liệu vào

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

Dữ liệu ra

1
5