CF2053D Refined Product Optimality

As a tester, when my solution has a different output from the example during testing, I suspect the author first. — Chris, [a comment](https://codeforces.com/blog/entry/133116?#comment-1190579) Although 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);

}


```
```
                            

Each 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.

For each test case, output $ q + 1 $ integers in a line, representing the answers that Chris will calculate, modulo $ 998\,244\,353 $ .

In 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.