You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

小 Z 似乎来到了一片空间错乱的原野......

题目描述

这里曾经有个有趣的题意描述

给出一棵以 $1$ 为根的有根树，边有边权，定义函数 $dist(u,v)$ 如下：

• 若 $u=v$，则 $dist(u,v)=0$。

• 若 $u,v$ 之间的简单路径为一条边权是 $w$ 的边，则 $dist(u,v)=w。$

• 否则，记 $S$ 为 $u,v$ 之间简单路径上所有节点构成的集合，则：

  $$dist(u,v)=\sum_{x,y\in S,x<y,\{x,y\}\not=\{u,v\}}dist(x,y) $$

现在这棵树动了起来，同时有 $q$ 次操作，操作分两种：

• 1 u w 表示将节点 $u$ 与其父节点的边的边权更改为 $w$，保证 $u$ 不为 $1$。
• 2 u v 询问 $dist(u,v)$ 的值，由于答案很大，你只需输出答案对 $2^{32}$ 取模后的结果。

现在，请你帮助小 Z，回答所有询问。

输入格式

第一行包含两个正整数 $n,q$，表示树的节点个数以及操作个数。

接下来 $n-1$ 行，每行包含三个正整数 $u,v,w$，表示树中的一条边。

接下来 $q$ 行，每行包含若干个正整数，表示一次操作。

输出格式

对每次询问，输出一行一个整数表示答案对 $2^{32}$ 取模的结果。

样例 #1

样例输入 #1

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

样例输出 #1

7
27
15
132

提示

样例输入/输出 2

详见下发文件下的 ex_cross2.in/out。

这个数据满足第 $1\sim 5$ 个测试点的限制。

样例输入/输出 3

详见下发文件下的 ex_cross3.in/out。

这个数据满足第 $6\sim 8$ 个测试点的限制。

ex_cross1.in
ex_cross1.out
ex_cross2.in
ex_cross2.out
ex_cross3.in
ex_cross3.out

数据规模与约定

对所有数据，保证 $1\le n,q\le 3\times 10^5,1\le w\le 10^9$，保证所有 1 操作中的 $u$ 不为 $1$。