题目内容

给定一个长度为 $n$ 的二进制串 $S$（仅包含字符 0 和 1），以及 $m$ 个非负整数 $b_1, b_2, \dots, b_m$。

对于每个 $b_i$，取其无前导零的二进制表示作为它的模式串；特别地，若 $b_i = 0$，则模式串定义为单个字符 0。

你需要判断是否能在 $S$ 中选出 $m$ 个互不相交的连续子串，使得第 $i$ 个子串恰好等于 $b_i$ 的模式串。

约束条件：

• 测试用例总数 $T$ 满足 $1 \le T \le 20$。
• 串长度 $n$ 满足 $1 \le n \le 100$。
• 整数个数 $m$ 满足 $1 \le m \le 6$。
• 每个整数满足 $0 \le b_i < 2^{10}$。

输入描述

第一行包含一个整数 $T$，表示测试用例的数量。

接下来每个测试用例按以下格式给出：

• 第一行包含两个整数 $n$ 和 $m$，分别表示二进制串的长度和整数个数。
• 第二行是一个长度为 $n$ 的字符串，仅包含字符 0 和 1。
• 第三行包含 $m$ 个整数 $b_1, b_2, \dots, b_m$，表示待匹配的数字。

输出描述

对于每个测试用例，输出一行：若存在满足条件的 $m$ 个不相交区间则输出 YES，否则输出 NO。

样例1

输入

1
8 3
10101010
2 5 0

输出

YES

说明

二进制表示：$b_1=2$ 的模式串为 "10"，$b_2=5$ 为 "101"，$b_3=0$ 为 "0"。 在 $S = \texttt{10101010}$ 中，我们可以选择区间 $[3,5]$ 匹配 "101"（对应 $b_2$），区间 $[6,6]$ 匹配 "0"（对应 $b_3$），区间 $[7,8]$ 匹配 "10"（对应 $b_1$）。 这三个区间互不相交，因此可以选出所需的 3 个子串，输出 YES。

样例2

输入

1
4 2
1010
5 2

输出

NO

说明

$b_1=5$ 的模式串为 "101"，$b_2=2$ 为 "10"。$S = \texttt{1010}$。 "101" 只能出现在区间 $[1,3]$。若选用它，剩余字符为第 4 位的 "0"，无法构成 "10"。 若不选 "101"，两个 "10" 分别出现在 $[1,2]$ 和 $[3,4]$，只能选取其中一个，且无法再放入 "101"。 因此不存在互不相交的选取方案，输出 NO。

样例3

输入

1
10 4
0010110100
1 2 4 0

输出

YES

说明

模式串：$b_1=1$ 为 "1"，$b_2=2$ 为 "10"，$b_3=4$ 为 "100"，$b_4=0$ 为 "0"。 $S = \texttt{0010110100}$ 长度为 10。我们可以选择区间 $[1,1]$ 作为 "0"，$[3,4]$ 作为 "10"，$[5,5]$ 作为 "1"，$[8,10]$ 作为 "100"。 这四个区间互不相交，满足所有数字的匹配要求，因此输出 YES。