Bajtazar 在圓周率日收到了一座森林（無向無環圖）作為禮物，該森林有 $n$ 個頂點。森林中的頂點編號為 $1$ 到 $n$，邊則被賦予了正整數長度。此外，每個頂點都有一個由整數表示的顏色。最初，所有頂點的顏色均為 $0$。

由於這份禮物是你送給 Bajtazar 的，你的任務是回答 Bajtazar 關於這座森林的查詢。每個查詢屬於以下類型之一：

• $1\ a_i\ b_i\ d_i$ – Bajtazar 在森林中加入一條長度為 $d_i$ 的無向邊，連接頂點 $a_i$ 和 $b_i$。保證加入該邊後，圖中仍然不會出現環。
• $2\ a_i\ b_i$ – Bajtazar 從森林中移除連接頂點 $a_i$ 和 $b_i$ 的邊。
• $3\ v_i\ z_i\ k_i$ – Bajtazar 將所有從頂點 $v_i$ 出發，且距離 $v_i$ 不超過 $z_i$ 的頂點重新塗上顏色 $k_i$。此處兩頂點間的距離定義為它們之間唯一路徑上所有邊的長度總和。
• $4\ u_i$ – Bajtazar 詢問你頂點 $u_i$ 目前的顏色。

輸入格式

輸入的第一行包含三個整數 $n, m$ 和 $q$ ($2 \le n \le 200\,000$; $0 \le m \le n - 1$; $1 \le q \le 200\,000$)，分別代表森林中的頂點數量、初始邊數以及查詢數量。

接下來的 $m$ 行描述森林的初始邊。第 $i$ 行包含三個整數 $a_i, b_i$ 和 $d_i$ ($1 \le a_i, b_i \le n$; $1 \le d_i \le 10^9$)，表示頂點 $a_i$ 和 $b_i$ 之間有一條長度為 $d_i$ 的邊。

接下來的 $q$ 行描述查詢，格式如題目所述。在所有查詢中，$1 \le a_i, b_i, v_i, u_i \le n$, $1 \le d_i \le 10^9$, $0 \le z_i \le 10^{15}$ 以及 $1 \le k_i \le 10^9$。

保證給定的 $m$ 條邊描述了一個合法的森林，且圖在每次修改後仍保持為合法的森林。此外，保證不會出現移除森林中不存在的邊的查詢。

同時保證至少會出現一個第四類型的查詢。

輸出格式

輸出應包含與輸入中第四類型查詢數量相同的行數。每一行應包含一個整數，即 Bajtazar 詢問的頂點顏色。

範例

輸入 1

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

輸出 1

0
5
3
0
0

子任務

• 在某些測試群組中，沒有第一或第二類型的查詢，且滿足 $m = n - 1$。
• 在某些測試群組中，所有第三類型的查詢均滿足 $z_i = 10^{15}$。

對於上述每一種情況，至少存在一個滿足該條件的測試群組。這些群組對於上述兩個條件可能是互斥的，也可能不是。