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:

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

见题面 Input 部分

见题面 Output 部分

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.