动态序列区间仿射区间求和

【题目描述】

给定一个由 $N$ 个整数构成的序列 $a_0, a_1, ..., a_{N - 1}$。

按顺序处理 $Q$ 个如下类型的查询：

• 0 $i$ $x$：
  • 若 $i < |a|$，在 $a_i$ 之前插入 $x$
  • 若 $i = |a|$，在 $a_{|a| - 1}$ 之后插入 $x$
• 1 $i$：删除 $a_i$（剩余元素将拼接在一起）
• 2 $l$ $r$：翻转 $a_l, a_{l + 1}, a_{l + 2}, \dots, a_{r - 1}$
• 3 $l$ $r$ $b$ $c$：对于每个 $i = l, l + 1, l + 2, \dots, {r - 1}$，令 $a_i \gets b \times a_i + c$
• 4 $l$ $r$：输出 $\sum_{i = l}^{r - 1} a_i \bmod 998244353$

【输入】

$N$ $Q$
$a_0$ $a_1$ ... $a_{N - 1}$
$\textrm{Query}_0$
$\textrm{Query}_1$
:
$\textrm{Query}_{Q - 1}$

【输出】

对于每个 4 $l$ $r$ 查询，输出一行一个整数，表示对应的答案。

【输入样例】

5 6
1 10 100 1000 10000
4 1 4
0 2 100000
1 3
4 2 5
2 2 5
4 0 4

【输出样例】

1110
111000
11011

【数据范围】

• $1 \le N, Q \le 500000$
• $0 \le a_i \lt 998244353$
• 对于格式 0 $i$ $x$：
  • $0 \le i \le （当时的 |a|）$
  • $0 \le x \lt 998244353$
• 对于格式 1 $i$：
  • $0 \le i \lt （当时的 |a|）$
• 对于格式 2 $l$ $r$：
  • $0 \le l \lt r \le （当时的 |a|）$
• 对于格式 3 $l$ $r$ $b$ $c$：
  • $0 \le l \lt r \le （当时的 |a|）$
  • $0 \le b \lt 998244353$
  • $0 \le c \lt 998244353$
• 对于格式 4 $l$ $r$：
  • $0 \le l \lt r \le （当时的 |a|）$

【来源】

Library Checker（yosupo06） dynamic_sequence_range_affine_range_sum