C. 最短路

题目描述

小W有一棵 $n$ 个点的带权树，现在他想从 $S$ 走到 $T$。定义一条路径的长度为上面所有边的长度的异或和（如果不知道异或是什么可以戳 Wikipedia，异或和就是所有数异或的和）。

但是他觉得直接沿着树上的边走太慢了，于是他决定新建一些边。他有 $m$ 个修建计划，第 $i$ 个是在 $u$ 和 $v$ 之间修建一条长为 $w$ 的边。

现在他有一些询问，每个询问形如 $S, T, l, r$，表示如果动用 $[l,r]$ 区间内的所有修建计划，他从 $S$ 走到 $T$ 的最短路长度应该是多少。

输入格式

第一行三个整数 $n$，$m$，$q$。

接下来 $n-1$ 行，每行三个整数 $u$，$v$，$w$，表示原本树上有一条 $u$ 和 $v$ 之间有一条长度为 $w$ 的边。

接下来 $m$ 行，第 $i$ 行有三个整数 $u$，$v$，$w$，表示一个修建计划。

接下来 $q$ 行，每行四个整数 $S$，$T$，$l$，$r$，表示一组询问。

输出格式

输出共 $q$ 行，表示每组询问的答案。

样例1

input

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

output

0
0
1

限制与约定

对于 $20\%$ 的数据，$n, m, q \le 1000$。

对于 $50\%​$ 的数据，$n, m, q \le 5 * 10^4​$。

对于 $100\%$ 的数据，$1 \le n, m, q \le 3 * 10^5, 1 \le w \le 10^9$。

时间限制：3s

空间限制：512MB

提示

输入输出量可能很大，请使用较快的I/O方式。

下载

样例数据下载