给你一个从 $$$1$$$ 到 $$$2n-1$$$ 的奇数排列 $$$p_0, p_1, \ldots, p_{n-1}$$$ 和从 $$$0$$$ 到 $$$0$$$ 的整数排列 $$$q_0, q_1, \ldots, q_{k-1}$$$ $$$k-1$$$。
长度为 $$$nk$$$ 的数组 $$$a_0, a_1, \ldots, a_{nk-1}$$$ 定义如下:
$$$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$$$ 为模。
示例
输入 #1
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
输出 #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]$$$。其中没有倒置。