Cho một đồ thị liên thông $G$ gồm $N$ đỉnh và $M$ cạnh vô hướng có trọng số. Trong $G$, trọng số của một đường đi được tính bằng cách XOR trọng số của tất cả các cạnh trên đường đi đó. Lưu ý rằng bạn được phép đi qua một cạnh nhiều lần, trong trường hợp đó, bạn sẽ XOR trọng số của cạnh đó số lần tương ứng.

Với hai đỉnh $u$ và $v$, gọi $d(u, v)$ là trọng số lớn nhất của một đường đi từ $u$ đến $v$.

Bạn cần trả lời $Q$ truy vấn có dạng sau: Cho $l$ và $r$, với mọi $i$ và $j$ sao cho $l \le i < j \le r$, hãy tìm giá trị XOR của các giá trị $d(i, j)$.

Dữ liệu vào

Dòng đầu tiên chứa ba số nguyên $N$, $M$ và $Q$ ($1 \le N, M, Q \le 10^5$).

$M$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $u$, $v$ và $w$, mô tả một cạnh có trọng số $w$ nối giữa hai đỉnh $u$ và $v$ ($1 \le u, v \le N$, $0 \le w < 2^{30}$). Lưu ý rằng bài toán này cho phép tồn tại đa cạnh và khuyên (loop).

$Q$ dòng tiếp theo, mỗi dòng mô tả một truy vấn và chứa hai số nguyên $l$ và $r$ ($1 \le l < r \le N$).

Dữ liệu ra

Với mỗi truy vấn, in ra kết quả trên một dòng riêng biệt.

Ví dụ

Dữ liệu vào 1

8 10 7
1 2 662784558
3 2 195868257
3 4 294212653
4 5 299265014
6 5 72652580
6 7 29303370
7 8 183954825
2 1 752722885
5 3 197591314
8 4 877461873
4 8
5 7
6 7
2 3
7 8
3 4
2 7

Dữ liệu ra 1

0
713437792
738051848
716356296
736682272
1003204975
987493236