11471147 SUSTech Online Judge
Problem 1147 --KMP [Easy]

1147: KMP [Easy]

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 15  Solved: 10
[Submit][Status][Web Board]

Description

Hong has two strings S and T, he wants to know if S is a substring of T. If the given string S is a substring of T, print "YES", otherwise print "NO".

Input

The first line will be an integer T (1≤T≤100), which is the number of test cases.  

For each test data:

The first line contains two integers n and m (1≤n< m≤210^5) — the length of the string S and the length of the string T, respectively.

The second line contains string s of length n, which consists only of lowercase letters.

The third line contains string t of length m, which consists only of lowercase letters.

Output

For each test cases, print "YES" (without quotes), if string S is a substring of T. Otherwise print "NO" (without quotes).

Sample Input

1
2 3
aa
aaa

Sample Output

YES

HINT

Source

[Submit][Status]