AquaMoon has two binary sequences $a$ and $b$, which contain only $0$ and $1$. AquaMoon can perform the following two operations any number of times ($a_1$ is the first element of $a$, $a_2$ is the second element of $a$, and so on):

Operation 1: if $a$ contains at least two elements, change $a_2$ to $\operatorname{min}(a_1,a_2)$, and remove the first element of $a$.

Operation 2: if $a$ contains at least two elements, change $a_2$ to $\operatorname{max}(a_1,a_2)$, and remove the first element of $a$.

Note that after a removal of the first element of $a$, the former $a_2$ becomes the first element of $a$, the former $a_3$ becomes the second element of $a$ and so on, and the length of $a$ reduces by one.

Determine if AquaMoon can make $a$ equal to $b$ by using these operations.


-----Input-----

The first line contains a single integer $t$ ($1 \leq t \leq 2000$) — the number of test cases. Description of test cases follows.

The first line of each test case contains two integers $n$, $m$ ($1 \leq n,m \leq 50$, $m \leq n$) — the lengths of $a$ and $b$ respectively.

The second line of each test case contains a string $a$ of length $n$, consisting only $0$ and $1$.

The third line of each test case contains a string $b$ of length $m$, consisting only $0$ and $1$.


-----Output-----

For each test case, output "YES" if AquaMoon can change $a$ to $b$ by using these options; otherwise, output "NO".

You may print each letter in any case (for example, "YES", "Yes", "yes", "yEs" will all be recognized as a positive answer).


-----Examples-----

Input
10
6 2
001001
11
6 2
110111
01
6 2
000001
11
6 2
111111
01
8 5
10000101
11010
7 4
1010001
1001
8 6
01010010
010010
8 4
01010101
1001
8 4
10101010
0110
7 5
1011100
11100
Output
YES
YES
NO
NO
NO
YES
YES
NO
NO
YES


-----Note-----

In the first test case, you can use Operation 2 four times to make $a$ equals to $b$.

In the second test case, you can use Operation 1 four times to make $a$ equals to $b$.

In the third test case, it can be proved that no matter how we use the operations, it is impossible to make $a$ equal to $b$.

In the fourth test case, it can be proved that no matter how we use the operations, it is impossible to make $a$ equal to $b$.

In the fifth test case, you can use Operation 2 three times to make $a$ become $10101$, so the first element of $a$ equals to the first element of $b$, but it can be proved that no matter how to operate, the second to the fifth elements of $a$ can't be the same as $b$.

Source: codeforces | Difficulty: EASY
Tags: Greedy algorithms

Constructive algorithms


Solutions:
t = int(input())
sol = []
for _ in range(t):
	(m, n) = [int(x) for x in input().split()]
	a = input()
	b = input()
	zero_in = '0' in a[:m - n + 1]
	one_in = '1' in a[:m - n + 1]
	if b[0] == '0':
		if zero_in and a[m - n + 1:] == b[1:]:
			sol.append('YES')
		else:
			sol.append('NO')
	if b[0] == '1':
		if one_in and a[m - n + 1:] == b[1:]:
			sol.append('YES')
		else:
			sol.append('NO')
for s in sol:
	print(s)


q = int(input())
N = []
for i in range(q):
	tttt = 0
	fe = input()
	(n, m) = list(map(int, fe.split()))
	a = input()
	b = input()
	if b[1:] == a[n - m + 1:]:
		o = b[0]
		if o in a[:n - m + 1]:
			tttt = 1
	if tttt:
		N.append('YES')
	else:
		N.append('NO')
for k in N:
	print(k)


import sys
input = sys.stdin.readline
t = int(input())
out = []
for _ in range(t):
	(n, m) = [int(x) for x in input().split()]
	a = input().strip()
	b = input().strip()
	if a[len(a) - len(b) + 1:] == b[1:] and b[0] in a[:len(a) - len(b) + 1]:
		out.append('YES\n')
	else:
		out.append('NO\n')
print(''.join(out))


