可持久化区间仿射区间和（Persistent Range Affine Range Sum）

问题描述

给定一个长度为 $N$ 的整数序列 $a_0, a_1, \dots, a_{N-1}$。令 $A_{-1}$ 表示初始序列 $(a_0, a_1, \dots, a_{N-1})$。
对 $i = 0, 1, \dots, Q-1$，按顺序处理第 $i$ 个查询：

• 0 k l r b c：以 $A_k$ 为模板创建新版本 $A_i$；对每个 $j = l, l+1, \dots, r-1$，在 $A_i$ 中令
  $a_j \leftarrow b \times a_j + c$。
• 1 k s l r：以 $A_k$ 为模板创建新版本 $A_i$；对每个 $j = l, l+1, \dots, r-1$，在 $A_i$ 中令 $a_j\leftarrow a'_j$（$a'_j$ 是 $A_s$ 中的数）
• 2 k l r：以 $A_k$ 为当前版本；输出 $\sum_{j=l}^{r-1} a_j \bmod 998244353$。

约束条件

• 设 $t_i$ 为第 $i$ 次操作的类型。（$0 \le i < Q,t\in\{0,1,2\}$）
• $1 \leq N, Q \leq 10^5$
• $0 \leq a < 998244353$
• $1 \leq b < 998244353$
• $0 \leq c < 998244353$
• $-1 \leq k < i$
• $-1 \leq s < i$
• $k = -1$ 或 $t_k \in \{0,1\}$
• $s = -1$ 或 $t_s \in \{0,1\}$
• $0 \leq l < r \leq N$

输入格式

$N\ Q$
$a_0\ \cdots\ a_{N-1}$
$Query_0$
$Query_1$
:
$Query_{Q-1}$

5 11
1 2 3 4 5
2 -1 0 5
0 -1 2 4 100 1
0 1 1 3 100 3
2 2 1 5
2 2 0 5
1 2 -1 1 3
2 5 0 1
2 5 0 2
2 5 0 3
2 5 0 4
2 5 0 5

15
30712
30713
1
3
6
407
412

10 10
98571302 347764691 874908879 522525408 665451426 585614689 752625419 867933974 588349757 331245164
2 -1 5 7
1 -1 -1 8 9
0 -1 3 4 559932567 67455332
1 1 1 0 8
1 3 1 5 9
2 1 1 2
1 2 -1 5 6
0 -1 0 9 703344909 379527638
2 6 2 9
2 7 7 9

339995755
347764691
266369014
783560804