Изменения рейтингов за последние раунды временно удалены. Скоро они будут возвращены. ×

E. София и строки
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Софии есть строка $$$s$$$ длины $$$n$$$, состоящая из строчных латинских букв. Она может выполнять следующие операции с этой строкой.

  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$$$ в алфавитном порядке.
Здесь $$$|s|$$$ обозначает текущую длину строки $$$s$$$. В частности, $$$|s| = n$$$ перед первой операцией. Например, если $$$s = \mathtt{sofia}$$$, то, применив операцию первого типа с $$$i=4$$$, мы сделаем строку $$$s$$$ равной $$$\mathtt{sofa}$$$. Применив после этого операцию второго типа с $$$(l, r) = (2, 4)$$$, получим строку $$$s$$$, равную $$$\mathtt{safo}$$$.

София хочет получить строку $$$t$$$ длины $$$m$$$ из строки $$$s$$$, используя операции, описанные выше, несколько раз (возможно, ноль). Определите, возможно ли это.

Входные данные

В первой строке задано одно целое число $$$t$$$ ($$$1 \leq t \leq 10\,000$$$) — количество наборов входных данных. Далее следуют описания этих наборов.

В первой строке дано два целых числа $$$n$$$ и $$$m$$$ ($$$1\leq m \leq n \leq 2\cdot 10^5$$$) — длины строк $$$s$$$ и $$$t$$$ соответственно.

Во второй строке дана строка $$$s$$$ длины $$$n$$$, состоящая из строчных латинских букв.

Во третьей строке дана строка $$$t$$$ длины $$$m$$$, состоящая из строчных латинских букв.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2\cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите «YES», если София может получить строку $$$t$$$ из строки $$$s$$$, используя операции из условия. Иначе, выведите «NO».

Вы можете выводить каждую букву в любом регистре (строчную или заглавную). Например, строки «yEs», «yes», «Yes» и «YES» будут приняты как положительный ответ.

Пример
Входные данные
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
Примечание

В первом наборе входных данных София может сделать следующую операцию:

  1. операция второго типа с $$$l=1$$$ и $$$r=5$$$: строка $$$s$$$ станет равной $$$\mathtt{afios}$$$ после операции.

Во втором наборе входных данных София может сделать следующие операции:

  1. операция второго типа с $$$l=1$$$ и $$$r=2$$$: строка $$$s$$$ станет равной $$$\mathtt{bca}$$$ после операции;
  2. операция первого типа с $$$i=3$$$: строка $$$s$$$ станет равной $$$\mathtt{bc}$$$ после операции.

В третьем наборе входных данных можно показать, что невозможно получить строку $$$t$$$ из строки $$$s$$$ используя операции из условия.