Sofia 有一个长度为 $$$n$$$ 的字符串 $$$s$$$,仅由小写英文字母组成。她可以使用该字符串执行以下类型的操作。
1. 选择索引 $$$1 \le i \le |s|$$$ 并从字符串中删除字符 $$$s_i$$$。
2. 选择一对索引 $$$(l, r)$$$ ($$$1 \le l \le r \le |s|$$$) 并按字母顺序对子字符串 $$$s_{l} s_{l+1} \ldots s_r$$$ 进行排序。
Sofia 希望在如上所述对字符串 $$$s$$$ 执行零次或多次操作后获取长度为 $$$m$$$ 的字符串 $$$t$$$。请判断是否可以。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10\,000$$$) — 测试用例的数量。
每个测试用例的第一行包含两个整数 $$$n$$$、$$$m$$$ ($$$1\leq m \leq n \leq 2\cdot 10^5$$$) — 分别是字符串 $$$s$$$ 和 $$$t$$$ 的长度。
每个测试用例的第二行包含长度为$$$n$$$的字符串$$$s$$$,仅由小写英文字母组成。
每个测试用例的第三行包含长度为$$$m$$$的字符串$$$t$$$,仅由小写英文字母组成。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2\cdot 10^5$$$。
输出
对于每个测试用例,如果 Sofia 可以使用上述操作从 $$$s$$$ 获取字符串 $$$t$$$,则输出“YES”。否则,输出“NO”。
您可以在任何情况下输出答案(大写或小写)。例如,字符串“yEs”、“yes”、“Yes”和“YES”将被识别为肯定响应。
示例
输入 #1
8 5 5 sofia afios 3 2 cba bc 5 1 sofia e 15 7 anavolimilovana aamanan 26 4 abcdefghijklmnopqrstuvwxyz nope 26 4 zyxwvutsrqponmlkjihgfedcba nope 7 3 apricot cat 3 3 cba acb
输出 #1
YES YES NO YES NO YES NO YES
注意
在第一个测试用例中,Sofia 可以执行以下操作:
1. $$$l=1$$$ 和 $$$r=5$$$ 的第二类运算:字符串 $$$s$$$ 之后变为 $$$\mathtt{afios}$$$。
在第二个测试用例中,Sofia 可以执行以下操作:
1. $$$l=1$$$ 和 $$$r=2$$$ 的第二种运算:字符串 $$$s$$$ 之后变为 $$$\mathtt{bca}$$$;
2. $$$i=3$$$ 的第一类运算:字符串$$$s$$$ 后面变成$$$\mathtt{bc}$$$。
在第三个测试用例中,可以证明使用提供的操作不可能从 $$$s$$$ 获得 $$$t$$$。