题目内容

小艾有一条长度为 $n$ 的指令序列，仅由字符 0 和 1 组成。她手上有 $m$ 个任务，每个任务有一个非负整数编号 $a_i$。任务对应的指令片段就是该编号的二进制表示（没有前导 $0$，特别地，$0$ 的二进制表示为 "0"）。

现在她想从指令序列中切出 $m$ 个互不相交的连续子段，使得这些子段构成的集合恰好与 $m$ 个任务的指令片段一一匹配（每个片段恰好使用一次，顺序任意）。如果存在这样的划分方案，输出 YES；否则输出 NO。

数据范围：指令序列长度 $n$ 不超过 $100$，任务个数 $m$ 不超过 $6$，任务编号 $a_i$ 均为 $0$ 到 $1023$ 之间的整数，测试数据组数 $T$ 不超过 $20$。

样例

输入

2
5 2
10110
2 1
5 1
00000
1

输出

YES
NO

说明

对于第一组测试数据，$2$ 的二进制表示为 $10$，$1$ 的二进制表示为 $1$，其中一种可以选择的区间为 $[1,2]$、$[3,3]$。

对于第二组测试数据，$1$ 的二进制表示为 $1$，由于指令序列中不存在字符 1，故答案一定不存在。

输入描述

第一行一个整数 $T$，表示测试数据组数。 接下来每组数据按以下格式给出： 第一行包含两个整数 $n$ 和 $m$，保证 $1 \le n \le 100$，$1 \le m \le 6$。 第二行一个长度为 $n$ 的字符串，由 0 和 1 组成。 第三行 $m$ 个整数 $a_1, a_2, \dots, a_m$，每个整数均在 $0$ 到 $1023$ 之间。

输出描述

对于每组测试数据，输出一行 YES 或 NO（大写）。

样例1

输入

1
5 3
01010
2 1 0

输出

YES

说明

任务编号 2 的二进制表示为 10，对应片段 10；编号 1 为 1；编号 0 为 0。 指令序列 01010 可切分为三个互不相交的连续子段：0（位置 1）、10（位置 2-3）、1（位置 4），恰好与三个任务的指令片段一一匹配，故输出 YES。

样例2

输入

1
3 2
101
2 2

输出

NO

说明

任务编号 2 的二进制表示为 10，需要两个片段 10。 指令序列 101 中仅存在一个子串 10（位置 1-2），无法切分出两个互不相交的 10，因此输出 NO。

样例3

输入

1
1 1
0
1

输出

NO

说明

任务编号 1 的二进制表示为 1，对应片段 1。 指令序列 0 中不包含子串 1，无法匹配，因此输出 NO。