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$.
## Input
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.
## Output
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$.
[samples]
## Note
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}$.
[{"iden":"statement","content":"在Dirtpolis的魔法学校中，计算机科学课程研究了许多有趣的对象。\n\n例如，考虑魔法多重集。如果你尝试向其中添加一个已经存在的整数，那么多重集中的每个元素都会翻倍。例如，如果你尝试向多重集 ${1, 2, 3, 3}$ 中添加整数 $2$，你会得到 ${1, 1, 2, 2, 3, 3, 3, 3}$。\n\n如果你尝试添加一个不存在于多重集中的整数，它会被简单地加入其中。例如，如果你尝试向多重集 ${1, 2, 3, 3}$ 中添加整数 $4$，你会得到 ${1, 2, 3, 3, 4}$。\n\n此外，考虑一个由 $n$ 个初始为空的魔法多重集组成的数组，编号从 $1$ 到 $n$。\n\n你需要处理 $q$ 个查询，形式为：“将整数 $x$ 添加到所有索引为 $l, l + 1, dots.h, r$ 的多重集中” 或 “计算索引为 $l, l + 1, dots.h, r$ 的多重集的大小之和”。第二类查询的答案可能很大，因此请对 $998244353$ 取模输出。\n\n第一行包含两个整数 $n$ 和 $q$ ($1 lt.eq n, q lt.eq 2 dot.op 10^5$) —— 数组中魔法多重集的数量和查询的数量。\n\n接下来的 $q$ 行描述查询，每行一个。每行以一个整数 $t$ ($1 lt.eq t lt.eq 2$) 开头，表示查询类型。如果 $t$ 等于 $1$，则后跟三个整数 $l$, $r$, $x$ ($1 lt.eq l lt.eq r lt.eq n$, $1 lt.eq x lt.eq n$)，表示应将 $x$ 添加到索引从 $l$ 到 $r$（含）的所有多重集中。如果 $t$ 等于 $2$，则后跟两个整数 $l$, $r$ ($1 lt.eq l lt.eq r lt.eq n$)，表示应计算索引从 $l$ 到 $r$（含）的所有多重集的大小之和。\n\n对于每个第二类查询，输出给定区间内多重集的大小之和。\n\n答案可能很大，因此请对 $998244353$ 取模输出。\n\n在第一个示例中，前两个查询后多重集为 $[ {1, 2}, {1, 2}, {}, {} ]$，第三个查询后为 $[ {1, 1, 2, 2}, {1, 1, 2, 2}, {1}, {1} ]$。\n\n在第二个示例中，第一个多重集的演变过程如下：\n\n${} arrow.r {3} arrow.r {3, 3} arrow.r {2, 3, 3} arrow.r {1, 2, 3, 3} arrow.r {1, 1, 2, 2, 3, 3, 3, 3}$。 "},{"iden":"input","content":"第一行包含两个整数 $n$ 和 $q$ ($1 lt.eq n, q lt.eq 2 dot.op 10^5$) —— 数组中魔法多重集的数量和查询的数量。接下来的 $q$ 行描述查询，每行一个。每行以一个整数 $t$ ($1 lt.eq t lt.eq 2$) 开头，表示查询类型。如果 $t$ 等于 $1$，则后跟三个整数 $l$, $r$, $x$ ($1 lt.eq l lt.eq r lt.eq n$, $1 lt.eq x lt.eq n$)，表示应将 $x$ 添加到索引从 $l$ 到 $r$（含）的所有多重集中。如果 $t$ 等于 $2$，则后跟两个整数 $l$, $r$ ($1 lt.eq l lt.eq r lt.eq n$)，表示应计算索引从 $l$ 到 $r$（含）的所有多重集的大小之和。"},{"iden":"output","content":"对于每个第二类查询，输出给定区间内多重集的大小之和。答案可能很大，因此请对 $998244353$ 取模输出。"},{"iden":"examples","content":"输入\n4 4\n1 1 2 1\n1 1 2 2\n1 1 4 1\n2 1 4\n输出\n10\n\n输入\n3 7\n1 1 1 3\n1 1 1 3\n1 1 1 2\n1 1 1 1\n2 1 1\n1 1 1 2\n2 1 1\n输出\n4\n8"},{"iden":"note","content":"在第一个示例中，前两个查询后多重集为 $[ {1, 2}, {1, 2}, {}, {} ]$，第三个查询后为 $[ {1, 1, 2, 2}, {1, 1, 2, 2}, {1}, {1} ]$。\n\n在第二个示例中，第一个多重集的演变过程如下： ${} arrow.r {3} arrow.r {3, 3} arrow.r {2, 3, 3} arrow.r {1, 2, 3, 3} arrow.r {1, 1, 2, 2, 3, 3, 3, 3}$。 "}]}
**Definitions**
Let $ n, q \in \mathbb{Z}^+ $ denote the number of magic multisets and the number of queries, respectively.
Let $ \mathcal{M} = (M_1, M_2, \dots, M_n) $ be a tuple of $ n $ magic multisets, initially all empty: $ M_i = \emptyset $ for all $ i \in \{1, \dots, n\} $.
Let $ \mathbb{Z}_{998244353} = \mathbb{Z} / 998244353\mathbb{Z} $ be the ring of integers modulo $ 998244353 $.
**Magic Multiset Operation**
For a multiset $ M $ and an integer $ x $:
- If $ x \in M $, then $ M \leftarrow M \cup \{ y \mid y \in M \} $ (i.e., every element is duplicated).
- If $ x \notin M $, then $ M \leftarrow M \cup \{x\} $.
**Constraints**
1. $ 1 \le n, q \le 2 \cdot 10^5 $
2. For each query:
- If type $ t = 1 $: $ 1 \le l \le r \le n $, $ 1 \le x \le n $, apply the magic add operation to all $ M_i $ for $ i \in [l, r] $.
- If type $ t = 2 $: $ 1 \le l \le r \le n $, compute $ \sum_{i=l}^{r} |M_i| \mod 998244353 $.
**Objective**
Process $ q $ queries:
- For each query of type 1: update $ M_i \leftarrow \text{magic\_add}(M_i, x) $ for all $ i \in [l, r] $.
- For each query of type 2: output $ \sum_{i=l}^{r} |M_i| \mod 998244353 $.