Cho đồ thị ~G~ vô hướng có ~n~ đỉnh và ~m~ cạnh. Hãy trả lời ~q~ truy vấn sau, mỗi truy vấn thuộc một trong ba loại:

1. ~Zero(u,v)~: Thay đổi trọng số của cạnh ~(u,v)~ về ~0~.
2. ~Original(u,v)~: Thay đổi trọng số của cạnh ~(u,v)~ về giá trị ban đầu.
3. ~CalWeight()~: Trả về trọng số cây khung nhỏ nhất của ~G~.

Dữ liệu vào:

• Dòng đầu tiên chứa ba số nguyên ~n,m,q~ ~(1≤n≤2000; 1≤m≤20000; 1≤q≤5000)~ lần lượt cho biết số lượng đỉnh, số lượng cạnh của ~G~ và số lượng truy vấn.
• ~m~ dòng tiếp theo mõi dòng chứa 2 số nguyên ~u,v~ ~(1≤u,v≤n)~ và ~w~ ~(1≤w≤10^9)~ cho biết cạnh ~(u,v)~ có trọng số ~w~.
• Dòng thứ ~i~ trong ~q~ dòng tiếp theo tương ứng với truy vấn thứ ~i~. Mỗi truy vấn bắt đầu bằng 1 số nguyên ~type~ thể hiện loại truy vấn, nếu ~type=1~ hoặc ~type=2~ thì theo sau là 2 số nguyên ~u,v~ cho biết tham số của truy vấn.

Kết quả: Với mỗi truy vấn loại 3 in ra một số nguyên cho biết câu trả lời của truy vấn đó.

Ví dụ:

Input

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

Output

3
2
3 

Ràng buộc:

• Có 80% số test có ~1≤n≤100; m≤1000; q≤1000~
• Có 10% số test khác có ~1≤n≤2000~ và không có quy vấn loại 2
• Có 10% số test còn lại không có ràng buộc gì thêm.