def firstQuestion():
	(n, m) = map(int, input().split())
	str1 = input()
	str2 = input()
	equal = str1[-m + 1:] == str2[1:]
	if len(str2) == 1 and str2 in str1:
		print('Yes')
	elif equal and str2[0] == '1' and (str1[:-m + 1].count('1') > 0):
		print('YES')
	elif equal and str2[0] == '0' and (str1[:-m + 1].count('0') > 0):
		print('YES')
	else:
		print('NO')

def secondQuestion():
	(n, x) = map(int, input().split())
	arr = list(map(int, input().split()))
	count = 0
	inter = range(-x + arr[0], x + arr[0] + 1)
	for i in range(1, n):
		aa = range(-x + arr[i], x + arr[i] + 1)
		inter = range(max(inter[0], aa[0]), min(inter[-1], aa[-1]) + 1)
		if len(inter) == 0:
			count += 1
			inter = aa
		else:
			continue
	print(count)

def thirdQuestion():
	(n, m) = map(int, input().split())
	arr = list(map(int, input().split()))
	arr.sort()
	diff = [arr[i + 1] - arr[i] for i in range(m - 1)]
	diff.append(n - arr[-1] + arr[0])

def main():
	for _ in range(int(input())):
		firstQuestion()
main()


def Solve():
	for t in range(int(input())):
		(n, m) = map(int, input().split())
		a = input()
		b = input()
		if b[0] in a[:n - m + 1] and a.endswith(b[1:]):
			print('YES')
		else:
			print('NO')
Solve()


for i in range(int(input())):
	(n, m) = map(int, input().split())
	a = input()
	b = input()
	if a[n - m + 1:n] == b[1:m]:
		if a[n - m] == b[0]:
			print('YES')
		elif b[0] in a[0:n - m]:
			print('YES')
		else:
			print('NO')
	else:
		print('NO')


for i in range(int(input())):
	(n, m) = map(int, input().split())
	s = input()
	s1 = input()
	if s == s1:
		print('YES')
	elif s1 == s[-n:]:
		print('YES')
	elif m == 1 and s1 in s:
		print('YES')
	elif m >= 2 and s1[1:] == s[-len(s1[1:]):] and (s1[0] in s[:-len(s1[1:])]):
		print('YES')
	else:
		print('NO')


import math
for _ in range(int(input())):
	(n, m) = [int(i) for i in input().split(' ')]
	(a, b) = (input(), input())
	if b == a[n - m:]:
		print('YES')
	elif b[1:] != a[n - m + 1:]:
		print('NO')
	elif str(int(not bool(int(a[n - m])))) in a[:n - m]:
		print('YES')
	else:
		print('NO')


t = int(input())
for _ in range(t):
	(a, b) = map(int, input().split())
	s = input()
	s1 = input()
	if s1[1:] == s[a - b + 1:] and s1[:1] in s[:a - b + 1]:
		print('YES')
	else:
		print('NO')


cases = int(input())
for i in range(cases):
	(a, b) = input().split()
	if int(a) >= int(b):
		a = input()
		b = input()
	else:
		b = input()
		a = input()
	if b.count('0') <= a.count('0') and b.count('1') <= a.count('1'):
		if a[len(a) - len(b) + 1:len(a)] == b[1:len(b)]:
			print('YES')
		else:
			print('NO')
	else:
		print('NO')


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	a = input()
	b = input()
	c = a[n - m + 1:]
	if c != b[1:]:
		print('NO')
	else:
		b1 = b[0]
		a1 = list(a[:n - m + 1])
		if b1 in a1:
			print('YES')
		else:
			print('NO')


for i in range(int(input())):
	(a, b) = map(int, input().split())
	la = input()
	lb = input()
	if la[a - b + 1:] == lb[1:]:
		if lb[0] in la[:a - b + 1]:
			print('YES')
		else:
			print('NO')
	else:
		print('NO')


for _T in range(int(input())):
	(n, m) = map(int, input().split())
	(a, b) = (input(), input())
	print('YNEOS'[a[n - m + 1:] != b[1:] or b[0] not in a[:n - m + 1]::2])


