P16067 [CSPro 32] 宝藏

洛谷的测试数据仅供民间交流使用，非官方测试数据。官方评测链接：。

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

### 样例 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$ | ^ |