As a tester, when my solution has a different output from the example during testing, I suspect the author first.

— Chris, a comment

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);
}

Input

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.

Output

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

Note

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 \lt 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.

#	Name	Rating↕	Solved↕
2197A	Friendly Numbers binary search brute force expression parsing math schedules	800	23.9k
2053D	Refined Product Optimality binary search data structures greedy math schedules sortings	1700	7.8k
2020C	Bitwise Balancing bitmasks hashing implementation math schedules ternary search	1400	18.7k
1955F	Unfair Game dp games greedy math schedules	1800	8.9k

Problemset