Loading [MathJax]/jax/output/HTML-CSS/fonts/TeX/fontdata.js

D. Yet Another Inversions Problem
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a permutation p0,p1,,pn1 of odd integers from 1 to 2n1 and a permutation q0,q1,,qk1 of integers from 0 to k1.

An array a0,a1,,ank1 of length nk is defined as follows:

aik+j=pi2qj for all 0i<n and all 0j<k

For example, if p=[3,5,1] and q=[0,1], then a=[3,6,5,10,1,2].

Note that all arrays in the statement are zero-indexed. Note that each element of the array a is uniquely determined.

Find the number of inversions in the array a. Since this number can be very large, you should find only its remainder modulo 998244353.

An inversion in array a is a pair (i,j) (0i<j<nk) such that ai>aj.

Input

The first line contains a single integer t (1t104) — the number of test cases.

The first line of each test case contains two integers n and k (1n,k2105) — the lengths of arrays p and q.

The second line of each test case contains n distinct integers p0,p1,,pn1 (1pi2n1, pi is odd) — the array p.

The third line of each test case contains k distinct integers q0,q1,,qk1 (0qi<k) — the array q.

It is guaranteed that the sum of n over all test cases doesn't exceed 2105 and the sum of k over all test cases doesn't exceed 2105.

Output

For each test case, output one integer: the number of inversions in array a modulo 998244353.

Example
Input
4
3 2
3 5 1
0 1
3 4
1 3 5
3 2 0 1
1 5
1
0 1 2 3 4
8 3
5 1 7 11 15 3 9 13
2 0 1
Output
9
25
0
104
Note

In the first test case, array a is equal to [3,6,5,10,1,2]. There are 9 inversions in it: (0,4), (0,5), (1,2), (1,4), (1,5), (2,4), (2,5), (3,4), (3,5). Note that these are pairs (i,j) such that i<j and ai>aj.

In the second test case, array a is equal to [8,4,1,2,24,12,3,6,40,20,5,10]. There are 25 inversions in it.

In the third test case, array a is equal to [1,2,4,8,16]. There are no inversions in it.