import sys
input = sys.stdin.readline

def solve():
	(n, m) = map(int, input().split())
	a = input().strip()
	b = input().strip()
	return 'YES' if b[0] in a[:n - m + 1] and a[n - m + 1:] == b[1:] else 'NO'
for _ in range(int(input())):
	print(solve())


def solve():
	(n, k) = map(int, input().split())
	a = input()
	b = input()
	if b[0] in a[:n - k + 1] and a[n - k + 1:] == b[1:]:
		print('YES')
	else:
		print('NO')
for _ in range(int(input())):
	solve()


def solve():
	(n, m) = map(int, input().split())
	a = input().strip()
	b = input().strip()
	a = a[::-1]
	b = b[::-1]
	ok = b[:-1] == a[:m - 1]
	ok = ok and b[-1] in a[m - 1:]
	if ok:
		print('YES')
	else:
		print('NO')
t = int(input())
for _ in range(t):
	solve()


for pratyush in range(int(input())):
	(n, m) = list(map(int, input().split()))
	a = str(input())
	b = str(input())
	c = b[1:]
	d = a[:n - m + 1]
	e = a[n - m + 1:]
	if b[0] in d and c == e:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = input()
	b = input()
	if a[n - m:] == b:
		print('YES')
	else:
		print('YES' if any((x == b[0] for x in a[:n - m + 1])) and a[n - m + 1:] == b[1:] else 'NO')


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	a = input()
	b = input()
	if a[len(a) - len(b) + 1:len(a)] == b[1:] and b[0] in a[:len(a) - len(b) + 1]:
		print('YES')
	else:
		print('NO')


def num():
	c = int(input())
	return c

def stri():
	c = str(input())
	return c

def vector():
	c = list(map(int, input().split()))
	return c

def strvector():
	c = list(map(str, input().split()))
	return c
import math

def isprime(num):
	a = 2
	while a <= math.sqrt(num):
		if num % a < 1:
			return False
		a = a + 1
	return num > 1
t = num()
while t > 0:
	t -= 1
	(a, b) = vector()
	s = stri()
	p = stri()
	(z1, o1) = (s.count('0'), s.count('1'))
	(z2, o2) = (p.count('0'), p.count('1'))
	if a < b or (z2 > 0 and z1 == 0) or (o2 > 0 and o1 == 0):
		print('NO')
	elif s[a - b + 1:] != p[1:]:
		print('NO')
	elif p[0] not in s[0:a - b + 1]:
		print('NO')
	else:
		print('YES')


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = input()
	b = input()
	x = a[:-m + 1]
	if len(x) == 0:
		x = a
		print('YES' if max(x) == b[0] or min(x) == b[0] else 'NO')
	else:
		print('YES' if (max(x) == b[0] or min(x) == b[0]) and b[1:] == a[-m + 1:] else 'NO')


import sys

def solve():
	inp = sys.stdin.readline
	(n, m) = map(int, inp().split())
	a = inp().strip()
	b = inp().strip()
	z = min(n, m)
	if n < m:
		print('NO')
		return
	if a[n - z + 1:] != b[m - z + 1:]:
		print('NO')
		return
	if a[:n - z + 1].find(b[m - z]) == -1:
		print('NO')
	else:
		print('YES')

def main():
	for i in range(int(sys.stdin.readline())):
		solve()
main()


def main():
	for t in range(int(input())):
		(n, m) = map(int, input().split())
		s = input()
		t = input()
		flag = False
		for i in range(n - m + 1):
			if s[i] == t[0]:
				flag = True
		if flag and s[n - m + 1:] == t[1:]:
			print('YES')
		else:
			print('NO')
main()


def main():
	t = int(input())
	for _ in range(t):
		(n, m) = [int(i) for i in input().split()]
		a = input()[::-1]
		b = input()[::-1]
		msg = 'YES' if a[:m - 1] == b[:-1] and b[-1] in a[m - 1:] else 'NO'
		print(msg)
main()


