Alice 和 Bob 喜欢在一棵有 $n$ 个顶点的树上玩游戏，顶点编号为 $1, 2, \dots, n$。他们总共进行了 $q$ 场游戏。

在第 $i$ 场游戏中，Alice 从顶点 $a_i$ 开始，Bob 从另一个不同的顶点 $b_i$ 开始。最初，除了顶点 $a_i$ 和 $b_i$ 外，所有顶点都没有颜色：顶点 $a_i$ 被 Alice 涂色，顶点 $b_i$ 被 Bob 涂色。

此后，玩家轮流进行总共 $k_i$ 次移动：Alice 先手，Bob 后手，然后 Alice 进行第三次移动，依此类推。在每次移动中，当前玩家移动到一个相邻的顶点并将其涂色。注意，一个顶点可以被重新涂色：在任何时刻，每个被涂色的顶点都具有最近到达该顶点的玩家的颜色。

设 Alice 颜色的最终顶点数为 $A$，Bob 颜色的最终顶点数为 $B$。Alice 希望最大化 $(A - B)$，而 Bob 希望最小化这个数值。

对于每场游戏，如果双方都采取最优策略，求出 $(A - B)$ 的值。

输入格式

输入包含零个或多个测试用例，并以文件结束符（EOF）终止。对于每个测试用例：

第一行包含两个整数 $n$ 和 $q$ ($2 \le n \le 2 \cdot 10^5$, $1 \le q \le 2 \cdot 10^5$)。

接下来的 $(n - 1)$ 行，每行包含两个整数 $u_i$ 和 $v_i$，表示顶点 $u_i$ 和 $v_i$ 之间的一条边 ($1 \le u_i, v_i \le n$)。保证输入构成一棵树。

最后 $q$ 行，每行包含三个整数 $a_i, b_i$ 和 $k_i$ ($1 \le a_i, b_i \le n, 1 \le k_i \le 2n, a_i \neq b_i$)。

保证所有 $n$ 的总和与所有 $q$ 的总和均不超过 $2 \cdot 10^5$。

输出格式

对于每个测试用例，输出一个整数，表示该差值。

样例

输入 1

4 3
1 2
2 3
3 4
1 4 1
1 4 2
1 4 3

输出 1

1
0
2