题目描述

灵界和源堡的眷者，源自古代的诡秘，漫长历史的见证，贝克兰德魔术和戏剧表演的保护者/ 贝克兰德所有贫困孩子的保护者，伟大的格尔曼·斯帕罗。

无尽之海（《诡秘之主》·卷三曲）。

苏尼亚海上有 $n$ 个岛屿，$m$ 条双向航道连接了这些岛屿。每条航道 $(x_i, y_i)$ 上都有一些实力为 $z_i$ 的海盗侵扰。

海上冒险家 $\text{Germain Sparrow}$ 决定在这些航道上与金镑海盗们友好交流，以暴力说服他们献出自己的悬赏金。

定义一次从 $x$ 点到 $y$ 点的旅行的 收获 $val$ 为路径上实力最强的海盗的实力。

但 $\text{Germain Sparrow}$ 深知可持续发展的重要性，所以每次都会选择收获最小的一条路径旅行。

他总共会旅行 $q$ 次，每次从 $st_i$ 到 $en_i$，请告诉他每次旅行的收获。

输入格式

第一行三个整数 $n,m,q$，含义如题目所述。
第二到 $m +1$ 行，每行三个整数 $x,y,z$，表示岛屿 $x$ 到岛屿 $y$ 有一条最强海盗实力为 $z$ 的航道。
第 $m + 2$ 到 $m + q + 1$ 行，每行两个整数 $st,en$，表示一次从点 $st$ 到点 $en$ 的旅行。

输出格式

为了输出便利，请输出 $\displaystyle \bigoplus_{i=1}^q ans_i \times i$，$\bigoplus$ 为异或和。

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

2

数据规模与约定

对于 $30\%$ 的数据，$1 \le n \le 10^3$，$n - 1 \le m \le \frac{n\times(n-1)}{2}$，$1\le q \le 10^3$。
对于 $70\%$ 的数据，$1 \le n \le 10^5$，$n - 1 \le m \le 10^5$，$1\le q \le 10^3$。
对于 $100\%$ 的数据，$1 \le n \le 10^5$，$n - 1 \le m \le 3\times 10^6$，$1\le q \le 10^7$，$1 \le z_i \le 10^9$，数据保证图联通（可能有重边）。

Warning： 请使用较快的 I/O 方式。