CF981G.Magic multisets

In the School of Magic in Dirtpolis a lot of interesting objects are studied on Computer Science lessons.

Consider, for example, the magic multiset. If you try to add an integer to it that is already presented in the multiset, each element in the multiset duplicates. For example, if you try to add the integer $2$ to the multiset ${1, 2, 3, 3}$, you will get ${1, 1, 2, 2, 3, 3, 3, 3}$.

If you try to add an integer that is not presented in the multiset, it is simply added to it. For example, if you try to add the integer $4$ to the multiset ${1, 2, 3, 3}$, you will get ${1, 2, 3, 3, 4}$.

Also consider an array of $n$ initially empty magic multisets, enumerated from $1$ to $n$.

You are to answer $q$ queries of the form "add an integer $x$ to all multisets with indices $l, l + 1, \ldots, r$" and "compute the sum of sizes of multisets with indices $l, l + 1, \ldots, r$". The answers for the second type queries can be large, so print the answers modulo $998244353$.

在迪尔特波利斯魔法学院的计算机科学课上，学生们研究了许多有趣的对象。

例如，考虑一种魔法多重集（multiset）。如果你尝试向其中添加一个已在该多重集中存在的整数，则多重集中的每个元素都会复制一份。例如，若向多重集 $\{1, 2, 3, 3\}$ 中添加整数 $2$，你将得到 $\{1, 1, 2, 2, 3, 3, 3, 3\}$。

如果你尝试添加一个不在该多重集中出现的整数，则该整数将被直接加入其中。例如，若向多重集 $\{1, 2, 3, 3\}$ 中添加整数 $4$，你将得到 $\{1, 2, 3, 3, 4\}$。

再考虑一个由 $n$ 个初始为空的魔法多重集组成的数组，这些多重集从 $1$ 到 $n$ 编号。

你需要回答 $q$ 个查询，查询分为两类：

• “将整数 $x$ 添加到所有下标在区间 $[l, l + 1, \ldots, r]$ 内的多重集中”；
• “计算所有下标在区间 $[l, l + 1, \ldots, r]$ 内的多重集的大小之和”。

第二类查询的答案可能非常大，因此请输出答案对 $998244353$ 取模的结果。

The first line contains two integers $n$ and $q$ ($1 \leq n, q \leq 2 \cdot 10^{5}$) — the number of magic multisets in the array and the number of queries, respectively.

The next $q$ lines describe queries, one per line. Each line starts with an integer $t$ ($1 \leq t \leq 2$) — the type of the query. If $t$ equals $1$, it is followed by three integers $l$, $r$, $x$ ($1 \leq l \leq r \leq n$, $1 \leq x \leq n$) meaning that you should add $x$ to all multisets with indices from $l$ to $r$ inclusive. If $t$ equals $2$, it is followed by two integers $l$, $r$ ($1 \leq l \leq r \leq n$) meaning that you should compute the sum of sizes of all multisets with indices from $l$ to $r$ inclusive.

第一行包含两个整数 $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$（含端点）的所有多重集的大小之和。

For each query of the second type print the sum of sizes of multisets on the given segment.

The answers can be large, so print them modulo $998244353$.

对于每个第二类查询，输出给定区间上所有多重集的大小之和。

答案可能很大，因此请对 $998244353$ 取模后输出。

In the first example after the first two queries the multisets are equal to $[{1, 2},{1, 2},{},{}]$, after the third query they are equal to $[{1, 1, 2, 2},{1, 1, 2, 2},{1},{1}]$.

In the second example the first multiset evolves as follows:

${} \to {3} \to {3, 3} \to {2, 3, 3} \to {1, 2, 3, 3} \to {1, 1, 2, 2, 3, 3, 3, 3}$.

在第一个例子中，前两次查询后，多重集合分别为 $[{1, 2},{1, 2},{},{}]$；第三次查询后，它们变为 $[{1, 1, 2, 2},{1, 1, 2, 2},{1},{1}]$。

在第二个例子中，第一个多重集合的变化过程如下：

${} \to {3} \to {3, 3} \to {2, 3, 3} \to {1, 2, 3, 3} \to {1, 1, 2, 2, 3, 3, 3, 3}$。