Cho đồ thị liên thông, có trọng số gồm \(N\) đỉnh, \(M\) cạnh. Xét \(Q\) truy vấn, mỗi truy vấn thuộc một trong hai loại sau:

• Truy vấn loại \(1\): có dạng \(1\) \(k\), có ý nghĩa xóa cạnh thứ \(k\);
• Truy vấn loại \(2\): có dạng \(2\) \(u\) \(v\), có ý nghĩa tìm đường đi ngắn nhất từ \(u\) đến \(v\) với giá trị của đường đi là giá trị XOR của các cạnh trên đường đi đó (có thể đi lặp cạnh) hoặc cho biết không tồn tại đường đi.

Nhắc lại, phép toán XOR (có kí hiệu là ^) được định nghĩa như sau: Kết quả của phép toán XOR giữa hai số nguyên không âm \(a\) và \(b\) là một số nguyên không âm \(c\) trong đó bit thứ \(i\) trong biểu diễn nhị phân của \(c\) sẽ là \(0\) khi và chỉ khi bit thứ \(i\) trong biểu diễn nhị phân của \(a\) và \(b\) giống nhau, ngược lại bit thứ \(i\) trong biểu diễn nhị phân của \(c\) sẽ là \(1\).

Dữ liệu vào

• Dòng đầu chứa ba số nguyên dương \(N\), \(M\), \(Q\).
• \(M\) dòng tiếp theo, mỗi dòng chứa ba số nguyên \(u_i\), \(v_i\), \(w_i\) mô tả cạnh từ \(u_i\) đến \(v_i\) với trọng số \(w_i\).
• \(Q\) dòng tiếp theo, mỗi dòng mô tả một trong hai loại truy vấn:
  • \(1\) \(k\) - xóa cạnh thứ \(k\).
  • \(2\) \(u\) \(v\) - truy vấn đường đi từ \(u\) đến \(v\).

Dữ liệu ra

• Với mỗi truy vấn loại 2, in ra giá trị nhỏ nhất hoặc \(-1\) nếu không có đường đi.

Input 1

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

Output 1

1
2
-1

Các subtask

• Subtask 1 (30%): \(M = N - 1\);
• Subtask 2 (30%): \(M = N\);
• Subtask 3 (30%): \(Q=1, N,w \le 1000\)
• Subtask 4 (10%): Không có ràng buộc nào thêm.