题目描述

一棵无根树有 $n$ 个节点，编号 $1\sim n$ 。

树上每个节点有个袋子，袋子里可以放一定数量的糖果。节点 $i$ 的袋子至多可以装 $s_i$ 颗糖果，虽然不知道 $s_i$ 的确切数值，但规定每个 $s_i$ 都是不超过 $10^{18}$ 的非负整数。

初始所有袋子都是空的。

接下来有 $q$ 次操作，操作有以下三种：

• 1 a b x ：对于节点 $a$ 到节点 $b$ 的简单路径上每一个袋子，分别放入 $x$ 颗糖果，每个袋子至多放满为止；
• 2 a b x ：对于节点 $a$ 到节点 $b$ 的简单路径上每一个袋子，分别取走 $x$ 颗糖果，每个袋子至多取空为止；
• 3 a y ：假如节点 $a$ 的袋子现在装有恰好 $y$ 颗糖果，查询 $s_a$ 所有可能的值的总和 $\bmod 998\ 244\ 353$ 。如果不存在符合要求的 $s_a$ ，输出 $-1$ 。

输入格式

第一行两个整数 $n,q$ 。

接下来 $n-1$ 行，每行两个整数 $u_i,v_i$ ，表示树上一条边。

接下来 $q$ 行，每行 $3$ 个整数或者 $4$ 个整数，表示一次操作。

输出格式

对于每次第 $3$ 种操作，输出 $1$ 个整数答案。

样例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

样例解释

对于前三次询问：

• 节点 $3$ 的袋子在查询前被执行了三次操作，依次是“放入 $2$ 颗”、“取走 $1$ 颗”、“放入 $2$ 颗”。
  • 如果容量 $s_3=0$ ，则此时装有 $0$ 颗糖果；
  • 如果容量 $s_3=1$ ，则此时装有 $1$ 颗糖果；
  • 如果容量 $s_3=2$ ，则此时装有 $2$ 颗糖果；
  • 如果容量 $3\leq s_3\leq 10^{18}$ ，则此时装有 $3$ 颗糖果。
• 第 $1$ 次询问要求此时装有 $1$ 颗糖果，则 $s_3$ 只可能是 $1$ ；
• 第 $2$ 次询问要求此时装有 $2$ 颗糖果，则 $s_3$ 只可能是 $2$ ；
• 第 $3$ 次询问要求此时装有 $3$ 颗糖果，则 $s_3$ 可能是区间 $[3, 10^{18}]$ 范围内的任意整数，算出总和再取模之后得到答案 $75\ 433\ 844$ 。

对于第四次和第五次询问：

• 节点 $2$ 的袋子在查询前被执行了一次操作，是“放入 $2$ 颗”。
• 如果要求当前装有 $0$ 颗糖果，则 $s_2$ 只可能是 $0$ ；
• 无论如果，都不可能使当前装有 $10$ 颗糖果。

样例2~6

见附加的样例文件。

• 样例 $2$ 符合测试点 $3,4$ 的限制；
• 样例 $3$ 符合测试点 $5,6$ 的限制；
• 样例 $4$ 符合测试点 $12,13$ 的限制；
• 样例 $5$ 符合测试点 $17$ 的限制；
• 样例 $6$ 符合测试点 $20$ 的限制（即没有特殊限制）。
• 这些样例数据的生成器与最终测试数据的生成器相同，随机种子不同。

数据范围

所有数据： $1\leq n,q\leq 300\ 000$ ， $1\leq u_i,v_i,a,b\leq n$ ， $0\leq x\leq 10^9$ ， $0\leq y\leq 10^{18}$