双端队列操作复合（Deque Operate All Composite）

问题描述

初始时有一个空的线性函数序列 $f = ()$。
处理 $Q$ 个查询：

• 0 a b：在序列开头添加线性函数 $f(x) = a x + b$。
• 1 a b：在序列末尾添加线性函数 $f(x) = a x + b$。
• 2：移除序列开头的函数。
• 3：移除序列末尾的函数。
• 4 x：设当前序列为 $f = (f_0, f_1, \dots, f_{r-1})$，输出$$f_{r-1}(f_{r-2}(\cdots f_0(x)\cdots)) \bmod 998244353.$$若序列为空，直接输出 $x$。

注意：复合顺序为从左到右：先应用 $f_0$，再 $f_1$，…，最后 $f_{r-1}$。

约束条件

• $1 \leq Q \leq 500\,000$
• $1 \leq a < 998244353$
• $0 \leq b, x < 998244353$
• 序列在执行查询 2 或 3 时非空。

输入

$Q$
Query₀
Query₁
:
Query$_{Q-1}$

其中每条查询为：

• 0 a b
• 1 a b
• 2
• 3
• 4 x

输出

对每个类型 4 的查询，输出一行：复合结果 $\bmod 998244353$。

6
1 4 5
4 3
0 2 1
4 2
3
4 3

17
25
7

1
4 1333

1333