You are given 2 arrays A and B of length N and M respectively. You define F(A, B) as follows:

                                                    $F(A, B) = \sum\limits_{i=1}^{N} \sum\limits_{j=1}^{M} A[i]\times B[j] \times (i + j)$

You are also given an integer Q denoting the Q queries of the following types:

• 1 i j: Swap A[i] and B[j], that is you replace the i^th element in A with B[j] and j^th element in B with A[i]
• 2 i j: Swap A[i] and A[j], as described above
• 3 i j: Swap B[i] and B[j], as described above

Task

Given Q queries in form of array queries, you need to output Q + 1 integers. The initial value of F(A, B) and the values after each query. The value of F(A, B) can be very large so, output the values modulo 998244353.

Notes

• Assume 1-based indexing
• Queries are dependent.

Example

Assumptions

• T = 1
• N = 2
• M = 2
• A = [2, 4]
• B = [1, 5]
• Q = 1
• queries = [ [1, 2, 1] ]

Approach

• You first evaluate F(A, B) = A[1]*B[1]*( 1 + 1 ) + A[1]*B[2]*( 1 + 2 ) + B[1]*A[2]*( 1 + 2 ) + B[2]*A[2]*( 2 + 2 ) = 2*1*2 + 2*5*3 + 1*4*3 + 5*4*4 = 4 + 30 + 12 + 80 = 126.
• You swap A[2] and B[1], therefore A becomes [2, 1] and B becomes [4, 5], F(A, B) = A[1]*B[1]*( 1 + 1 ) + A[1]*B[2]*( 1 + 2 ) + B[1]*A[2]*( 1 + 2 ) + B[2]*A[2]*( 2 + 2 ) = 2*4*2 + 2*5*3 + 4*1*3 + 1*5*4 = 16 + 30 + 12 + 20 = 78.
• You, therefore, output "126 78" in a single line.

Function description

Complete the array_queries function provided in the editor. This function takes the following 6 parameters and returns a vector/array denoting the values of F(A, B) for all queries:

• N: Represents an integer denoting the length of array A
• M: Represents an integer denoting the length of array B
• A: Represents the integer array A
• B: Represents the integer array B
• Q: Represents an integer denoting the number of queries
• queries: Represents a 2D array/vector denoting queries of the type "1 i j" or "2 i j" or "3 i j". Therefore, the size of the queries array is Q*3.

Input format

Note: This is the input format that you must use to provide custom input (available above the Compile and Test button).

• The first line contains a single integer T, which denotes the number of test cases. T also specifies the number of times you have to run the array_queries function on a different set of inputs.
• For each test case:
  • The first line contains an integer N denoting the length of the array A.
  • The second line contains an integer M denoting the length of the array B.
  • The third line contains N space-separated integers denoting array A.
  • The fourth line contains M space-separated integers denoting array B.
  • The fifth line contains an integer Q denoting the number of queries.
  • The next Q lines follow. For each line:
    • The first line contains three space-separated integers denoting tp, i and j, where tp = 1, 2 or 3.

Output format

For each test case in a new line, print Q + 1 space-separated integers denoting the initial value of F(A, B) and F(A, B) after each query. Do not forget to take modulo 998244353.

Constraints

$1 \leq T \leq 10 \\ 1\leq N, M \leq 10^5 \\ 1 \leq A[i], B[i] \leq 10^6 \\ 1 \leq Q \leq 10^5 \\ \text{If query is of type 1: } 1 \leq i \leq N, 1 \leq j \leq M \\ \text{If query is of type 2: } 1 \leq i, j \leq N \\ \text{If query is of type 3: } 1 \leq i, j \leq M$

Code snippets (also called starter code/boilerplate code) 

This question has code snippets for C, CPP, Java, and Python.