区间赋值区间复合（Range Set Range Composite）

问题描述

给定一个长度为 $N$ 的线性函数序列 $f_0, f_1, \dots, f_{N-1}$，其中对每个 $i$，有 $f_i(x) = a_i x + b_i$。
请按顺序处理以下 $Q$ 个查询：

• 0 l r c d：对每个 $i = l, l+1, \dots, r-1$，将 $f_i$ 更新为 $f_i(x) \leftarrow c x + d$。
• 1 l r x：计算并输出 $f_{r-1}(f_{r-2}(\cdots f_l(x)\cdots)) \bmod 998244353$。

约束条件

• $1 \leq N, Q \leq 5 \times 10^5$
• $1 \leq a_i, c < 998244353$
• $0 \leq b_i, d, x < 998244353$
• $0 \leq l < r \leq N$

输入格式

$N\ Q$
$a_0\ b_0$
$a_1\ b_1$
:
$a_{N-1}\ b_{N-1}$
$Query_0$
$Query_1$
:
$Query_{Q-1}$

5 7
1 2
3 4
5 6
7 8
9 10
1 0 5 11
1 2 4 12
0 1 2 13 14
1 0 4 15
1 2 5 16
0 0 5 10 1
1 0 5 1

14005
470
8275
5500
111111