def exe():
	if a[n - m + 1:] != b[1:]:
		return 'NO'
	else:
		s = a[:n - m + 1]
		if b[0] in s:
			return 'YES'
		else:
			return 'NO'
	return
for i in range(int(input())):
	(n, m) = map(int, input().split())
	a = input()
	b = input()
	print(exe())


for _ in range(int(input())):
	(m, n) = map(int, input().split())
	a = str(input())
	b = str(input())
	s1 = a[-len(b):]
	s2 = b[-len(b):]
	if s1 == s2:
		print('YES')
		continue
	elif s1[1:] != s2[1:]:
		print('NO')
		continue
	x1 = s1[0]
	x2 = s2[0]
	if x1 == '0':
		if '1' in a[:len(a) - len(s1)]:
			print('YES')
		else:
			print('NO')
	elif '0' in a[:len(a) - len(s1)]:
		print('YES')
	else:
		print('NO')


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = input()
	b = input()
	t = 0
	for i in range(1, m):
		if a[i + n - m] == b[i]:
			continue
		else:
			t = 1
			break
	if t:
		print('NO')
	else:
		for i in range(n - m + 1):
			if a[i] == b[0]:
				print('YES')
				break
		else:
			print('NO')


x = int(input())

def cal(n, m, a, b):
	if n == m:
		return a == b
	if m == 1:
		return b in a
	if a[n - m + 1:] != b[1:]:
		return False
	return b[0] in a[:n - m + 1]
for jj in range(x):
	(n, m) = [int(i) for i in input().split(' ')]
	a = input()
	b = input()
	if cal(n, m, a, b):
		print('YES')
	else:
		print('NO')


for t in range(int(input())):
	(n, m) = list(map(int, input().split()))
	A = input()
	B = input()
	i = A.find(B[0])
	if i == -1:
		print('NO')
	elif m == 1:
		print('YES')
	else:
		B = B[1:]
		A = A[i + 1:]
		if len(A) >= len(B):
			if A[1 - m:] == B:
				print('YES')
			else:
				print('NO')
		else:
			print('NO')


n = int(input())
for _ in range(n):
	(n, m) = list(map(int, input().split()))
	a = input()
	b = input()
	a1 = a[:n - m + 1]
	a2 = a[n - m + 1:]
	b2 = b[1:]
	if a2 == b2 and b[0] in a1:
		print('YES')
	else:
		print('NO')


for t in range(int(input())):
	(n1, n2) = map(int, input().split())
	ans = 'YES'
	s1 = input()
	m = n1 + 1 - n2
	a = s1[:m]
	b = s1[m:]
	s2 = input()
	if s2[1:] != b:
		ans = 'NO'
	elif a.count(s2[0]) == 0:
		ans = 'NO'
	print(ans)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = input()
	b = input()
	if a[n - m + 1:] == b[1:]:
		c = a[:n - m + 1]
		if b[0] in c:
			print('YES')
		else:
			print('NO')
	else:
		print('NO')


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	a = input()
	b = input()
	if b[0] not in a[:n - m + 1]:
		print('NO')
	elif a[n - m + 1:] != b[1:]:
		print('NO')
	else:
		print('YES')


def func_1(a):
	if a[0] < a[1]:
		return a[0] + a[2:]
	else:
		return a[1:]

def func_2(a):
	if a[0] > a[1]:
		return a[0] + a[2:]
	else:
		return a[1:]
N = int(input())
for i in range(N):
	lens = [int(i) for i in input().split()]
	len_a = lens[0]
	len_b = lens[1]
	a = input()
	b = input()
	a_1 = a[:-len_b]
	a_2 = a[-len_b:]
	if a_2 == b:
		print('YES')
	elif a_2[1:] != b[1:]:
		print('NO')
	elif b[0] in set(list(a_1)):
		print('YES')
	else:
		print('NO')


t = int(input())

