题目描述

公司员工的里程报销规定十分明确：员工应当按照其住所与办公室之间的最短距离获得相应金额的报销。

这让你的圣诞装饰品零售公司十分头疼。每年花在里程报销上的钱越来越多，公司的利润也越来越少。你仔细研究报销规定，希望找到一个可以减少支出的漏洞。

规则似乎非常严格：只要员工记录了自己行驶的距离，你就必须按规定报销。突然，你想到了一点——规则并没有规定必须使用欧几里得距离。

于是你开始研究一些更特别的距离函数，并设计出了第一个原型：异或距离。

一条路径的长度定义为该路径上所有边权的按位异或值，而不是通常的边权之和。两个结点之间的距离，定义为它们之间所有路径长度中的最小值。

你构造了一个连通的带权无向图，并提出了 $q$ 个询问。每个询问要求计算两个结点之间的最短异或距离。

输入格式

第一行包含三个整数 $n,m,q$：

• $2\le n\le 10^4$：结点数量；
• $n-1\le m\le 10^5$：边数量；
• $1\le q\le 10^5$：询问数量。

接下来 $m$ 行，每行包含三个整数 $x,y,w$：

$$1\le x,y\le n,\qquad x\ne y,\qquad 0\le w\le 10^{18},$$

表示结点 $x$ 与结点 $y$ 之间有一条边权为 $w$ 的无向边。

接下来 $q$ 行，每行包含两个整数 $a,b$：

$$1\le a,b\le n,$$

表示询问结点 $a$ 与结点 $b$ 之间的最短异或距离。

任意一对不同结点之间至多有一条边，并且整个图连通。

输出格式

对于每个询问，输出一行一个整数，表示结点 $a$ 与结点 $b$ 之间的最短异或距离。

样例 1

输入

3 3 3
1 2 2
1 3 2
2 3 3
1 2
1 3
2 3

输出

1
1
0

样例 2

输入

7 10 5
1 2 45
2 3 11
2 4 46
3 4 28
3 5 59
3 6 12
3 7 3
4 5 11
5 6 23
6 7 20
1 4
2 6
3 5
1 7
5 5

输出

1
5
0
5
0