Terdapat graf terhubung $G$ yang terdiri atas $N$ simpul dan $M$ sisi tak berarah berbobot. Dalam $G$, bobot suatu jalur diperoleh dengan melakukan XOR terhadap bobot semua sisi pada jalur tersebut. Perhatikan bahwa satu sisi boleh dilalui beberapa kali; dalam hal itu, bobotnya di-XOR sebanyak kali sisi itu dilalui.

Untuk simpul $u$ dan $v$, misalkan $d(u, v)$ adalah bobot maksimum jalur dari $u$ ke $v$.

Anda perlu menjawab $Q$ kueri berbentuk berikut:

Diberikan $l$ dan $r$, untuk semua $i$ dan $j$ yang memenuhi $l \le i < j \le r$, carilah XOR dari nilai-nilai $d(i, j)$.

Masukan

Baris pertama berisi tiga bilangan bulat $N$, $M$, dan $Q$ ($1 \le N, M, Q \le 10^5$).

Masing-masing dari $M$ baris berikutnya berisi tiga bilangan bulat $u$, $v$, dan $w$, yang menjelaskan sisi berbobot $w$ yang menghubungkan simpul $u$ dan $v$ ($1 \le u, v \le N$, $0 \le w < 2^{30}$). Perhatikan bahwa sisi ganda dan gelang diperbolehkan dalam soal ini.

Masing-masing dari $Q$ baris berikutnya menjelaskan satu kueri dan berisi dua bilangan bulat $l$ dan $r$ ($1 \le l < r \le N$).

Keluaran

Untuk setiap kueri, cetak jawaban dalam baris tersendiri.

Contoh

Masukan 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

Keluaran 1

0
713437792
738051848
716356296
736682272
1003204975
987493236