Berland 是一个拥有 $n$ 个城市的独立国家，其中一些城市通过 $n-1$ 条道路相连，使得从任何一个城市出发都能到达其他任何城市。已知驾驶汽车通过每条道路所需的时间。

Berland 的管理部门计算了所有城市对之间行驶的最短时间，并对道路的陈旧程度感到震惊。现在是进行创新的时候了！具体来说，管理部门进行了 $m$ 次操作，每次选取两个城市 $u, v$，并将 $u$ 到 $v$ 最短路径上的所有道路替换为创新道路。如果某条道路之前所需的行驶时间为 $w$，那么在替换后，该道路的行驶时间将变为 $\lfloor \sqrt{w} \rfloor$。一条道路在变得创新后，还可以变得更加创新。换句话说，一条道路可以被更新多次。

不幸的是，这项翻新工作将由你来完成。请计算在创新之前以及每次路径替换之后，所有城市对之间的最短路径之和。由于这些和可能很大，请输出其对 $10^9 + 7$ 取模的结果。

输入格式

第一行包含两个整数 $n, m$，分别表示城市数量和查询次数。

接下来的 $n-1$ 行，每行包含三个整数 $u, v, w$，表示连接城市 $u$ 和 $v$ 的道路，以及通过该道路所需的行驶时间。

接下来的 $m$ 行，每行包含两个整数 $u, v$，表示对 $u$ 和 $v$ 之间的路径进行创新。

$1 \le n, m \le 2 \cdot 10^5$ $1 \le u, v \le n, 1 \le w \le 10^6$

输出格式

输出 $m+1$ 行，每行包含一个整数，依次表示初始状态下的最短路径之和以及每次查询后的最短路径之和，结果对 $10^9 + 7$ 取模。

样例

输入 1

5 3
1 2 4
2 3 4
1 4 9
1 5 16
1 5
1 3
1 4

输出 1

140
92
72
48