Bajtazar nhân ngày số $\pi$ đã nhận được một món quà là một khu rừng (đồ thị vô hướng không có chu trình) với $n$ đỉnh. Trong khu rừng này, các đỉnh được đánh số từ $1$ đến $n$, và các cạnh có gán các độ dài là số nguyên dương. Ngoài ra, mỗi đỉnh đều có một màu được mô tả bằng một số nguyên. Ban đầu, tất cả các đỉnh đều có màu $0$.

Vì bạn là người đã tặng món quà này cho Bajtazar, nhiệm vụ của bạn bây giờ là trả lời các truy vấn của Bajtazar về khu rừng này. Mỗi truy vấn thuộc một trong các loại sau:

• $1\ a_i\ b_i\ d_i$ – Bajtazar thêm vào khu rừng một cạnh vô hướng có độ dài $d_i$ nối hai đỉnh $a_i$ và $b_i$. Đảm bảo rằng sau khi thêm cạnh này, đồ thị vẫn không chứa chu trình.
• $2\ a_i\ b_i$ – Bajtazar xóa khỏi khu rừng cạnh nối hai đỉnh $a_i$ và $b_i$.
• $3\ v_i\ z_i\ k_i$ – Bajtazar sơn lại màu $k_i$ cho tất cả các đỉnh có thể đi đến từ đỉnh $v_i$ và cách đỉnh $v_i$ một khoảng cách không quá $z_i$. Khoảng cách giữa hai đỉnh ở đây được định nghĩa là tổng độ dài các cạnh trên đường đi duy nhất giữa chúng.
• $4\ u_i$ – Bajtazar hỏi bạn về màu hiện tại của đỉnh $u_i$.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào chứa ba số nguyên $n, m$ và $q$ ($2 \le n \le 200\,000$; $0 \le m \le n - 1$; $1 \le q \le 200\,000$), lần lượt là số lượng đỉnh trong khu rừng, số lượng cạnh ban đầu và số lượng truy vấn.

Trong $m$ dòng tiếp theo là mô tả các cạnh của khu rừng. Dòng thứ $i$ trong số đó chứa ba số nguyên $a_i, b_i$ và $d_i$ ($1 \le a_i, b_i \le n$; $1 \le d_i \le 10^9$), nghĩa là các đỉnh $a_i$ và $b_i$ được nối với nhau bằng một cạnh có độ dài $d_i$.

Trong $q$ dòng tiếp theo là mô tả các truy vấn theo định dạng đã nêu trong đề bài. Trong tất cả các truy vấn, ta có $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}$ và $1 \le k_i \le 10^9$.

Đảm bảo rằng $m$ cạnh được cho mô tả một khu rừng hợp lệ, đồ thị vẫn là một khu rừng hợp lệ sau mỗi lần sửa đổi và sẽ không bao giờ có truy vấn yêu cầu xóa một cạnh không tồn tại trong khu rừng tại thời điểm đó.

Đảm bảo rằng sẽ có ít nhất một truy vấn loại bốn.

Dữ liệu ra

Dữ liệu ra cần chứa số dòng bằng với số lượng truy vấn loại bốn. Mỗi dòng chứa một số nguyên duy nhất – màu của đỉnh mà Bajtazar đã hỏi.

Ví dụ

Dữ liệu vào 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

Dữ liệu ra 1

0
5
3
0
0

Nhiệm vụ con

• Trong một số nhóm test, không có truy vấn loại một hoặc loại hai và $m = n - 1$.
• Trong một số nhóm test, với tất cả các truy vấn loại ba, ta có $z_i = 10^{15}$.

Đối với mỗi trường hợp nêu trên, tồn tại ít nhất một nhóm test thỏa mãn. Các nhóm test cho hai điều kiện này có thể rời nhau hoặc không.