{"raw_statement":[{"iden":"background","content":"神明愚弄凡间，所谓命运，不过是神明掷出的一颗骰子而已。\n\n花朵等不到的蝴蝶，终究成了一分蹊跷的梦，一轮轮再次重启。\n\n神明的提线木偶一次又一次的被扼住脖颈, 以爱的名义，消逝在时间的花海里。\n\n无数的执念背后，都有一个被扭曲的“真理”。\n \n 你所承诺的没有出现，彻夜无眠，或许我只是自作主张的，替你爱了一次人间\n\n“最虔诚者只祝祷，不虔诚者才有所求。”\n\n没有过信仰，因为舍命救了一个人，有幸来到了天堂。\n "},{"iden":"statement","content":"给定一棵 $n$ 个结点的无根树，每条边有非负整数边权。结点由 $1 \\sim n$ 编号。\n\n对于每一个点对 $(x, y)$，定义 $(x, y)$ 的距离 $\\operatorname{dis}(x, y)$ 为 $x,y$ 两点之间唯一简单路径上边权的异或和。\n\n给定两个结点 $x, y$，定义点 $i$ 的价值 $\\operatorname{val}_{x, y}(i)$ 为 $(x, i)$ 与 $(y, i)$ 的距离的异或和，即\n\n$$ \\operatorname{val}_{x, y}(i) = \\operatorname{dis}(x, i) \\oplus \\operatorname{dis}(y, i) \\textsf{。} $$\n\n现在有 $q$ 次询问，每次询问给出四个整数 $x, y, l, r$，求 $\\displaystyle \\bigoplus_{i = l}^{r} \\operatorname{val}_{x, y}(i)$ 的值，即求\n\n$$ \\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{。} $$\n\n上述公式中，$\\oplus$ 表示二进制按位异或。"},{"iden":"input","content":"第一行，两个整数 $n, q$。\n\n接下来 $n - 1$ 行，每行三个整数 $u, v, w$，表示 $u, v$ 之间有一条权值为 $w$ 的边。\n\n接下来 $q$ 行，每行四个整数 $x,y,l,r$，表示一次询问。"},{"iden":"output","content":"输出 $q$ 行，每行一个整数，为每次询问的答案。"},{"iden":"note","content":"**【样例解释】**\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/oew00pa7.png)\n\n输入给出的树如上图所示。对于点对的距离，有\n\n- $\\operatorname{dis}(1, 1) = \\operatorname{dis}(1, 3) = \\operatorname{dis}(2, 2) = \\operatorname{dis}(3, 1) = \\operatorname{dis}(3, 3) = 0$ 以及\n- $\\operatorname{dis}(1, 2) = \\operatorname{dis}(2, 1) = \\operatorname{dis}(2, 3) = \\operatorname{dis}(3, 2) = 1$。\n\n第 $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$。\n\n第 $2$ 问：$\\operatorname{val}_{2, 3}(2) \\oplus \\operatorname{val}_{2, 3}(3) = (0 \\oplus 1) \\oplus (1 \\oplus 0) = 1 \\oplus 1 = 0$。\n\n---\n\n**【数据范围】**\n\n**本题采用捆绑测试。**\n\n| 子任务编号 | $n \\le$ | $q \\le$ | 分值 |\n| :----------: | :----------: | :----------: | :----------: |\n| 1 | $100$ | $10$ | 24 |\n| 2 | $10^6$ | $10$ | 14 |\n| 3 | $100$ | $10^6$ | 14 |\n| 4 | $10^6$ | $10^6$ | 48 |\n\n对于 $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}$。\n\n---\n\n**【提示】**\n\n本题最大 I/O 量达到 60 MiB，请注意 I/O 效率。"}],"translated_statement":null,"sample_group":[["3 2\n1 2 1\n2 3 1\n1 2 1 3\n2 3 2 3\n","1\n0\n"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}