可持久化区间仿射区间求和

【题目描述】

给定一个长度为 $N$ 的整数序列 $a_0, a_1, \dots, a_{N-1}$。 令 $A_{-1}$ 表示序列 $(a_0, a_1, \dots, a_{N-1})$。

对于 $i=0,1,\ldots,Q-1$，依次处理如下查询：

• 0 k l r b c：将 $A_k$ 复制一份作为 $A_i$。对 $A_i$ 中的每个 $j = l, l+1, \dots, r - 1$，令 $a_j \gets b \times a_j + c$。
• 1 k s l r：将 $A_k$ 复制一份作为 $A_i$。对 $A_i$ 中的每个 $j = l, l+1, \dots, r - 1$，令 $a_j \gets a'_j$（其中 $a'_j$ 是 $a_j$ 在 $A_s$ 中的值）。
• 2 k l r：输出 $A_k$ 中的 $\sum_{j = l}^{r - 1} a_j \bmod 998244353$。

【输入】

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

【输出】

对每个类型为 2 的查询输出一行一个整数。

【输入样例】

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

【输入样例2】

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

【输出样例2】

339995755
347764691
266369014
783560804

【数据范围】

设 $t_i$ 表示第 $i$ 个查询的类型（$0\leq i \lt Q$，$t_i\in\lbrace 0,1,2\rbrace$）。

• $1 \leq N \leq 100000$
• $1 \leq Q \leq 100000$
• $0 \leq a \lt 998244353$
• $1 \leq b \lt 998244353$
• $0 \leq c \lt 998244353$
• $-1 \leq k \lt i$
• $k=-1$ 或 $t_k\in\lbrace 0,1\rbrace$
• $-1 \leq s \lt i$
• $s=-1$ 或 $t_s\in\lbrace 0,1\rbrace$
• $0 \leq l \lt r \leq N$

【来源】

Library Checker（yosupo06） persistent_range_affine_range_sum