D. Refined Product Optimalitytime limit per test3 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard outputAs a tester, when my solution has a different output from the example during testing, I suspect the author first.— Chris, a commentAlthough Iris occasionally sets a problem where the solution is possibly wrong, she still insists on creating problems with her imagination; after all, everyone has always been on the road with their stubbornness... And like ever before, Iris has set a problem to which she gave a wrong solution, but Chris is always supposed to save it! You are going to play the role of Chris now: Chris is given two arrays $$$a$$$ and $$$b$$$, both consisting of $$$n$$$ integers. Iris is interested in the largest possible value of $$$P = \prod\limits_{i=1}^n \min(a_i, b_i)$$$ after an arbitrary rearrangement of $$$b$$$. Note that she only wants to know the maximum value of $$$P$$$, and no actual rearrangement is performed on $$$b$$$. There will be $$$q$$$ modifications. Each modification can be denoted by two integers $$$o$$$ and $$$x$$$ ($$$o$$$ is either $$$1$$$ or $$$2$$$, $$$1 \leq x \leq n$$$). If $$$o = 1$$$, then Iris will increase $$$a_x$$$ by $$$1$$$; otherwise, she will increase $$$b_x$$$ by $$$1$$$. Iris asks Chris the maximum value of $$$P$$$ for $$$q + 1$$$ times: once before any modification, then after every modification. Since $$$P$$$ might be huge, Chris only needs to calculate it modulo $$$998\,244\,353$$$. Chris soon worked out this problem, but he was so tired that he fell asleep. Besides saying thanks to Chris, now it is your turn to write a program to calculate the answers for given input data.Note: since the input and output are large, you may need to optimize them for this problem.For example, in C++, it is enough to use the following lines at the start of the main() function:int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); std::cout.tie(nullptr);}InputEach test contains multiple test cases. The first line of input contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases. The description of test cases follows.The first line of each test case contains two integers $$$n$$$ and $$$q$$$ ($$$1 \leq n \leq 2\cdot 10^5$$$, $$$1 \leq q \leq 2\cdot 10^5$$$) — the length of the array and the number of operations.The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 5\cdot 10^8$$$) — the array $$$a$$$.The third line of each test case contains $$$n$$$ integers $$$b_1, b_2, \ldots, b_n$$$ ($$$1 \leq b_i \leq 5\cdot 10^8$$$) — the array $$$b$$$.Then $$$q$$$ lines follow, each line contains two integers $$$o$$$ and $$$x$$$ ($$$o \in \{1, 2\}$$$, $$$1 \leq x \leq n$$$), representing an operation.It's guaranteed that the sum of $$$n$$$ and the sum of $$$q$$$ over all test cases does not exceed $$$4\cdot 10^5$$$, respectively.OutputFor each test case, output $$$q + 1$$$ integers in a line, representing the answers that Chris will calculate, modulo $$$998\,244\,353$$$.ExampleInput43 41 1 23 2 11 32 31 12 16 81 4 2 7 3 57 6 5 6 3 32 51 61 51 51 52 32 31 613 87 7 6 6 5 5 5 2 2 3 4 5 11 4 1 9 6 6 9 1 5 1 3 8 42 22 112 42 41 71 12 121 55 310000000 20000000 30000000 40000000 5000000010000000 20000000 30000000 40000000 500000001 12 22 1Output2 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
NoteIn the first test case: Before the modifications, Chris can rearrange $$$b$$$ to $$$[1, 2, 3]$$$ so that $$$P = \prod\limits_{i=1}^n \min(a_i, b_i) = 1 \cdot 1 \cdot 2 = 2$$$. We can prove that this is the maximum possible value. For example, if Chris rearranges $$$b = [2, 3, 1]$$$, $$$P$$$ will be equal $$$1 \cdot 1 \cdot 1 = 1 < 2$$$, which is not optimal. After the first modification, Chris can rearrange $$$b$$$ to $$$[1, 2, 3]$$$ so that $$$P = 1 \cdot 1 \cdot 3 = 3$$$, which is maximized. After the second modification, Chris can rearrange $$$b$$$ to $$$[2, 2, 3]$$$ so that $$$P = 1 \cdot 1 \cdot 3 = 3$$$, which is maximized. After the third modification, Chris can rearrange $$$b$$$ to $$$[2, 2, 3]$$$ so that $$$P = 6$$$, which is maximized. After the fourth modification, Chris can rearrange $$$b$$$ to $$$[2, 2, 4]$$$ so that $$$P = 6$$$, which is maximized.