题目背景

2079 年 1 月 4 日

我不知道该怎么办。

那些标记无处不在。

红色记号到处都是，各个街道无一例外。

失踪的人口每天都在增加。

事情变得愈发奇怪，越来越不真实。

我不知道自己还有多少时间。

王 国

题目描述

有$Q$个事件依次发生。事件分为两种：

• $1$ $l$ $r$ ，表示一个新的区间$[l,r]$从天而降，满足$1 \le l < r \le n$。
• $2$ $x$，表示位置$x$发生崩坏，满足$1 \le x \le n$，所有满足$l<x$且$x<r$的区间$[l,r]$都会以$\frac{1}{2}$的概率变成$[l,x]$，另$\frac{1}{2}$的概率变成$[x,r]$。

请求出最后所有区间的期望长度之和，对$998244353$取模。(区间$[l,r]$的长度为 $r-l$ )

输入格式

第一行两个整数 $n,Q$。

接下来$Q$行每行表示一个事件，即$1$ $l$ $r$或$2$ $x$。

输出格式

一行一个整数表示答案。

样例

输入 #1

3 3
1 1 3
1 2 3
2 2

输出 #1

2

样例解释

区间$[1,3]$发生崩坏，$\frac{1}{2}$概率变为$[1,2]$，$\frac{1}{2}$概率变为$[2,3]$，区间$[2,3]$未发生崩坏。

所以最后的期望长度之和为$\frac{1}{2}\*1+\frac{1}{2}\*1+1\*1=2$。

数据范围

对于所有数据：$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$，依赖$Subtask$ $1$。

$Subtask$ $3$ $(40$ $pts):$ 保证所有事件$1$在所有事件$2$之前。

$Subtask$ $4$ $(30$ $pts):$ 无特殊限制，依赖$Subtask$ $1,2,3$。