Mr. Panda 喜欢解决难题。在 Mr. Panda 的生日那天，Mr. Sheep 送给 Mr. Panda 一个谜题作为生日礼物。

在这个谜题中，Mr. Panda 得到一个由正整数组成的序列。他可以对该序列执行多次操作。一次操作定义为选取序列的一个前缀并将其反转。Mr. Panda 必须按照前缀长度递增的顺序执行操作。为了解决这个谜题，Mr. Panda 需要找出操作后字典序最小的序列。

Mr. Sheep 觉得这个谜题对 Mr. Panda 来说太简单了。因此，Mr. Sheep 将序列中的某些前缀列入黑名单。Mr. Panda 不能反转任何被列入黑名单的前缀。

尽管今天是 Mr. Panda 的生日，但他感到很难过，因为他不知道如何解决这个谜题。你能帮 Mr. Panda 解决这个谜题让他开心起来吗？

输入格式

第一行输入包含测试用例的数量 $T$ ($1 \le T \le 100$)。接下来是 $T$ 个测试用例。

每个测试用例的第一行包含两个整数 $N$ ($1 \le N \le 3 \times 10^5$)，即 Mr. Panda 序列的长度，以及 $M$ ($0 \le M \le N$)，即被列入黑名单的前缀数量。保证所有测试用例的 $N$ 之和不超过 $5 \times 10^6$。

接下来一行包含 $N$ 个整数，第 $i$ 个整数 $A_i$ ($1 \le A_i \le 10^9$) 表示 Mr. Panda 序列中的第 $i$ 个整数。

最后一行包含 $M$ 个不同的整数，第 $i$ 个数字 $B_i$ ($1 \le B_i \le N$) 表示被列入黑名单的前缀长度。

输出格式

对于每个测试用例，输出一行，包含 “Case x: y”，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是 Mr. Panda 能得到的字典序最小的序列的哈希值。

整数序列的哈希值可以通过以下公式计算：

$$\text{HashCode}(s) = \left( \sum_{i=1}^{\text{len}(s)} 37^{i-1} s_i \right) \mod 20181125$$

例如： $\text{HashCode}([1, 2, 3]) = (1 + 2 \times 37 + 3 \times 37^2) \mod 20181125 = 4182$ 以及 $\text{HashCode}([1, 2, 3, 456789]) = (1 + 2 \times 37 + 3 \times 37^2 + 456789 \times 37^3) \mod 20181125 = 10168149$

样例

输入 1

5
4 0
2 2 1 2
5 0
1 1 1 1 1
3 0
3 2 1
3 1
3 2 1
3
3 2
3 2 1
3 2

输出 1

Case 1: 104119
Case 2: 1926221
Case 3: 4182
Case 4: 1482
Case 5: 1446

说明

1. 对于序列 $x_1, x_2, \dots, x_n$，反转后变为 $x_n, x_{n-1}, \dots, x_1$。
2. 对于两个长度相同的序列 $x$ 和 $y$，$x$ 的字典序小于 $y$ 当且仅当存在某个 $i$，使得 $x_1 = y_1, x_2 = y_2, \dots, x_{i-1} = y_{i-1}$ 且 $x_i < y_i$。