D. Очередная задача про инверсии
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам даны перестановка $$$p_0, p_1, \ldots, p_{n-1}$$$ нечётных чисел от $$$1$$$ до $$$2n-1$$$ и перестановка $$$q_0, q_1, \ldots, q_{k-1}$$$ целых чисел от $$$0$$$ до $$$k-1$$$.

Определим массив $$$a_0, a_1, \ldots, a_{nk-1}$$$ длины $$$nk$$$ в соответствии со следующим правилом:

$$$a_{i \cdot k+j}=p_i \cdot 2^{q_j}$$$ для всех $$$0 \le i < n$$$ и всех $$$0 \le j < k$$$

Например, если $$$p = [3, 5, 1]$$$ и $$$q = [0, 1]$$$, то $$$a = [3, 6, 5, 10, 1, 2]$$$.

Обратите внимание, что все массивы в условии нумеруются с нуля. Также обратите внимание, что каждый элемент массива $$$a$$$ определён однозначно.

Найдите количество инверсий в массиве $$$a$$$. Так как ответ может быть очень большим, выведите его по модулю $$$998\,244\,353$$$.

Инверсией в массиве $$$a$$$ называется пара $$$(i, j)$$$ ($$$0 \le i < j < nk$$$), такая что $$$a_i > a_j$$$.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора содержит два числа $$$n$$$ и $$$k$$$ ($$$1 \le n, k \le 2 \cdot 10^5$$$) — длины массивов $$$p$$$ и $$$q$$$.

Вторая строка каждого набора содержит $$$n$$$ различных целых чисел $$$p_0, p_1, \ldots, p_{n-1}$$$ ($$$1 \le p_i \le 2n-1$$$, $$$p_i$$$ нечётно) — массив $$$p$$$.

Третья строка каждого набора содержит $$$k$$$ различных целых чисел $$$q_0, q_1, \ldots, q_{k-1}$$$ ($$$0 \le q_i < k$$$) — массив $$$q$$$.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$, и что сумма $$$k$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите одно число — количество инверсий в массиве $$$a$$$ по модулю $$$998\,244\,353$$$.

Пример
Входные данные
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
Выходные данные
9
25
0
104
Примечание

В первом наборе входных данных массив $$$a$$$ равен $$$[3, 6, 5, 10, 1, 2]$$$. В нём есть $$$9$$$ инверсий: $$$(0, 4)$$$, $$$(0, 5)$$$, $$$(1, 2)$$$, $$$(1, 4)$$$, $$$(1, 5)$$$, $$$(2, 4)$$$, $$$(2, 5)$$$, $$$(3, 4)$$$, $$$(3, 5)$$$. Обратите внимание, что здесь перечислены пары $$$(i, j)$$$, такие что $$$i < j$$$ и $$$a_i > a_j$$$.

Во втором наборе входных данных массив $$$a$$$ равен $$$[8, 4, 1, 2, 24, 12, 3, 6, 40, 20, 5, 10]$$$. В нём $$$25$$$ инверсий.

В третьем наборе входных данных массив $$$a$$$ равен $$$[1, 2, 4, 8, 16]$$$. В нём нет инверсий.