Background

January 4, 2079 I don't know what to do. The marks are everywhere. Red marks are all over the place, in every street without exception. The number of missing people is increasing every day. Things are getting stranger and more surreal. I don't know how much time I have left. Kingdom

There are $Q$ events occurring in sequence. The events are of two types:

• $1$ $l$ $r$: A new interval $[l, r]$ appears, where $1 \le l < r \le n$.
• $2$ $x$: A collapse occurs at position $x$, where $1 \le x \le n$. For every existing interval $[l, r]$ such that $l < x < r$, the interval becomes $[l, x]$ with probability $\frac{1}{2}$ and $[x, r]$ with probability $\frac{1}{2}$.

Calculate the sum of the expected lengths of all intervals at the end, modulo $998244353$. (The length of an interval $[l, r]$ is $r - l$.)

Input

The first line contains two integers $n$ and $Q$.

Each of the following $Q$ lines describes an event, either $1$ $l$ $r$ or $2$ $x$.

Output

Output a single integer representing the answer.

Examples

Input 1

3 3
1 1 3
1 2 3
2 2

Output 1

2

Note 1

The interval $[1, 3]$ collapses, becoming $[1, 2]$ with probability $\frac{1}{2}$ and $[2, 3]$ with probability $\frac{1}{2}$. The interval $[2, 3]$ is not affected by the collapse.

Therefore, the sum of the expected lengths is $\frac{1}{2} \times 1 + \frac{1}{2} \times 1 + 1 \times 1 = 2$.

Constraints

For all data: $1 \le n, Q \le 50000$, $1 \le l < r \le n$, $1 \le x \le n$.

• Subtask 1 (10 pts): $1 \le n, Q \le 500$.
• Subtask 2 (20 pts): $1 \le n, Q \le 5000$, depends on Subtask 1.
• Subtask 3 (40 pts): All type 1 events occur before all type 2 events.
• Subtask 4 (30 pts): No special restrictions, depends on Subtasks 1, 2, and 3.