该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Problem Description

给定 $n$ 个正整数 $a_1,a_2,\dots,a_n$ ($1\leq a_i<2^m$) 以及 $0$ 到 $2^m-1$ 的权重 $w_0,w_1,\dots,w_{2^m-1}$；你需要把这 $n$ 个正整数分成四组 $A,B,C,D$，令 $ f ( A ) , f ( B ) , f ( C ) , f ( D ) $ 分别表示每组中所有数字的异或和，你的分组方案需要最小化 $w_{f(A)},w_{f(B)},w_{f(C)},w_{f(D)}$ 的极差，即：
$$\max\left(w_{f(A)},w_{f(B)},w_{f(C)},w_{f(D)}\right)-\min\left(w_{f(A)},w_{f(B)},w_{f(C)},w_{f(D)}\right)$$
注意：每组都可以为空，此时 $ f ( \cdot ) = 0 $。

Input

第一行包含一个正整数 $T$ ($1\leq T\leq 5$)，表示测试数据的组数。

每组数据第一行包含两个正整数 $n,m$ ($4\leq n\leq 18$, $1\leq m\leq 10$)。

第二行包含 $n$ 个正整数 $a_1,a_2,\dots,a_n$ ($1\leq a_i<2^m$)。

第三行包含 $2^m$ 个整数 $w_0,w_1,\dots,w_{2^m-1}$ ($0\leq w_i\leq 10^9$)。

Output

对于每组数据输出一行一个整数，即 $w_{f(A)},w_{f(B)},w_{f(C)},w_{f(D)}$ 的极差的最小可能值。

2
4 2
1 2 3 1
0 1 2 3
7 4
3 2 15 13 11 9 7
12 13 14 15 16 1 2 3 4 5 6 7 8 9 10 11

1
2