AT_scpc2026_div1_l.Lulu, the Magician

Lulu is actually a genius magician. After a long period of research, Lulu developed a secret magic of her own using a magic circle.

The magic circle Lulu uses is a tree structure consisting of $N$ spells and $N-1$ connections. The spells are numbered in order from $1$ to $N$, and Lulu can strengthen each spell. The $i$-th connection of the magic circle means that spell $a_i$ and spell $b_i$ are directly connected.

Initially, the power of every spell is $0$. When Lulu strengthens spell $r$ by $w$, the power $W_r$ of spell $r$ increases by $w$.

Lulu can cast magic by choosing two spells $u$ and $v$ in the magic circle. When Lulu casts magic, every spell in the magic circle interacts with the set $P(u,v)$ of vertices on the unique simple path connecting $u$ and $v$. The final power of the magic Lulu casts can be calculated by the following formula. Here, $d(a,b)$ is the number of edges on the unique simple path connecting $a$ and $b$.

$\sum_{x \in P(u, v)} \sum_{r=1}^{N} W_r \times d(r, x)$

The genius magician Lulu wants to learn magic by performing the following two types of actions in order, $Q$ times in total.

• 1 v w: Increase the power of spell $v$ by $w$.

• 2 u v: Choose spells $u$ and $v$ and cast magic.

For each action of type $2$, compute the final power of the cast magic modulo $998\,244\,353$.

露露实际上是一位天才魔法师。经过长期研究，露露利用一个魔法阵，开发出了属于自己的秘密魔法。

露露所使用的魔法阵是一个由 $N$ 个咒语和 $N-1$ 条连接构成的树形结构。这些咒语按顺序编号为 $1$ 至 $N$，露露可以强化其中任意一个咒语。第 $i$ 条连接表示咒语 $a_i$ 与咒语 $b_i$ 直接相连。

初始时，每个咒语的力量值均为 $0$。当露露将咒语 $r$ 强化 $w$ 单位时，咒语 $r$ 的力量值 $W_r$ 增加 $w$。

露露可通过在魔法阵中选择两个咒语 $u$ 和 $v$ 来施放魔法。施放魔法时，魔法阵中的每个咒语都会与连接 $u$ 和 $v$ 的唯一简单路径上的顶点集合 $P(u,v)$ 发生交互。露露所施放魔法的最终威力可由以下公式计算。其中，$d(a,b)$ 表示连接 $a$ 和 $b$ 的唯一简单路径上的边数。

$$\sum_{x \in P(u, v)} \sum_{r=1}^{N} W_r \times d(r, x)$$

这位天才魔法师露露希望通过依次执行以下两种操作共 $Q$ 次来学习魔法：

• 1 v w：将咒语 $v$ 的力量值增加 $w$；

• 2 u v：选择咒语 $u$ 和 $v$ 并施放魔法。

对每一次类型为 2 的操作，请计算所施放魔法的最终威力，并对 $998\,244\,353$ 取模。

The input is given from Standard Input in the following format:

$N$ $Q$
$a_1$ $b_1$
$a_2$ $b_2$
$\vdots$
$a_{N-1}$ $b_{N-1}$
$\mathrm{action}_1$
$\mathrm{action}_2$
$\vdots$
$\mathrm{action}_Q$

输入从标准输入中按以下格式给出：

$N$ $Q$
$a_1$ $b_1$
$a_2$ $b_2$
$\vdots$
$a_{N-1}$ $b_{N-1}$
$\mathrm{action}_1$
$\mathrm{action}_2$
$\vdots$
$\mathrm{action}_Q$

For each action of type $2$, output one line containing the final power of the cast magic modulo $998\,244\,353$.

对于每个类型为 $2$ 的操作，输出一行，包含施放魔法的最终力量值对 $998\,244\,353$ 取模的结果。

表示言語

/ /

Constraints

• $1 \leq N, Q \leq 200\,000$
• $1 \leq a_i, b_i \leq N$
• $a_i \ne b_i$
• The given magic circle is a tree.
• In an action of the form 1 v w, $1 \leq v \leq N$ and $1 \leq w \leq 10^9$.
• In an action of the form 2 u v, $1 \leq u, v \leq N$.
• All given numbers are integers.

表示语言

/ /

约束条件

• $1 \leq N, Q \leq 200\,000$
• $1 \leq a_i, b_i \leq N$
• $a_i \ne b_i$
• 给定的魔法环是一棵树。
• 对于形如 1 v w 的操作，满足 $1 \leq v \leq N$ 且 $1 \leq w \leq 10^9$。
• 对于形如 2 u v 的操作，满足 $1 \leq u, v \leq N$。
• 所有给定的数均为整数。