区间赋值区间复合

【题目描述】

给定一个长度为 $N$ 的线性函数序列 $f _ 0, f _ 1, ..., 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 \gets cx + d$。
• 1 $l$ $r$ $x$：输出 $f _ {r-1}(f _ {r-2}(...f _ l(x))) \bmod 998244353$。

【输入】

输入按以下格式给出：

$N$ $Q$
$a _ 0$ $b _ 0$
$a _ 1$ $b _ 1$
:
$a _ {N - 1}$ $b _ {N - 1}$
$\textrm{Query} _ 0$
$\textrm{Query} _ 1$
:
$\textrm{Query} _ {Q - 1}$

【输出】

对每个 1 $l$ $r$ $x$ 查询，输出一行一个整数，表示该查询的答案。

【输入样例】

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

【数据范围】

• $1 \leq N, Q \leq 500000$
• $1 \leq a _ i, c < 998244353$
• $0 \leq b _ i, d, x < 998244353$
• $0 \leq l < r \leq N$

【来源】

Library Checker（yosupo06） range_set_range_composite