双端队列（带全体复合操作）

【题目描述】

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

• 0 $a$ $b$：将线性函数 $\lambda x. ax + b$ 添加到序列 $f$ 的开头。
• 1 $a$ $b$：将线性函数 $\lambda x. ax + b$ 添加到序列 $f$ 的末尾。
• 2：删除序列 $f$ 开头的线性函数。
• 3：删除序列 $f$ 末尾的线性函数。
• 4 $x$：设 $f = (f_{l}, \dots, f_{r - 1})$，输出 $f _ {r - 1}(f _ {r - 2}(\dots (f _ l(x)) \dots)) \bmod 998244353$。当 $f = ()$ 时输出 $x$。

【输入】

输入格式如下：

$Q$
$\textrm{Query}_0$
$\textrm{Query}_1
:
$\textrm{Query}_{Q - 1}$

【输出】

对于每个类型为 4 的查询，输出一行一个整数，表示按照题意复合后的函数值。

【输入样例】

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

【输出样例】

17
25
7

【输入样例2】

1
4 1333

【输出样例2】

1333

【数据范围】

• $1 \leq Q \leq 500,000$
• $1 \leq a \lt 998244353$
• $0 \leq b, x \lt 998244353$
• 当查询 2 或查询 3 出现时，序列 $f$ 非空。

【来源】

Library Checker（yosupo06） deque_operate_all_composite