Description

给定 $n,q$。现有一个初始为 $0$ 的整数 $m$。你需要支持以下操作：

• 0 x：将 $m$ 加上 $2^x$。
• 1 x：将 $m$ 减去 $2^x$。若 $m<2^x$，则忽略此操作。
• 2：查询有多少长度为 $n$、每个数都在 $1\sim m$ 中的严格递增正整数序列，使得其前缀异或和与后缀异或和均严格递增。答案对 $998\,244\,353$ 取模。

其中，一个序列 $a_1,a_2,\cdots,a_n$ 的前缀异或和是指序列 $s_1,s_2,\cdots,s_n$，满足 $s_i=\begin{cases}a_1&i=1\\a_{i}\oplus s_{i-1}&i\ge2\end{cases}$，而其后缀异或和是指序列 $t_1,t_2,\cdots,t_n$，满足 $t_i=\begin{cases}a_n&i=1\\a_{n-i+1}\oplus t_{i-1}&i\ge2\end{cases}$，其中 $x\oplus y$ 表示 $x$ 与 $y$ 的按位异或。

Input Format

第一行两个正整数，表示 $n,q$。

接下来 $q$ 行，每行表示一个操作。

Output Format

对于每个 2 操作，输出对应的答案对 $998\,244\,353$ 取模的值。

3 4
0 0
0 1
0 2
2

2

20 15
0 1
0 2
0 21
0 5
2
0 15
1 18
0 7
0 8
0 25
2
1 22
0 12
0 13
2

313288290
39181640
134388812

Hint

【样例解释 #1】

查询时 $m=7$，满足要求的序列为 $\{1,2,4\}$ 和 $\{1,3,5\}$，可以证明不存在其他解。

注意，序列 $\{1,3,1\}$ 是不满足要求的，尽管其前、后缀异或和均为严格递增数列 $\{1,2,3\}$，该序列本身并不满足严格递增的限制。

【数据范围】

本题开启捆绑测试。

特殊性质 A：仅有最后一次操作为 2 操作。
特殊性质 B：不包含 1 操作。

对于 $100\%$ 的数据，$3\le n\le 10^7$，$1\le q\le 2\times10^5$，$0\le x\le 10^7$。