小钟有一个长度为 n 的 01 串 s (仅由字符 0 和 1 组成,如 0101101 ),还有 m 个数字 a1,a2,...,am 。
他想知道:是否能选择 m 个不相交的区间 [l1,r1],[l2,r2],...,[lm,rm],使得每个数字 ai 的二进制表示(无前置0 , 0 的二进制就是 "0 "),都能被 s 中对应的连续子串 s[li..ri] 精确表示。
输入包括多组测试数据。
1.第一行包括一个正整数 T(1≤T≤20),表示测试数据组数。
2.每组测试数据:
第一行有两个整数 n(1≤n≤100),m(1≤m≤6),分别表示 01 串 s 的长度和数字个数。
第二行有一行长度为 n 的 01 串 s 。
第三行有 m 个整数 a1,a2,...am(0≤ai<210),表示待匹配的数字。
对于每组测试数据,输出一行:
若存在满足条件的 m 个不相交区间,输出 YEs
否则输出 NO
输入
2
5 2
10110
2 1
5 1
00000
1
输出
YES
NO
说明
对于第一组测试数据,2 的二进制表示为 10,1 的二进制表示为 1 ,其中一种可以选择的区间 为 [1,2]、[3,3]。
对于第二组测试数据,1 的二进制表示为 1,由于 01 串中不存在字符 1,故答案一定不存在。