宝藏

题目描述

西西艾弗岛上埋藏着一份宝藏，小 $C$ 根据藏宝图找到了宝藏的位置。

藏有宝藏的箱子被上了锁，旁边写着一些提示：

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

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

1. 给定 $2 \times 2$ 的矩阵 $A$，将 $A$ 插入队列的头部；
2. 给定 $2 \times 2$ 的矩阵 $B$，将 $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$ 的矩阵 $A$ 插入队列的头部；
• 若 $v=2$，接下来给出四个非负整数 $B_{1,1},B_{1,2},B_{2,1},B_{2,2}$，表示操作为将 $2 \times 2$ 的矩阵 $B$ 插入队列的尾部；
• 若 $v=3$，表示操作为若队列非空，删除队列中最晚被插入的矩阵；

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

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

数据范围

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

输出格式

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

样例 #1

样例输入 #1

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

样例输出 #1

30 57 12 34
2 3 9 3

提示

第一次事件发生时，

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

依次执行第 $2 \sim 3$ 条指令，得到的队列为 $\bigg\{ \begin{bmatrix} 6 & 9 \\ 4 & 2 \end{bmatrix}, \begin{bmatrix} 2 & 8 \\ 2 & 1 \end{bmatrix} \bigg\}$，则密码为 $\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$ 条指令，得到的队列为 $\bigg\{ \begin{bmatrix} 2 & 3 \\ 9 & 3 \end{bmatrix} \bigg\}$，则密码为 $\begin{bmatrix} 2 & 3 \\ 9 & 3 \end{bmatrix}$。