该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

众所周知，qym 很喜欢玩游戏，最近他又玩了一款解密类的迷宫游戏

这个游戏的地图中存在 $n$ 个房间，这 $n$ 个房间通过 $n - 1$ 条道路相连，且题目保证没有房间不可达。

而每条道路有可能是不同的，有的可能存在陷阱，有的可能存在怪物，所以 qym 如果想通过一条道路，需要扣除相应的血量。

qym 作为一个大科(wai)学(gua)家，他给自己在游戏中增加了一次瞬间移动的机会，他可以从编号为 $x$ 的房间直接瞬移到 $y$ 的房间

因为 qym 很菜，所以虽然增加了一次瞬间移动，但是这次瞬间移动因为 $BUG$，依旧需要扣除血量，而扣除的血量则为 $x$ 移动到 $y$ 路径上所有道路需要扣除血量的 异或和

现在 qym 想知道，自己从 $x$ 房间移动到 $y$ 房间需要扣除多少点血量

注意： 异或 在 C/C++ 的计算符号为 ^， 异或也叫半加运算，其运算法则相当于不带进位的二进制加法：二进制下用 1 表示真， 0 表示假 则异或的运算法则为：0 ^ 0 = 0，1 ^ 0=1，0 ^ 1=1，1 ^ 1=0（同为 0 ，异为 1），这些法则与加法是相同的，只是不带进位，所以异或常被认作不进位加法。

例如 $1$ $\hat{}$ $5 = 7$, $5$ $\hat{}$ $5 = 0$

输入格式

输入第一行包含两个正整数 $n, m$，表示总共有 $n$ 个房间和 $m$ 次询问

接下来 $n - 1$ 行每行包含三个整数 $u,v,w$ 分别表示房间 $u$ 到房间 $v$ 存在一条道路，通过这条道路需要扣除 $w$ 点血量

接下来 $m$ 行，每行包含两个整数 $x,y$，表示 qym 想知道从房间 $x$ 瞬间移动到房间 $y$ 需要扣除多少血量

输出格式

对于每次询问输出一个整数，表示需要扣除的血量

数据范围

对于 $30\%$ 的数据，$n,m \leq 10$

对于 $70\%$ 的数据，$n,m \leq 1000$

对于 $100\%$ 的数据，$n,m \leq 100000, x,y \leq n$

对于 $90\%$ 的数据每个点 $i$ 均与 $floor(i / 2)$ 有边

样例输入

5 5
2 1 12
3 1 5
4 3 7
5 4 2
4 3
5 3
2 1
3 2
4 1

样例输出

7
5
12
9
2