一座星港由 $n$ 个停靠点和 $n-1$ 条双向通道组成，任意两个停靠点之间都能互相到达，且每条通道长度均为 $1$。也就是说，星港结构是一棵树。

某些停靠点上停有探测员。现在星港将在停靠点 $r$ 启动集结程序，并在停靠点 $v$ 设置一次记录终端。

接下来的 $n-1$ 秒内，所有探测员会按照统一规则向停靠点 $r$ 集结。具体地，第 $i$ 秒时，所有当前距离停靠点 $r$ 恰好为 $n-i$ 的探测员，会沿着通往 $r$ 的最短路径向前移动一步。第 $0$ 秒时，所有探测员仍在自己的初始停靠点。

若两个不同的探测员 $a,b$ 在第 $i$ 秒第一次相遇，即它们在第 $i$ 秒位于同一个停靠点，而在第 $i-1$ 秒不位于同一个停靠点，设它们此时所在的停靠点编号为 $x$，则探测员 $a$ 与探测员 $b$ 都会各自获得 $\frac{x}{2}$ 点记录值。

对于某个探测员 $a$，设 $c$ 是 $0\sim n-1$ 中最大的一个时刻，使得第 $c$ 秒时 $a$ 位于记录终端 $v$。那么在第 $c$ 秒，$a$ 会在终端 $v$ 进行记录，并将其当时拥有的记录值计入总记录值。若不存在这样的时刻 $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$ 表示该探测员当前记录值。

第 $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$ 都曾到达记录终端 $1$，且最后一次到达记录终端的时刻均为第 $3$ 秒，因此总记录值为 $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$。

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

特殊性质 B：$r_i=1$。

特殊性质 C：$r_i=v_i$。