D. 优化乘积最大化

时间限制：每个测试点 $3$ 秒 内存限制：每个测试点 $512$ 兆字节

作为一名测试者，当我的程序在测试时与样例输出不同，我首先怀疑出题人。 —— 某评论 Chris

尽管 Iris 偶尔会出一道标程可能有误的题目，但她依然坚持用自己的想象力出题；毕竟，每个人都始终带着自己的固执前行……而和往常一样，Iris 又出了一道她给出了错误解法的题目，但 Chris 总会来救场！现在，你要扮演 Chris 的角色：

Chris 得到两个数组 $a$ 和 $b$，均包含 $n$ 个整数。

Iris 想知道：在对 $b$ 进行任意重排后，

$$P=\prod_{i=1}^n \min(a_i,b_i)$$

的最大可能值。注意只需要求出 $P$ 的最大值，不需要实际对 $b$ 进行重排。

接下来会有 $q$ 次修改操作。每次修改用两个整数 $o$ 和 $x$ 表示（$o$ 为 $1$ 或 $2$，$1\le x\le n$）：

• 若 $o=1$，则将 $a_x$ 增加 $1$；
• 若 $o=2$，则将 $b_x$ 增加 $1$。

Iris 会让 Chris 计算 $q+1$ 次 $P$ 的最大值： 一次在所有修改之前，之后每次修改后各计算一次。

由于 $P$ 可能极大，Chris 只需要将结果对 $998244353$ 取模。

Chris 很快解出了这道题，但他太累睡着了。除了感谢 Chris 之外，现在轮到你写程序来计算给定输入的答案了。

注意：由于输入输出量较大，你可能需要对其进行优化。 例如在 C++ 中，在 main() 函数开头加入以下代码即可：

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr); std::cout.tie(nullptr);
}

输入格式

每个测试点包含多组测试数据。 第一行一个整数 $t$（$1\le t\le 10^4$）—— 测试数据组数。 每组测试数据描述如下：

第一行两个整数 $n,q$（$1\le n\le 2\cdot 10^5$，$1\le q\le 2\cdot 10^5$）—— 数组长度与操作次数。

第二行 $n$ 个整数 $a_1,a_2,\dots,a_n$（$1\le a_i\le 5\cdot 10^8$）—— 数组 $a$。

第三行 $n$ 个整数 $b_1,b_2,\dots,b_n$（$1\le b_i\le 5\cdot 10^8$）—— 数组 $b$。

接下来 $q$ 行，每行两个整数 $o,x$（$o\in\{1,2\}$，$1\le x\le n$），表示一次操作。

保证所有测试数据的 $n$ 之和与 $q$ 之和分别不超过 $4\cdot 10^5$。

输出格式

对于每组测试数据，在一行中输出 $q+1$ 个整数，表示 Chris 算出的答案，对 $998244353$ 取模。

样例输入

4
3 4
1 1 2
3 2 1
1 3
2 3
1 1
2 1
6 8
1 4 2 7 3 5
7 6 5 6 3 3
2 5
1 6
1 5
1 5
1 5
2 3
2 3
1 6
13 8
7 7 6 6 5 5 5 2 2 3 4 5 1
1 4 1 9 6 6 9 1 5 1 3 8 4
2 2
2 11
2 4
2 4
1 7
1 1
2 12
1 5
5 3
10000000 20000000 30000000 40000000 50000000
10000000 20000000 30000000 40000000 50000000
1 1
2 2
2 1

样例输出

2 3 3 6 6
840 840 1008 1344 1680 2016 2016 2016 2352
2116800 2646000 3528000 3528000 3528000 4233600 4838400 4838400 4838400
205272023 205272023 205272023 264129429

样例说明

在第一个测试用例中：

修改前，Chris 可以将 $b$ 重排为 $[1,2,3]$，使得

$$P=\prod_{i=1}^n\min(a_i,b_i)=1\cdot 1\cdot 2=2$$

可以证明这是最大可能值。例如若将 $b$ 重排为 $[2,3,1]$，则 $P=1\cdot 1\cdot 1=1<2$，不是最优。

第一次修改后，$b$ 重排为 $[1,2,3]$，$P=1\cdot 1\cdot 3=3$，达到最大。

第二次修改后，$b$ 重排为 $[2,2,3]$，$P=1\cdot 1\cdot 3=3$，达到最大。

第三次修改后，$b$ 重排为 $[2,2,3]$，$P=6$，达到最大。

第四次修改后，$b$ 重排为 $[2,2,4]$，$P=6$，达到最大。