E. Ahmad and Substrings Syndrome
time limit per test
6 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Ahmad was trying to rob ideas for writing problems, but all the ideas were classic, so he decided to twist a problem just a little bit; it's more fun, right?

You're given a string $$$s$$$ of length $$$n$$$ consisting of lowercase English letters; you have to answer $$$q$$$ queries.

For each query, you will be given a string $$$t$$$ that you can reorder as you wish, and you have to find out if there is a substring in $$$s$$$ that is equal to $$$t$$$ after re-ordering its characters.

Note that you can only re-order characters in the string $$$t$$$.

Input

The first line of the input contains an integer $$$t$$$ $$$(1 \leq t \leq 10^3)$$$ – the number of test cases.

The first line of each test case contains two integers $$$n$$$ and $$$q$$$ $$$(1 \leq n, q \leq 10^5)$$$.

The second line of the test case contains a string $$$s$$$ consisting of $$$n$$$ lower case English letters.

The next $$$q$$$ lines of the test case each contain a string $$$t$$$ $$$(1 \leq t \leq n)$$$ consisting of lower case English letters.

It's guaranteed that the sum of $$$n$$$, $$$q$$$, and $$$|t|$$$ over all test cases doesn't exceed $$$10^5$$$.

Output

For each query, print "YES" if you could find the string $$$t$$$, otherwise print "NO". "Yes", "YeS", "No" or any other casing will be accepted.

Example
Input
2
3 5
aab
aa
ba
aba
bab
bba
4 6
abcd
abcd
dbca
bacd
bdac
cab
acdd
Output
YES
YES
YES
NO
NO
YES
YES
YES
YES
YES
NO