游乐场可以看作有 $n$ 个游乐点，$n-1$ 条道路连接的树，每条道路长度都为 $1$ 。

有一些游乐点上会有游客。

现在游乐园将在游乐点 $r$ 开展庆典，在游乐点 $v$ 设置打卡点。

在接下来 $n-1$ 秒，所有游客将会一同到达游乐点 $r$ 点以举行庆典。具体的，第 $i$ 秒时，所有距离游乐点 $r$ 为 $n-i$ 的游客将会向着距离 $r$ 更近的地方走一步。 第 $0$ 秒时大家都在原地。

若两名游客 $a,b(a\not= b)$ 在第 $i$ 秒时处于同一个游乐点且在 $i-1$ 秒时不处于同一个游乐点，设第 $i$ 秒他们都处于游乐点 $x$ ，$a,b$ 将各自获得 $\frac{x}{2}$ 的欢乐值。

设 $c$ 是 $0\sim n-1$ 中最大的，满足第 $c$ 秒，游客 $a$ 处于打卡点 $v$ ，那么第 $c$ 秒 $a$ 将在此打卡，游乐场将会把 $a$ 当前的欢乐值计入总欢乐值中。若不存在这样的 $c$ ，那么将不计入总欢乐值。

现在需要你输出 $n-1$ 秒过后，总欢乐值是多少。

具体的，有 $q$ 个询问需要你处理，每次给出三个数 $u,r,v$ 表示若游乐点 $u$ 有游客，那么这名游客将离开游乐园，否则游乐点 $u$ 将迎来一名游客。然后需要你输出如果在 $r$ 举办庆典，$v$ 设置打卡点的情况下，总欢乐值是多少。初始游乐场里没有游客。

注意，所有游客并没有真的移动，但是游客真的离开和进入了游乐园。

输入格式

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

接下来 $n-1$ 行，每行两个数 $x_i,y_i$ 表示游乐点 $x_i,y_i$ 间有一条道路。

接下来 $q$ 行，每行三个整数 $u_i,r_i,v_i$ 表示一次询问。

输出格式

输出共 $q$ 行，每行一个整数表示询问答案。

样例 1 输入

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

样例 1 输出

0
2
4
6
9

样例 1 解释

对于最后一组询问，游乐点 $1、2、3、4、5$ 还有游客，庆典在游乐点 $3$ 举办，打卡点在游乐点 $1$ 举办。下文用 $i$ 表示第 $0$ 秒位于游乐点 $i$ 的游客，用 $a_i$ 表示 $i$ 游客当前欢乐值。

第 $1$ 秒时，没有游客移动。

第 $2$ 秒时，游客 $4、5$ 走到了游乐点 $2$ ，此时游客 $2、4、5$ 两两都是第一次见面，所以 $a_i=[0,2,0,2,2]$。

第 $3$ 秒时，游客 $2、4、5$ 走到游乐点 $1$ ，此时 $a_i=[1.5,2.5,0,2.5,2.5]$。

第 $4$ 秒时，游客 $1、2、4、5$ 游乐点 $3$ ，此时 $a_i=[3,4,6,4,4]$，开始庆典。

其中游客 $1、2、4、5$ 都曾到达过打卡点，并且到达打卡点最晚时间都是第 $3$ 秒（虽然游客 $1$ 初始就在打卡点），他们将会在第 $3$ 秒在游乐点 $1$ 打卡，总欢乐值为 $1.5+2.5+2.5+2.5=9$ ，所以输出 $9$ 。

样例 2 输入

7 8
1 2
1 3
2 4
2 5
3 6
6 7
2 1 1
3 1 1
4 1 1
1 1 4
5 1 4
1 4 7
7 4 4
1 5 1

样例 2 输出

0
1
4
0
0
0
29
5

样例 3

见选手目录下 $celebration/ex\_celebration3.in$ 和 $celebration/ex\_celebration3.out$

样例 4

见选手目录下 $celebration/ex\_celebration4.in$ 和 $celebration/ex\_celebration4.out$

该样例满足特殊性质 B

样例 5

见选手目录下 $celebration/ex\_celebration5.in$ 和 $celebration/ex\_celebration5.out$

该样例满足特殊性质 C

数据范围

$1\leq n\leq 5\times 10^4,1\leq q\leq 10^5,1\leq x_i,y_i,u_i,r_i,v_i\leq n$。

子任务编号	$n,q$ 限制	特殊性质	分值
$1$	$\max(n,q)\leq 100$		7
$2$	$\max(n,q)\leq 500$		8
$3$	$\max(n,q)\leq 4000$		10
$4$	$q\leq 7\times 10^4$	A	20
$5$		B
$6$		C
$7$	无		15

特殊性质 A：$r_i=v_i=1$

特殊性质 B：$r_i=1$

特殊性质 C：$r_i=v_i$