虽然Iris偶尔会提出一个解法可能错误的问题,但她仍然坚持用自己的想象力制造问题;毕竟,每个人都一直在固执地走在路上……就像以前一样,艾丽丝提出了一个问题,但她给出了错误的解决方案,但克里斯总是应该拯救它!你现在将扮演克里斯的角色:
- 给 Chris 两个数组 $$$a$$$ 和 $$$b$$$,均由 $$$n$$$ 整数组成。
- Iris 对任意重新排列 $$$b$$$ 后 $$$P = \prod\limits_{i=1}^n \min(a_i, b_i)$$$ 的最大可能值感兴趣。请注意,她只想知道 $$$P$$$ 的最大值,并没有对 $$$b$$$ 执行实际的重新排列。
- 将会有 $$$q$$$ 修改。每个修改可以用两个整数 $$$o$$$ 和 $$$x$$$ 表示($$$o$$$ 是 $$$1$$$ 或 $$$2$$$,$$$1 \leq x \leq n$$$)。如果 $$$o = 1$$$,则 Iris 会将 $$$a_x$$$ 增加 $$$1$$$;否则,她会将 $$$b_x$$$ 增加 $$$1$$$。
- Iris 询问 Chris $$$P$$$ 的最大值 $$$q + 1$$$ 次:在任何修改之前询问一次,然后在每次修改之后询问一次。
- 由于 $$$P$$$ 可能很大,Chris 只需要对 $$$998\,244\,353$$$ 进行模计算。
克里斯很快就解决了这个问题,但他太累了,睡着了。除了感谢 Chris 之外,现在轮到您编写一个程序来计算给定输入数据的答案。
注意:由于输入和输出很大,因此您可能需要针对此问题对其进行优化。
例如,在 C++ 中,在 main() 函数的开头使用以下几行就足够了:
输入
每个测试包含多个测试用例。输入的第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$q$$$ ($$$1 \leq n \leq 2\cdot 10^5$$$, $$$1 \leq q \leq 2\cdot 10^5$$$) — 数组的长度和操作数。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 5\cdot 10^8$$$) - 数组 $$$a$$$。
每个测试用例的第三行包含 $$$n$$$ 整数 $$$b_1, b_2, \ldots, b_n$$$ ($$$1 \leq b_i \leq 5\cdot 10^8$$$) — 数组 $$$b$$$。
接下来是 $$$q$$$ 行,每行包含两个整数 $$$o$$$ 和 $$$x$$$ ($$$o \in \{1, 2\}$$$, $$$1 \leq x \leq n$$$),代表一个运算。
保证所有测试用例的 $$$n$$$ 之和和 $$$q$$$ 之和分别不超过 $$$4\cdot 10^5$$$。
输出
对于每个测试用例,在一行中输出 $$$q + 1$$$ 整数,代表 Chris 将计算的答案,以 $$$998\,244\,353$$$ 为模。
示例
输入 #1
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
输出 #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\limits_{i=1}^n \min(a_i, b_i) = 1 \cdot 1 \cdot 2 = 2$$$。我们可以证明这是最大可能值。例如,如果 Chris 重新排列 $$$b = [2, 3, 1]$$$,$$$P$$$ 将等于 $$$1 \cdot 1 \cdot 1 = 1 < 2$$$,这不是最优的。
- 第一次修改后,Chris 可以将 $$$b$$$ 重新排列为 $$$[1, 2, 3]$$$,以便 $$$P = 1 \cdot 1 \cdot 3 = 3$$$,从而最大化。
- 第二次修改后,Chris 可以将 $$$b$$$ 重新排列为 $$$[2, 2, 3]$$$,使得 $$$P = 1 \cdot 1 \cdot 3 = 3$$$,从而最大化。
- 第三次修改后,Chris 可以将 $$$b$$$ 重新排列为 $$$[2, 2, 3]$$$,从而使 $$$P = 6$$$ 最大化。
- 第四次修改后,Chris 可以将 $$$b$$$ 重新排列为 $$$[2, 2, 4]$$$,从而使 $$$P = 6$$$ 最大化。