def solve():
	(n, m) = map(int, input().split())
	a = input()
	b = input()
	x = n - m
	is_zero = -1
	is_one = -1
	for i in range(x + 1):
		if a[i] == '0':
			is_zero = 1
		else:
			is_one = 1
	if is_zero == 1 and is_one == -1:
		if '0' + a[x + 1:] == b:
			print('YES')
		else:
			print('NO')
	elif is_zero == -1 and is_one == 1:
		if '1' + a[x + 1:] == b:
			print('YES')
		else:
			print('NO')
	elif is_zero == 1 and is_one == 1:
		if '1' + a[x + 1:] == b or '0' + a[x + 1:] == b:
			print('YES')
		else:
			print('NO')
while t:
	solve()
	t -= 1


n = eval(input())
for i in range(n):
	(la, lb) = list(map(int, input().split()))
	a = input()
	b = input()
	flag = 0
	if a[la - lb + 1:] == b[1:]:
		if b[0] in a[:la - lb + 1]:
			flag = 1
	if flag:
		print('YES')
	else:
		print('NO')


t = int(input())

def print_ans(ans):
	for i in ans:
		print(i)
ans = []
for _ in range(t):
	(n, m) = list(map(int, input().split()))
	a = input()
	b = input()
	if a[n - m + 1:] != b[1:]:
		ans.append('NO')
		continue
	if b[0] in a[0:n - m + 1]:
		ans.append('YES')
	else:
		ans.append('NO')
print_ans(ans)


t = int(input())

def canConvert(a, b, n, m):
	if a == b:
		return 'YES'
	if a[-1:-m:-1] != b[-1:-m:-1]:
		return 'NO'
	(flag1, flag2) = (a[n - m], b[0])
	flag = 0
	if flag1 != flag2:
		flag = flag1
	for bit in a[0:n - m]:
		if bit != flag:
			return 'YES'
	return 'NO'
while t:
	(n, m) = list(map(int, input().split()))
	a = input()
	b = input()
	print(canConvert(a, b, n, m))
	t -= 1


t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	a = input()
	b = input()
	d = abs(n - m)
	x = a[0:d + 1]
	y = a[d + 1:]
	z = b[1:]
	if b[0] in x and y == z:
		print('YES')
	else:
		print('NO')


def k(m, n, a, b):
	if b[1:n] == a[m - n + 1:m] and b[0] in a[0:m - n + 1]:
		return True
	return False
for _ in range(int(input())):
	(M, N) = map(int, input().split())
	A = input()
	B = input()
	if k(M, N, A, B):
		print('YES')
	else:
		print('NO')


t = int(input())
for _ in range(t):
	(n, m) = [int(j) for j in input().split()]
	a = input()
	b = input()
	k = m - 1
	if b[1:] == a[n - k:] and b[0] in a[:n - k]:
		print('YES')
	else:
		print('NO')


for i in range(int(input())):
	a = list(map(int, input().split()))
	m = a[0]
	n = a[1]
	a1 = input()
	a2 = input()
	if len(a2) > len(a1):
		print('NO')
	elif a2[0] in a1[0:m - n + 1] and a2[1:] == a1[m - n + 1:]:
		print('YES')
	else:
		print('NO')


for x in range(int(input())):
	(n, m) = map(int, input().split())
	s1 = input()
	s2 = input()
	if n == 1:
		if s1 == s2:
			print('YES')
		else:
			print('NO')
	else:
		s2first = s2[0]
		if s2first in s1[0:n - m + 1] and s1[n - m + 1:n] == s2[1:m]:
			print('YES')
		else:
			print('NO')


from sys import stdin, stdout

def ans():
	(n, m) = map(int, stdin.readline().strip().split())
	a = str(stdin.readline())
	b = str(stdin.readline())
	az = a.count('0')
	ao = a.count('1')
	bz = b.count('0')
	bo = b.count('1')
	if az < bz or ao < bo:
		print('NO')
	else:
		temp = b[1:]
		temp2 = a[n - (m - 1):]
		if temp == temp2:
			print('YES')
		else:
			print('NO')
t = int(stdin.readline())
for _ in range(t):
	ans()


