Binary Tree Operations

You are given a full binary tree with exactly \(2n-1\) nodes, constructed in the following way: Consider a segment tree built on the interval \([1,n]\). The root (node 1) covers the interval \([1,n]\). Then, if a node covers the interval \([l,r]\) with \(l<r\), it splits the interval into two parts: the left child covers \([l,\,\lfloor\frac{l+r}{2}\rfloor]\) and the right child covers \([\lfloor\frac{l+r}{2}\rfloor+1, r]\). The nodes are numbered in the order of a DFS (preorder) so that a node's number is less than any node in its subtree. In particular, the leaf nodes (when \(l=r\)) are numbered from 1 to \(n\) in increasing order and are also called the \(1^\text{st}\) leaf, \(2^\text{nd}\) leaf, …, \(n^\text{th}\) leaf.

For each node \(j\) (\(1\le j\le 2n-1\)) we define an initial weight \(v_j=0\). A node \(j\) is said to govern a leaf \(i\) if leaf \(i\) lies in the subtree of node \(j\) (note that a leaf governs itself since it lies in its own subtree). Let \(g(j,i)=1\) if node \(j\) governs leaf \(i\) and \(0\) otherwise. For each leaf \(i\) define its function value as

[ f(i)=\sum_{j:,g(j,i)=1}v_j. ]

You are to process \(q\) operations on the tree. Each operation is one of the following three types:

• 1 s t v: For every node with DFS number \(i\) where \(s\le i\le t\), add \(v\) to \(v_i\).
• 2 s t v: Let \(S=\bigcup_{i=s}^{t}S_i\), where \(S_i\) is the set of leaf nodes governed by node \(i\). For every leaf in \(S\), add \(v\) to its own weight. (Note that even if a leaf appears in several \(S_i\), it is only updated once.)
• 3 l r: Compute \(\sum_{i=l}^{r}f(i)\) modulo \(998\,244\,353\).

Input Format: The first line contains two integers \(n\) and \(q\). Each of the next \(q\) lines contains an operation. For operations of type 1 and 2 the line is of the form 1 s t v or 2 s t v, and for operations of type 3 the line is of the form 3 l r.

Note: The tree structure is fixed and is identical to that of a segment tree built on \([1,n]\); hence every node \(j\) corresponds to a contiguous interval \([L_j,R_j]\) of leaves. An update on a node (operation 1) contributes its added weight \(v\) to every leaf in \([L_j,R_j]\). Operation 2 updates a set of leaves (computed as the union over several intervals) by \(v\) each. Operation 3 queries the total sum of \(f(i)\) for leaves \(i\) in the given range.

inputFormat

The input begins with a line containing two integers \(n\) and \(q\) \((1\le n \le ... , 1\le q \le ... )\). Each of the following \(q\) lines describes an operation in one of the following formats:

• 1 s t v — add \(v\) to the weight of every node with DFS number in \([s, t]\).
• 2 s t v — for all leaves governed by at least one node with DFS number in \([s, t]\), add \(v\) to that leaf's weight (each leaf is updated at most once in this operation).
• 3 l r — output the value \(\sum_{i=l}^{r} f(i) \bmod 998244353\), where \(f(i)=\sum_{j:\,g(j,i)=1}v_j\).

outputFormat

For each operation of type 3, output the corresponding answer on a separate line.

sample

3 5
1 1 3 2
3 1 3
2 2 4 1
1 3 5 3
3 2 3

12
13