暂无测试数据。

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

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

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

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

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

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

注意： 异或 在 C/C++ 的计算符号为 ^，

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

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

输入格式

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

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

接下来 $m$ 行，每行包含两个整数 $x,y$，表示蒜头君想知道从房间 $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