for _ in range(int(input())):
	[n, m] = list(map(int, input().split()))
	A = input()
	B = input()
	if A.count('1') < B.count('1') or A.count('0') < B.count('0'):
		print('NO')
	elif A[n - m + 1:] == B[1:]:
		print('YES')
	else:
		print('NO')


import fileinput
pos = 0
cases = []
curCase = []
done = 0
for line in fileinput.input():
	if pos == 0:
		numCases = int(line.strip())
	else:
		if len(curCase) < 3:
			curCase.append(line.strip())
		if len(curCase) == 3:
			cases.append(curCase)
			curCase = []
			done += 1
			if done == numCases:
				break
	pos += 1
for case in cases:
	a = case[1]
	b = case[2]
	if len(b) == 1:
		x = False
		for i in a:
			if i == b:
				print('YES')
				x = True
				break
		if not x:
			print('NO')
	elif a[len(a) - (len(b) - 1):] != b[1:]:
		print('NO')
	else:
		x = False
		for i in a[0:len(a) - (len(b) - 1)]:
			if i == b[0]:
				print('YES')
				x = True
				break
		if not x:
			print('NO')


number = int(input())
for q in range(number):
	(la, lb) = map(int, input().split())
	a = input()
	b = input()
	if a == b:
		print('YES')
	elif la > 1:
		if la > lb:
			na = a[0:la - lb + 1]
			if a[la - lb + 1:la] == b[1:lb]:
				if na.find('1') >= 0:
					if na.find('0') >= 0:
						print('YES')
					elif b[0] == '1':
						print('YES')
					else:
						print('NO')
				elif b[0] == '0':
					print('YES')
				else:
					print('NO')
			else:
				print('NO')
		elif a == b:
			print('YES')
		else:
			print('NO')
	else:
		print('NO')


def solve():
	(n, m) = map(int, input().split(' '))
	s1 = input()
	s2 = input()
	if s2[1:] == s1[n - m + 1:] and s2[:1] in s1[:n - m + 1]:
		print('YES')
	else:
		print('NO')
t = int(input())
while t:
	t -= 1
	solve()


cases = int(input())
for _ in range(cases):
	(n, m) = map(int, input().split())
	a = input()
	b = input()
	if a == b:
		print('YES')
		continue
	if m == 1 & a.count(b) > 0:
		print('YES')
		continue
	_a = a[n - m + 1:n]
	_b = b[1:m]
	if (_a == _b) & (a[0:n - m + 1].count(b[0]) > 0):
		print('YES')
	else:
		print('NO')


no_test_cases = int(input())
for i in range(no_test_cases):
	(n, m) = list(map(int, input().split(' ')))
	a = input()
	b = input()
	index = 0
	if len(a) == len(b) and a == b:
		print('YES')
	elif len(a) < len(b):
		print('NO')
	elif a[n - m + 1:] == b[1:]:
		if a[n - m] == b[0]:
			print('YES')
		else:
			if b[0] == '1':
				if '1' in a[:n - m]:
					print('YES')
				else:
					print('NO')
			if b[0] == '0':
				if '0' in a[:n - m]:
					print('YES')
				else:
					print('NO')
	else:
		print('NO')


t = int(input())
for i in range(t):
	(len1, len2) = map(int, input().split())
	li1 = list(input().split())
	li2 = list(input().split())
	li1 = li1[0]
	li2 = li2[0]
	if li1[len1 - len2 + 1:] == li2[1:] and li2[0] in li1[0:len1 - len2 + 1]:
		print('YES')
	else:
		print('NO')


for t in range(int(input())):
	(n, m) = list(map(int, input().split()))
	a = input()
	b = input()
	if a[n - m + 1:] == b[1:] and m <= n:
		x = int(min(a[:n - m + 1]))
		y = int(max(a[:n - m + 1]))
		if x ^ y or int(b[0]) == x:
			print('YES')
		else:
			print('NO')
	else:
		print('NO')


