题目描述

给出一颗带边权的无向连通边仙人掌，多次询问两点之间的点不重复的路径的边权异或和的最小值。

注意：原图可能有重边和自环。一对重边构成的环也被认为是环，自环显然不影响这道题。

输入格式

第一行三个整数 $n,m,k$，其中 $n$ 表示点数，$m$ 表示边数，$k$ 表示询问数。

接下来 $m$ 行，每行三个整数 $l_i,r_i,v_i$，表示在 $l_i,r_i$ 之间有一条边权为 $v_i$ 的边。

接下来 $k$ 行，每行两个整数 $l_i,r_i$，表示询问 $l_i,r_i$ 之间的点不重复路径的边权异或值的最小值。

输出格式

共 $k$ 行，每行一个整数，依次表示第 $i$ 次询问的答案。

4 4 3
1 2 1
2 3 2
3 4 3
4 2 4
1 4
1 3
2 4

0
3
1

提示

样例解释

第一个询问：$1\to2\to3\to4,1\bigoplus2\bigoplus3=0$；

第二个询问：$1\to2\to3,1\bigoplus2=3$；

第三个询问：$2\bigoplus3=1$。

数据范围

对于所有数据，$n\le5\times10^5,k\le10^5,v\le10^9$，具体范围如下：

Subtask	$n\le$	$k\le$	$v\le$	分值
$0$	$10$	$50$	$2^{5}-1$	$10$
$1$	$100$	$3000$	$2^{15}-1$	$20$
$2$	$10^4$	$10^5$	$2^{20}-1$	$30$
$3$	$5\times10^5$		$2^{30}-1$	$40$

特别说明

本题数据不是很好造，而且有很多种错误的或者时间复杂度偏高的解法，因此可能较为卡常。欢迎提交 Hack 数据！

目前不保证被卡掉的常见错误解法：

1. 我试试 $nk\log V$ 能不能过？
2. 我认为 $k\log^4$ 的重链剖分可以过？
3. 我猜测 $k\log^3$ 的长链剖分/倍增线性基可以过？
4. 我觉得 $(n\log n)^{\frac{4}{3}}$ 的树分块+线性基可以过？
5. 各种边界问题一类的。