点修区间排序区间复合（Point Set Range Sort Range Composite）

问题描述

给定一个三元组整数序列 $\big((p_i, a_i, b_i)\big)_{0 \le i < N}$。处理 $Q$ 个查询如下：

• 0 i p a b：将 $(p_i, a_i, b_i)$ 更新为 $(p, a, b)$。
• 1 l r x：输出 $f_{r-1}(f_{r-2}(\cdots f_l(x)\cdots)) \bmod 998244353$，其中 $f_i(x) := a_i x + b_i$。
• 2 l r：将子序列 $\big((p_i, a_i, b_i)\big)_{l \le i < r}$ 按 $p_i$ 升序排序。
• 3 l r：将子序列 $\big((p_i, a_i, b_i)\big)_{l \le i < r}$ 按 $p_i$ 降序排序。

约束条件

• $1 \leq N \leq 10^5$
• $1 \leq Q \leq 10^5$
• $0 \leq i < N$
• $0 \leq p_i, p \leq 10^9$
• 所有 $p_i$、以及查询 0 中给出的 $p$ 均互异。
• $0 \leq a_i, a < 998244353$
• $0 \leq b_i, b < 998244353$
• $0 \leq x < 998244353$
• $0 \leq l < r \leq N$

输入

$N\ Q$
$p_0\ a_0\ b_0$
$p_1\ a_1\ b_1$
:
$p_{N-1}\ a_{N-1}\ b_{N-1}$
Query₀
Query₁
:
Query$_{Q-1}$

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

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

123
314
435
653