for _ in range(int(input())):
	(n, m) = [int(x) for x in input().split()]
	a = input()
	b = input()
	k = n - m
	if a[k + 1:n + 1] == b[1:m + 1]:
		if b[0] in a[0:k + 1]:
			flag = 1
		else:
			flag = 0
	else:
		flag = 0
	if flag == 1:
		print('YES')
	else:
		print('NO')


t = int(input())
while t:
	t -= 1
	(n, m) = map(int, input().split())
	a = input()
	b = input()
	oia = a.count('1')
	zia = a.count('0')
	oib = b.count('1')
	zib = b.count('0')
	if len(b) == 1:
		if b in a:
			print('YES')
		else:
			print('NO')
	elif oia < oib or zia < zib:
		print('NO')
	elif b[1:] != a[1 - len(b):]:
		print('NO')
	else:
		print('YES')


attemps = int(input())
rez_mass = []
for _ in range(attemps):
	(n, m) = map(int, input().split())
	str_a = input()
	str_b = input()
	flag = False
	for i in range(n - m + 1):
		if str_a[i] + str_a[n - m + 1:] == str_b:
			rez_mass.append('YES')
			flag = True
			break
	if flag == False:
		rez_mass.append('NO')
print(*rez_mass, sep='\n')


t = int(input())
for _ in range(t):
	(n, m) = (int(i) for i in input().split())
	(a, b) = (input(), input())
	rem = len(a) - len(b) + 1
	if len(b) > len(a) or b[1:] != a[rem:]:
		print('NO')
	else:
		print('YES' if b[0] in a[:rem] else 'NO')


def solve():
	(n, m) = getInt()
	a = input()
	b = input()
	aln = len(a)
	bln = len(b)
	x = 1 - m
	if aln < bln:
		ans = 'NO'
	elif a == b:
		ans = 'YES'
	elif m == 1:
		if b in a:
			ans = 'YES'
		else:
			ans = 'NO'
	elif a[x:] == b[1:] and b[0] in a[:x]:
		ans = 'YES'
	else:
		ans = 'NO'
	print(ans)

def swap(a, b):
	temp = a
	a = b
	b = temp
	return (a, b)

def getInt():
	return list(map(int, input().split()))
for _ in range(int(input())):
	solve()


t = int(input())
for i in range(0, t):
	(n, m) = map(int, input().split())
	s1 = input()
	s2 = input()
	st = set()
	st1 = set()
	for x in range(0, n - m + 1):
		st.add(s1[x])
	st1.add(s1[n - m + 1:n])
	if s2[0] in st and s2[1:m] in st1:
		print('YES')
	else:
		print('NO')


def main():
	t = int(input())
	for _ in range(t):
		(n, m) = map(int, input().split())
		primary = input()
		secondary = input()
		if primary[n - m:] == secondary:
			print('YES')
		elif primary[n - m + 1:] == secondary[1:] and secondary[0] in primary[:n - m]:
			print('YES')
		else:
			print('NO')
main()


for i in range(int(input())):
	(n, m) = map(int, input().split())
	a = input()
	b = input()
	if b[1:] == a[n - m + 1:]:
		if b[0] == a[n - m]:
			print('YES')
		else:
			flag = 0
			for i in range(n - m):
				if a[i] == a[n - m]:
					pass
				else:
					flag = 1
					break
			if flag == 1:
				print('YES')
			else:
				print('NO')
	else:
		print('NO')


num_inp = lambda : int(input())
arr_inp = lambda : list(map(int, input().split()))
sp_inp = lambda : map(int, input().split())
str_inp = lambda : input()
t = num_inp()
for _ in range(t):
	(n, m) = sp_inp()
	a = input()
	b = input()
	if b[1:] == a[n - m + 1:] and (a.count('0') >= b.count('0') and a.count('1') >= b.count('1')):
		print('YES')
	else:
		print('NO')


for t in range(int(input())):
	(n, m) = tuple(map(int, input().split()))
	a = input()
	b = input()
	if m == 1:
		print('YES' if b in a else 'NO')
	elif b[-m + 1:] == a[-m + 1:] and b[0] in a[:n - m + 1]:
		print('YES')
	else:
		print('NO')