单点赋值区间排序区间复合

【题目描述】

给定一个由整数三元组构成的序列 $\bigl((p_i, a_i, b_i)\bigr)_{0\leq i < N}$。依次处理 $Q$ 个查询，查询类型如下：

• 0 $i$ $p$ $a$ $b$：令 $(p_i,a_i,b_i) \gets (p,a,b)$。
• 1 $l$ $r$ $x$：输出 $f_{r-1}(f_{r-2}(...f_l(x))) \bmod 998244353$，其中 $f_i(x) := a_ix + b_i$。
• 2 $l$ $r$：将 $\bigl((p_i, a_i, b_i)\bigr)_{l\leq i < r}$ 排序，使得 $p_i$ 递增。
• 3 $l$ $r$：将 $\bigl((p_i, a_i, b_i)\bigr)_{l\leq i < r}$ 排序，使得 $p_i$ 递减。

【输入】

$N$ $Q$
$p_0$ $a_0$ $b_0$
$\vdots$
$p_{N-1}$ $a_{N-1}$ $b_{N-1}$
第 $0$ 个查询
$\vdots$
第 $Q - 1$ 个查询

【输出】

对于每个 1 $l$ $r$ $x$ 查询，输出一行，表示 $f_{r-1}(f_{r-2}(...f_l(x))) \bmod 998244353$ 的值。

【输入样例】

3 8
1 10 1
0 10 2
2 10 3
1 0 3 0
2 0 3
1 0 3 0
3 0 3
1 0 3 0
2 0 2
1 0 3 0
1 1 3 0

【输出样例】

123
213
312
132
32

【输入样例2】

3 10
5 10 1
2 10 2
4 10 3
1 0 3 0
0 1 8 10 4
2 0 3
1 0 3 0
0 1 3 10 5
3 0 3
1 0 3 0
0 0 1 10 6
2 1 3
1 0 3 0

【输出样例2】

123
314
435
653

【数据范围】

• $1 \leq N \leq 100000$
• $1 \leq Q \leq 100000$
• $0 \leq i < N$
• $0 \leq p_i, p \leq 1000000000$
• 所有 $p_i, p$（初始值以及查询 0 中给出的值）互不相同。
• $1 \leq a_i, a < 998244353$
• $0 \leq b_i, b < 998244353$
• $0 \leq x < 998244353$
• $0 \leq l < r \leq N$

【来源】

Library Checker（yosupo06） point_set_range_sort_range_composite