給定一棵包含 $N$ 個頂點的樹。頂點編號由 $1$ 到 $N$ 的連續整數組成，且第 $i$ 個頂點包含變數 $A_i$。初始時 $A_i = 0$ ($1 \le i \le N$)。

你需要處理 $Q$ 個查詢。每個查詢屬於下列其中一種：

• “1 $u$ $v$”：以 $u$ 為樹根，考慮頂點 $v$ 的子樹，並將該子樹中每個頂點 $i$ 的 $A_i$ 加 $1$。
• “2 $u$ $v$”：對於 $u$ 到 $v$ 之間唯一簡單路徑上的每個頂點 $i$，將 $A_i$ 加 $1$。
• “3 $v$”：輸出 $\sum_{i=1}^{N} \text{dist}(v, i) \cdot A_i$，其中 $\text{dist}(x, y)$ 為從頂點 $x$ 到頂點 $y$ 路徑上的邊數。

輸入格式

第一行包含一個整數 $N$，代表頂點數量 ($1 \le N \le 2 \cdot 10^5$)。

接下來 $N - 1$ 行包含樹的描述。每行包含兩個以空格分隔的整數 $u$ 和 $v$，代表有一條邊連接 $u$ 和 $v$ ($1 \le u, v \le N$)。保證給定的圖是一棵樹。

下一行包含一個整數 $Q$，代表查詢數量 ($1 \le Q \le 2 \cdot 10^5$)。

接下來 $Q$ 行包含查詢，每行一個。每個查詢皆以如上所述的格式給出 ($1 \le u, 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