給定一個包含 $N$ 個頂點與 $M$ 條帶權無向邊的連通圖 $G$。在 $G$ 中，路徑的權重定義為該路徑上所有邊權的 XOR 和。請注意，路徑允許重複經過同一條邊，若重複經過，則該邊的權重需被 XOR 相應次數。

對於頂點 $u$ 與 $v$，令 $d(u, v)$ 為從 $u$ 到 $v$ 的路徑中，權重的最大值。

你需要回答 $Q$ 個查詢，格式如下： 給定 $l$ 與 $r$，對於所有滿足 $l \le i < j \le r$ 的 $i$ 與 $j$，求出所有 $d(i, j)$ 的 XOR 和。

輸入格式

第一行包含三個整數 $N, M, Q$ ($1 \le N, M, Q \le 10^5$)。

接下來 $M$ 行，每行包含三個整數 $u, v, w$，描述一條連接頂點 $u$ 與 $v$、權重為 $w$ 的邊 ($1 \le u, v \le N, 0 \le w < 2^{30}$)。請注意，本題允許存在多重邊與自環。

接下來 $Q$ 行，每行描述一個查詢，包含兩個整數 $l$ 與 $r$ ($1 \le l < r \le N$)。

輸出格式

對於每個查詢，請在獨立的一行中輸出答案。

範例

輸入 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

輸出 1

0
713437792
738051848
716356296
736682272
1003204975
987493236