Bạn có một cây gồm $N$ đỉnh. Các đỉnh được đánh số bằng các số nguyên liên tiếp từ $1$ đến $N$, và đỉnh thứ $i$ chứa biến $A_i$. Ban đầu $A_i = 0$ ($1 \le i \le N$).

Bạn cần xử lý $Q$ truy vấn. Mỗi truy vấn thuộc một trong các loại sau:

• “1 $u$ $v$”: Đặt gốc của cây tại đỉnh $u$, xét cây con của đỉnh $v$, và với mỗi đỉnh $i$ trong cây con của $v$, tăng $A_i$ thêm một đơn vị.
• “2 $u$ $v$”: Với mỗi đỉnh $i$ nằm trên đường đi đơn duy nhất từ $u$ đến $v$, tăng $A_i$ thêm một đơn vị.
• “3 $v$”: In ra $\sum_{i=1}^{N} \text{dist}(v, i) \cdot A_i$, trong đó $\text{dist}(x, y)$ là số cạnh trên đường đi từ đỉnh $x$ đến đỉnh $y$.

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên $N$, số lượng đỉnh ($1 \le N \le 2 \cdot 10^5$).

$N - 1$ dòng tiếp theo chứa mô tả của cây. Mỗi dòng chứa hai số nguyên $u$ và $v$ cách nhau bởi một dấu cách, nghĩa là có một cạnh nối giữa $u$ và $v$ ($1 \le u, v \le N$). Đảm bảo rằng đồ thị thu được là một cây.

Dòng tiếp theo chứa một số nguyên $Q$, số lượng truy vấn ($1 \le Q \le 2 \cdot 10^5$).

$Q$ dòng tiếp theo chứa các truy vấn, mỗi truy vấn trên một dòng. Mỗi truy vấn được đưa ra theo một trong các định dạng mô tả ở trên ($1 \le u, v \le N$). Bạn có thể giả định rằng 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.

Ví dụ

Dữ liệu vào 1

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

1
5