#216073. [CSPro 32] 宝藏

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

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

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

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

1. 给定 的矩阵 ，将 插入队列的头部；
2. 给定 的矩阵 ，将 插入队列的尾部；
3. 若队列非空，删除队列中最晚被插入的矩阵。

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

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

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

从标准输入读入数据。

输入的第一行包含两个正整数 。

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

• 输入的第一个正整数 描述这条指令的形式，保证 为 中的一种。
• 若 ，接下来给出四个非负整数 ，表示操作为将 的矩阵 插入队列的头部；
• 若 ，接下来给出四个非负整数 ，表示操作为将 的矩阵 插入队列的尾部；
• 若 ，表示操作为若队列非空，删除队列中最晚被插入的矩阵；

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

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

输出到标准输出。

对于所有类型为 的事件，输出一行四个非负整数 ，表示该时刻的密码 。

样例输入 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

样例 1 解释

第一次事件发生时，

• 第 条指令为在序列尾部插入矩阵 ；
• 第 条指令为在序列尾部插入矩阵 。

依次执行第 条指令，得到的队列为 ，则密码为

第四次事件发生时，

• 第 条指令为在序列头部插入矩阵 ；
• 第 条指令为在序列头部插入矩阵 ；
• 第 条指令为若队列非空，删除队列中最晚被插入的矩阵。

依次执行第 条指令，得到的队列为 ，则密码为 。

样例 2

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

该样例满足测试数据 的限制。

样例 3

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

该样例满足测试数据 的限制。

样例 4

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

该样例满足测试数据 的限制。

样例 5

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

该样例满足测试数据 的限制。

样例 6

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

该样例满足测试数据 的限制。

样例 7

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

该样例满足测试数据 的限制。

子任务

对于所有测试数据，满足 ，，。