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 ith element in A with B[j] and jth 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.
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor
Login to unlock the editorial