题目背景

神明愚弄凡间，所谓命运，不过是神明掷出的一颗骰子而已。

花朵等不到的蝴蝶，终究成了一分蹊跷的梦，一轮轮再次重启。

神明的提线木偶一次又一次的被扼住脖颈, 以爱的名义，消逝在时间的花海里。

无数的执念背后，都有一个被扭曲的“真理”。

你所承诺的没有出现，彻夜无眠，或许我只是自作主张的，替你爱了一次人间

“最虔诚者只祝祷，不虔诚者才有所求。”

没有过信仰，因为舍命救了一个人，有幸来到了天堂。

题目描述

给定一棵 $n$ 个结点的无根树，每条边有非负整数边权。结点由 $1 \sim n$ 编号。

对于每一个点对 $(x, y)$，定义 $(x, y)$ 的距离 $\operatorname{dis}(x, y)$ 为 $x,y$ 两点之间唯一简单路径上边权的异或和。

给定两个结点 $x, y$，定义点 $i$ 的价值 $\operatorname{val}_{x, y}(i)$ 为 $(x, i)$ 与 $(y, i)$ 的距离的异或和，即

$$\operatorname{val}_{x, y}(i) = \operatorname{dis}(x, i) \oplus \operatorname{dis}(y, i) \textsf{。} $$

现在有 $q$ 次询问，每次询问给出四个整数 $x, y, l, r$，求 $\displaystyle \bigoplus_{i = l}^{r} \operatorname{val}_{x, y}(i)$ 的值，即求

$$\operatorname{val}_{x, y}(l) \oplus \operatorname{val}_{x, y}(l + 1) \oplus \cdots \oplus \operatorname{val}_{x, y}(r - 1) \oplus \operatorname{val}_{x, y}(r) \textsf{。} $$

上述公式中，$\oplus$ 表示二进制按位异或。

输入格式

第一行，两个整数 $n, q$。

接下来 $n - 1$ 行，每行三个整数 $u, v, w$，表示 $u, v$ 之间有一条权值为 $w$ 的边。

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

输出格式

输出 $q$ 行，每行一个整数，为每次询问的答案。

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

1
0

提示

【样例解释】

输入给出的树如上图所示。对于点对的距离，有

• $\operatorname{dis}(1, 1) = \operatorname{dis}(1, 3) = \operatorname{dis}(2, 2) = \operatorname{dis}(3, 1) = \operatorname{dis}(3, 3) = 0$ 以及
• $\operatorname{dis}(1, 2) = \operatorname{dis}(2, 1) = \operatorname{dis}(2, 3) = \operatorname{dis}(3, 2) = 1$。

第 $1$ 问：$\operatorname{val}_{1, 2}(1) \oplus \operatorname{val}_{1, 2}(2) \oplus \operatorname{val}_{1, 2}(3) = (0 \oplus 1) \oplus (1 \oplus 0) \oplus (0 \oplus 1) = 1 \oplus 1 \oplus 1 = 1$。

第 $2$ 问：$\operatorname{val}_{2, 3}(2) \oplus \operatorname{val}_{2, 3}(3) = (0 \oplus 1) \oplus (1 \oplus 0) = 1 \oplus 1 = 0$。

---

【数据范围】

本题采用捆绑测试。

子任务编号	$n \le$	$q \le$	分值
1	$100$	$10$	24
2	$10^6$		14
3	$100$	$10^6$
4	$10^6$		48

对于 $100\%$ 的数据，保证 $1 \le n, q \le {10}^6$，$1 \le u, v, x, y \le n$，$1 \le l \le r \le n$，$0 \le w < 2^{31}$。

---

【提示】

本题最大 I/O 量达到 60 MiB，请注意 I/O 效率。