#JMFESTEST020. T3 获取字符串

T3 获取字符串

T3 获取字符串 (obtain, 2s/256M)

Sofia 有一个初始长度为 nn 的字符串 SS,只包含小写英文字母。她可以对这个字符串进行以下类型的操作:

  • 选择一个下标 i (1iS)i\ (1 \le i \le |S|),并删除 SiS_iS|S| 表示字符串的长度。
  • 选择两个整数 l,rl, r,要求 (1lrS)(1 \le l \le r \le |S|),之后对 Sl,Sl+1,,SrS_l, S_{l+1}, \ldots, S_{r} 按照从小到大进行排序。例如,对字符串 sofia 选择 l=2,r=4l=2, r=4 的话,变化之后的字符串为 sfioa

Sofia 想知道:对字符串 SS 进行若干次上述两种操作之后,是否有可能得到另一个长度为 mm 的字符串 TT

输入格式

第一行包含一个整数 tt,表示数据组数。

每组数据的第一行包含两个整数 n,mn, m,分别表示字符串 SSTT 的长度。第二行输入字符串 SS,第三行输入字符串 TT

输出格式

对于每组数据,如果 Sofia 能得到字符串 TT,输出一行 YES;否则的,输出一行 NO

样例输入

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

样例输出

YES
YES
NO
YES
NO
YES
NO
YES

样例解释

第一组数据,选择 l=1,r=5l=1,r=5 之后就可以得到。

第二组数据,先选择 l=1,r=2l=1,r=2,然后再删除第三个字符即可。

数据范围

  • 对于 30% 的数据,1mn8,n201 \le m \le n \le 8, \sum n \le 20
  • 对于 100% 的数据,1mn2105,n5105,1t1041 \le m \le n \le 2\cdot 10^5, \sum n \le 5\cdot 10^5, 1 \le t \le 10^4。输入的字符串仅包含小写英文字母。