Two 0-1 Sequences
Contest: CodeTON Round 2 (Div. 1 + Div. 2, Rated, Prizes!)
Difficulty rating: 800
Tags: constructive algorithms, greedy

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 format:
The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 2\,000$$$) — 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 format:
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).

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

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$$$.

Example 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

Example output:
YES
YES
NO
NO
NO
YES
YES
NO
NO
YES

Editorial:
Considering that whichever the operation you use, the length of $$$a$$$ would decrease $$$1$$$.
So you can only modify the first $$$n-m+1$$$ elements of $$$a$$$, otherwise the length of $$$a$$$ can't be equal to the length of $$$b$$$. That means $$$\{a_{n-m+2},\dots,a_n\}$$$ must equals to $$$\{b_2,\dots,b_m\}$$$.
And about the first element of $$$b$$$:
• if $$$b_1$$$ is $$$0$$$, you can use Operation 1 to make $$$0$$$ and remove elements.
• if $$$b_1$$$ is $$$1$$$, you can use Operation 2 to make $$$1$$$ and remove elements.
So just check the first $$$n-m+1$$$ elements in $$$a$$$ to find if there is anyone that equals to $$$b_1$$$.