题目描述

给定一棵 $n$ 个节点构成的树，树上每个节点均有一个盒子。节点 $i$ 的盒子至多可以装 $c_i$ 颗糖果。

虽然我们暂时并不知晓 $c_i$ 的具体数值，但首先规定每一个 $c_i$ 均为不超过 $10^{18}$ 的非负整数。初始所有盒子都是空的。

接下来进行 $q$ 次操作，每次操作有以下三种形式：

1. 1 x y w：对于路径 $(x,y)$ 上的每一个节点，将其对应的盒子里分别装入 $w$ 颗糖果。每个盒子放满时停止。
2. 2 x y w：对于路径 $(x,y)$ 上的每一个节点，将其对应的盒子里分别取出 $w$ 颗糖果。每个盒子取空时停止。
3. 3 x z：假设节点 $x$ 的盒子里恰好装有 $z$ 颗糖果，查询 $c_x$ 的所有可能的值的总和，对 $998244353$ 取模。如果不存在符合要求的 $c_x$，则输出 $-1$。

时间限制：5 秒。
空间限制：1024 MiB。

输入格式

输入的第一行包含两个整数 $n,q$，表示树的点数和操作次数。

接下来 $n-1$ 行，每行两个整数 $u,v$，表示树上的一条边 $(u,v)$。

接下来 $q$ 行，每行三到四个整数，表示一次操作。

输出格式

输出包含若干行。对于所有查询操作，输出一行一个整数，表示答案对 $998244353$ 取模的结果。若不存在合法的 $c_x$，则输出 $-1$。

样例

输入

3 8
1 2
1 3
1 1 3 2
2 1 3 1
1 2 3 2
3 3 1
3 3 2
3 3 3
3 2 0
3 2 10

输出

1
2
75433844
0
-1

数据范围

对于 $100\%$ 的数据，保证

$$1\le n,q\le 300000,\quad 1\le u,v,x,y\le n,\quad 0\le w\le 10^9,\quad 0\le z\le 10^{18}.$$

测试点编号	$n,q\le$	特殊性质
1	10	无
2	100
$3\sim 4$	1000
$5\sim 6$	$10^5$	A
$7\sim 8$		B
$9\sim 11$		C
$12\sim 13$	30000	D
14	$10^5$
$15\sim 16$	30000	无
17	$10^5$
18	$3\times 10^5$	E
19		F
20		无

特殊性质 A：保证 $n=1$。

特殊性质 B：保证所有操作一和操作二的路径 $(x,y)$ 满足 $x=y$。

特殊性质 C：保证所有操作一和操作二的路径 $(x,y)$ 满足 $x=1$。

特殊性质 D：保证树形态构成一条链，且所有树边均形如 $(i,i+1)$。

特殊性质 E：操作三大致占总操作次数的 $5\%$。

特殊性质 F：操作三大致占总操作次数的 $95\%$。