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.

（本题与 II 唯一区别为保证询问中两棵子树不为包含与被包含关系）

题目背景

这是一个抽象的题目背景

小 $L$ 曾种过一棵树，它的名字叫黑驴树（致敬黑色环保小能手。

题目描述

这是一个抽象的题目描述

这棵树上生活着 $n$ 头可可爱爱的黑驴（从 $1$ 到 $n$ 编号，$1$ 号为根），他们之间有 $n-1$ 条边，每条边有一个嘿嘿值 $w$.

两头黑驴 $a$，$b$ 之间的啦啦点数为他们俩之间的简单路径上的嘿嘿值总和，记为 $f(a,b)$.

小 $L$ 有 $q$ 次没事找事，形如：

• $1$ $x$ $y$ $w$ 表示小 $L$ 将编号为 $x$ 与 $y$ 的黑驴之间边的嘿嘿值改为 $w$ （保证边存在）。

• $2$ $x$ $y$ 表示小 $L$ 想询问以 $x$ 为根的子树内生活的黑驴，与以 $y$ 为根的子树内生活的黑驴两两之间啦啦点数之和。

  结果对998244353取模。 保证询问中两棵子树不为包含与被包含关系。

简明地说，询问：

格式

输入

第 $1$ 行两个整数 $n$，$q$.

第 $2$ 至第 $n$ 行，每行三个整数 $u$，$v$，$w$ 表示有一条 $u$ 号黑驴连向 $v$ 号黑驴的边，嘿嘿值为 $w$.

第 $n+1$ 至第 $n+q$ 行，每行第一个数为 $opt$，表示这次操作的类型。如果 $opt=1$，后面紧跟三个整数 $x$，$y$，$w$ 意义如题面所述；如果 $opt=2$，后面紧跟两个整数 $x$，$y$ 意义如题面所述。

输出

对于每个操作 $2$，在一行内输出一个数表示答案。 结果对998244353取模。

样例

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

10
34

解释

• 第二次询问：第二次操作将 $1$ 号黑驴至 $2$ 号黑驴之间的嘿嘿值从 $3$ 变为 $5$.以 $6$ 为根的子树内有两头黑驴 $6$、$7$，以 $3$ 为根的子树内有一头黑驴 $3$.$f(3,6)=2+5+9=16$，$f(3,7)=2+2+5+9=18$.故 $Sum(3,6)=16+18=34$.

限制

对于所有数据，保证任何时刻边上嘿嘿值为不超过 $1000000$ 的非负整数。