给定一个包含 $N$ 个顶点和 $M$ 条带权无向边的连通图 $G$。在 $G$ 中，路径的权值定义为路径上所有边权值的异或和。注意，允许沿同一条边多次行走，在这种情况下，你需要将该边的权值异或相应次数。

对于顶点 $u$ 和 $v$，令 $d(u, v)$ 为从 $u$ 到 $v$ 的路径的最大权值。

你需要回答 $Q$ 个如下形式的询问： 给定 $l$ 和 $r$，对于所有满足 $l \le i < j \le r$ 的 $i$ 和 $j$，求 $d(i, j)$ 的异或和。

输入格式

第一行包含三个整数 $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