在 Dirtpolis 的魔法学校,计算机科学课上研究了很多有趣的物体。
例如,考虑神奇的多重集。如果您尝试向其中添加多重集中已存在的整数,则多重集中的每个元素都会重复。例如,如果您尝试将整数 $$$2$$$ 添加到多重集 $$$\{1, 2, 3, 3\}$$$,您将得到 $$$\{1, 1, 2, 2, 3, 3, 3, 3\}$$$。
如果您尝试添加多重集中未出现的整数,则只需将其添加到其中即可。例如,如果您尝试将整数 $$$4$$$ 添加到多重集 $$$\{1, 2, 3, 3\}$$$,您将得到 $$$\{1, 2, 3, 3, 4\}$$$。
还要考虑 $$$n$$$ 最初为空的魔法多重集的数组,从 $$$1$$$ 到 $$$n$$$ 枚举。
你要回答 $$$q$$$ 形式的查询“将整数 $$$x$$$ 添加到所有索引为 $$$l, l + 1, \ldots, r$$$ 的多重集”和“计算索引为 $$$l, l + 1, \ldots, r$$$ 的多重集的大小总和”。第二种类型查询的答案可能很大,因此打印答案对 $$$998244353$$$ 取模。
输入
第一行包含两个整数 $$$n$$$ 和 $$$q$$$ ($$$1 \leq n, q \leq 2 \cdot 10^{5}$$$) - 分别是数组中魔法多重集的数量和查询的数量。
接下来的 $$$q$$$ 行描述查询,每行一个。每行都以整数 $$$t$$$ ($$$1 \leq t \leq 2$$$) 开头——查询的类型。如果 $$$t$$$ 等于 $$$1$$$,则后面跟着三个整数 $$$l$$$、$$$r$$$、$$$x$$$ ($$$1 \leq l \leq r \leq n$$$、$$$1 \leq x \leq n$$$),这意味着您应该将 $$$x$$$ 添加到索引从 $$$l$$$ 到$$$r$$$ 包括在内。如果 $$$t$$$ 等于 $$$2$$$,则后面跟着两个整数 $$$l$$$、$$$r$$$ ($$$1 \leq l \leq r \leq n$$$),这意味着您应该计算索引从 $$$l$$$ 到 $$$r$$$ 的所有多重集的大小总和。
输出
对于第二种类型的每个查询,打印给定段上多重集的大小总和。
答案可能很大,因此请以 $$$998244353$$$ 为模打印它们。
示例
输入 #1
4 4 1 1 2 1 1 1 2 2 1 1 4 1 2 1 4
输出 #1
10
输入 #2
3 7 1 1 1 3 1 1 1 3 1 1 1 2 1 1 1 1 2 1 1 1 1 1 2 2 1 1
输出 #2
4 8
注意
在前两个查询之后的第一个示例中,多重集等于 $$$[\{1, 2\},\{1, 2\},\{\},\{\}]$$$,在第三个查询之后,它们等于 $$$[\{1, 1, 2, 2\},\{1, 1, 2, 2\}、\{1\}、\{1\}]$$$。
在第二个示例中,第一个多重集演变如下:
$$$\{\} \到 \{3\} \到 \{3, 3\} \到 \{2, 3, 3\} \到 \{1, 2, 3, 3\} \到 \{1, 1, 2, 2, 3, 3, 3, 3\}$$$。