题目描述

给定 $n$ 个正整数 $a_1,a_2,…,a_n$ ($1≤a_i<2^m$) 以及 $0$ 到 $2^m−1$ 的权重 $w_0,w_1,…,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(w_{f(A)},w_{f(B)},w_{f(C)},w_{f(D)})−\min(w_{f(A)},w_{f(B)},w_{f(C)},w_{f(D)}) $$

注意：每组都可以为空，此时 $f(⋅)=0$。

输入格式

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

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

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

第三行包含 $2^m$ 个整数 $w_0,w_1,…,w_{2^m−1}$ ($0≤w_i≤10^9$)。

输出格式

对于每组数据输出一行一个整数，即 $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