题目描述

本题为一道挑战题。

所谓数树，就是让你看看无根树上的边上的数了！

当然，由于出题人很喜欢异或，数树的内容当然是求它们的异或值了。

我们定义两个点 $x,y$ 的异或距离 $dis(x,y)$ 为它们之间所隔边权的异或和。

定义 $val_{x,y}(p)=dis(x,p)\oplus dis(y,p)$。

当然，这样这题还有点简单，所以我们要求你对给定的 $(x,y,l,r)$，求：

$$\displaystyle \bigoplus_{i = l}^{r} \operatorname{val}_{x, y}(i)$$

输入格式

从文件 tree.in 中读入数据。

第一行一个正整数 $n$，表示树上节点的个数。

接下来 $n-1$ 行，描述树的结构，每行三个正整数 $u,v,w$，分别表示无向边的两个端点编号和边权。

接下来一行一个正整数 $q$，表示询问个数。

接下来 $q$ 行，每行四个正整数 $(x,y,l,r)$，表示询问。

输出格式

输出到文件 tree.out 中。

输出 $q$ 行，对每组询问，输出一个非负整数，表示答案。

样例

2
1 2 1
1
1 1 1 1

0

数据范围

对 $100\%$ 的数据，$1\le n,q\le 10^5$，$1\le u,v\le n$，$1\le w\le 10^9$，输入的是一棵树，$1\le x,y,l,r\le n$，$l\le r$。

本题采用子任务捆绑测试。

子任务	$q$	特殊性质	分数
#1	$\le 10$	-	$14$
#2	-	$n\le 10$	$8$
#3		树是一条链
#4		树是一个菊花
#5	$\le 10000$	$q\le 10000$	$12$
#6	-		$50$

对于标 - 的部分，即为“无特殊限制”。