贵公司的政策规定，每位员工都可以报销与他们家和办公室之间最短距离成比例的金额。这导致了一个漏洞：许多员工故意搬到很远的地方，以索取尽可能多的报销款。

有一名员工将这一政策利用到了极致，甚至有让你破产的风险。你必须在明年取消该政策之前找到阻止这种情况的方法。然而，规则非常严格：只要员工能记录下他们所经过的距离，你就必须报销。

突然，你灵光一闪：没有任何地方规定你必须使用欧几里得距离！你开始研究更微妙的距离函数，现在你有了第一个原型：异或距离（XOR distance）。路径的长度定义为路径上各条边长度的异或和（而不是求和）。两个位置之间的距离定义为它们之间最短路径的长度。

你需要依次在运输网络上测试这一原则，并考虑每位员工的位置。

输入格式

• 第一行包含三个整数 $n$ ($2 \le n \le 10^4$)，$m$ ($n - 1 \le m \le 10^5$) 和 $q$ ($1 \le q \le 10^5$)，分别表示节点数、边数和询问数。
• $m$ 行描述边。每行包含三个整数 $x, y, w$ ($1 \le x, y \le n, x \neq y$ 且 $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
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

样例输出 2

1
5
0
5
0