题目来自第 32 次 CSP 认证 T4，评测使用自造高质量复刻数据。我们承认原始题面与大样例版权均归中国计算机学会（CCF）所有，因此题面与评测服务均免费对外开放。如果您认为我们侵犯了您的权益，可联系我们。

时间限制： 1.5 秒

空间限制： 512 MB

题目描述

西西艾弗岛上埋藏着一份宝藏，小 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。

样例 2 解释

该样例满足子任务 1 的限制。

样例 3

见题目文件区的 3.in 与 3.ans。

样例 3 解释

该样例满足子任务 2 的限制。

样例 4

见题目文件区的 4.in 与 4.ans。

样例 4 解释

该样例满足子任务 4 的限制。

样例 5

见题目文件区的 5.in 与 5.ans。

样例 5 解释

该样例满足子任务 4 的限制。

样例 6

见题目文件区的 6.in 与 6.ans。

样例 6 解释

该样例满足子任务 5 的限制。

样例 7

见题目文件区的 7.in 与 7.ans。

样例 7 解释

该样例满足子任务 6 的限制。

子任务

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

本题采用捆绑测试，你只有通过一个子任务中的所有测试点才能得到该子任务的分数。

子任务编号	分值	$n,m\le$	特殊性质
1	15	$10^2$	无
2	20	$10^3$
3	10	$5\times 10^4$	所有指令的形式均为 $1$
4			所有指令的形式均为 $1$ 或 $2$
5	20		所有事件的类型均为 $2$
6	10		无
7	15	$10^5$