Zoom

Sequence $A$ of even length $N$ is given. Initially, every element of $A$ is $0$. Process the following queries.

• 1 l r b: Add $b$ to each of $A_l, A_{l+1}, \cdots, A_r$.
• 2 l: For every integer $i$ with $1 \leq i \leq N$, replace $A_i$ with $A_{l+\lfloor \frac{i-1}{2} \rfloor}$. All replacements happen simultaneously.
• 3: Re-run all type 1 and type 2 queries processed so far, in the same order. Queries that were executed by earlier type 3 queries are included.
• 4 l r: Print $\sum_{i=l}^r A_i$ modulo $998\,244\,353$.

The first line contains the length $N$ of the sequence and the number of queries $Q$, separated by a space.

Each of the next $Q$ lines contains one query.

For each type 4 query, print the answer on its own line.

• $2 \leq N \leq 100\,000$, and $N$ is even.
• $1 \leq Q \leq 100\,000$.
• For every type 1 query, $1 \leq l \leq r \leq N$ and $1 \leq b \leq 998\,244\,352$.
• For every type 2 query, $1 \leq l \leq \frac{N}{2}+1$.
• For every type 4 query, $1 \leq l \leq r \leq N$.
• At least one type 4 query appears in the input.
• All given numbers are integers.