题目背景

洛谷的测试数据仅供民间交流使用，非官方测试数据。官方评测链接：https://www.cspro.org/。

题目描述

西西艾弗岛上埋藏着一份宝藏，小 C 根据藏宝图找到了宝藏的位置。藏有宝藏的箱子被上了锁，旁边写着一些提示：

• 给定 $n$ 条指令，编号为 $1 \sim n$，其中每条指令都是对一个双端队列的操作，队列中的元素均为 $2 \times 2$ 的矩阵；
• 在某些时刻，某一条指令可能会改变；
• 在某些时刻，密码可以由以下方式计算：对于给定的指令区间 $[l, r]$，对初始为空的队列依次执行第 $l \sim r$ 条指令，将得到的队列里的所有矩阵从头到尾相乘，并将乘积矩阵中的所有元素对 $998244353$ 取模，得到的矩阵即为密码；特别地，若队列为空，则密码为单位矩阵；如果能分别计算出这些时刻的密码，将能够打开箱子的锁，从而获得宝藏。

经过小 C 的观察，每条指令的形式均为以下三种之一：

1. 给定 $2 \times 2$ 的矩阵 $\mathbf{A}$，将 $\mathbf{A}$ 插入队列的头部；
2. 给定 $2 \times 2$ 的矩阵 $\mathbf{B}$，将 $\mathbf{B}$ 插入队列的尾部；
3. 若队列非空，删除队列中最晚被插入的矩阵。

小 C 将所有的时刻发生的事件均记录了下来。具体地，共有 $m$ 个时刻，每个时刻可能会发生两种事件：

1. 第 $i$ 条指令改变，改变后的指令仍为以上三种形式之一；
2. 给定指令区间 $[l, r]$，求依次执行第 $l \sim r$ 条指令得到的密码。

由于小 C 并不会这个问题，他向你发起了求助。你需要帮助小 C 求出所有类型为 2 的事件所对应的密码。

输入格式

从标准输入读入数据。

输入的第一行包含两个正整数 $n, m$。

接下来 $n$ 行，按顺序给出初始时刻的每条指令：

• 输入的第一个正整数 $v$ 描述这条指令的形式，保证 $v$ 为 $1, 2, 3$ 中的一种。
• 若 $v = 1$，接下来给出四个非负整数 $A_{1,1}, A_{1,2}, A_{2,1}, A_{2,2}$，表示操作为将 $2 \times 2$ 的矩阵 $\mathbf{A}$ 插入队列的头部；
• 若 $v = 2$，接下来给出四个非负整数 $B_{1,1}, B_{1,2}, B_{2,1}, B_{2,2}$，表示操作为将 $2 \times 2$ 的矩阵 $\mathbf{B}$ 插入队列的尾部；
• 若 $v = 3$，表示操作为若队列非空，删除队列中最晚被插入的矩阵；

接下来 $m$ 行，按顺序给出每个时刻发生的事件：

• 输入的第一个正整数 $v$ 描述这个事件的类型，保证 $v$ 为 $1, 2$ 中的一种。
• 若 $v = 1$，接下来给出一个正整数 $i$ 与一条指令，表示将第 $i$ 条指令更新为当前输入的指令，指令的输入格式与初始时刻指令的输入格式相同。
• 若 $v = 2$，接下来给出两个正整数 $l, r$，你需要求出依次执行第 $l \sim r$ 条指令得到的密码。

输出格式

输出到标准输出。

对于所有类型为 $2$ 的事件，输出一行四个非负整数 $C_{1,1}, C_{1,2}, C_{2,1}, C_{2,2}$，表示该时刻的密码 $\mathbf{C}$。

3 4
1 2 3 9 3
2 6 9 4 2
2 2 8 2 1
2 2 3
1 2 1 3 1 0 1
1 3 3
2 1 3

30 57 12 34
2 3 9 3

提示

样例 1 解释

第一次事件发生时，

• 第 $2$ 条指令为在序列尾部插入矩阵 $\begin{bmatrix} 6 & 9 \\ 4 & 2 \end{bmatrix}$；
• 第 $3$ 条指令为在序列尾部插入矩阵 $\begin{bmatrix} 2 & 8 \\ 2 & 1 \end{bmatrix}$。

依次执行第 $2 \sim 3$ 条指令，得到的队列为 $\begin{bmatrix} 6 & 9 \\ 4 & 2 \end{bmatrix}, \begin{bmatrix} 2 & 8 \\ 2 & 1 \end{bmatrix}$，则密码为

$$\begin{bmatrix} 6 & 9 \\ 4 & 2 \end{bmatrix} \times \begin{bmatrix} 2 & 8 \\ 2 & 1 \end{bmatrix} = \begin{bmatrix} 30 & 57 \\ 12 & 34 \end{bmatrix}$$

第四次事件发生时，

• 第 $1$ 条指令为在序列头部插入矩阵 $\begin{bmatrix} 2 & 3 \\ 9 & 3 \end{bmatrix}$；
• 第 $2$ 条指令为在序列头部插入矩阵 $\begin{bmatrix} 3 & 1 \\ 0 & 1 \end{bmatrix}$；
• 第 $3$ 条指令为若队列非空，删除队列中最晚被插入的矩阵。

依次执行第 $1 \sim 3$ 条指令，得到的队列为 $\begin{bmatrix} 2 & 3 \\ 9 & 3 \end{bmatrix}$，则密码为 $\begin{bmatrix} 2 & 3 \\ 9 & 3 \end{bmatrix}$。

样例 2

见题目目录下的 2.in 与 2.ans。

该样例满足测试数据 $1 \sim 3$ 的限制。

样例 3

见题目目录下的 3.in 与 3.ans。

该样例满足测试数据 $4 \sim 7$ 的限制。

样例 4

见题目目录下的 4.in 与 4.ans。

该样例满足测试数据 $8, 9$ 的限制。

样例 5

见题目目录下的 5.in 与 5.ans。

该样例满足测试数据 $10, 11$ 的限制。

样例 6

见题目目录下的 6.in 与 6.ans。

该样例满足测试数据 $12 \sim 15$ 的限制。

样例 7

见题目目录下的 7.in 与 7.ans。

该样例满足测试数据 $16, 17$ 的限制。

子任务

对于所有测试数据，满足 $1 \le n, m \le 10^5$，$0 \le A_{i,j}, B_{i,j} < 998244353$，$1 \le l \le r \le n$。

测试点编号	$n, m \le$	特殊性质
$1 \sim 3$	$10^2$	无
$4 \sim 7$	$10^3$	^
$8, 9$	$5 \times 10^4$	所有指令的形式均为 $1$
$10, 11$	^	所有指令的形式均为 $1$ 或 $2$
$12 \sim 15$		所有事件的类型均为 $2$
$16, 17$		无
$18 \sim 20$	$10^5$	^