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

问题描述

给定一个长度为 $N$ 的线性函数序列 $f_0, f_1, \dots, f_{N-1}$，其中对每个 $i$，有 $f_i(x) = a_i x + b_i$ .

请按顺序处理以下 $Q$ 个查询：

• 0 p c d：将 $f_p$ 更新为 $f_p(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 500\,000$
• $1 \leq a_i, c < 998244353$
• $0 \leq b_i, d, x < 998244353$
• $0 \leq p < N$
• $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 5
1 2
3 4
5 6
7 8
9 10
1 0 5 11
1 2 4 12
0 1 13 14
1 0 4 15
1 2 5 16

14005
470
8275
5500