E2. Непростительное заклятие (сложная версия)
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это сложная версия задачи. В этой версии нет дополнительных ограничений на число $$$k$$$.

Верховный чародей Визенгамота однажды поймал злого волшебника Drahyrt, но злой волшебник вернулся и хочет отомстить верховному чародею. Поэтому он украл у его ученика Гарри заклинание $$$s$$$.

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

Drahyrt хочет заменить заклинание на непростительное заклятие — строку $$$t$$$.

Drahyrt с помощью древней магии может менять местами буквы на расстоянии $$$k$$$ или $$$k+1$$$ в заклинании сколько угодно раз. Другими словами, Drahyrt может поменять буквы на позициях $$$i$$$ и $$$j$$$ в заклинании $$$s$$$ если $$$|i-j|=k$$$ или $$$|i-j|=k+1$$$.

Например, если $$$k = 3, s = $$$ «talant» и $$$t = $$$ «atltna», то Drahyrt может действовать следующим образом:

  • поменять местами буквы на позициях $$$1$$$ и $$$4$$$, получив заклинание «aaltnt».
  • поменять местами буквы на позициях $$$2$$$ и $$$6$$$, получив заклинание «atltna».

Вам даны заклинания $$$s$$$ и $$$t$$$. Может ли Drahyrt изменить заклинание $$$s$$$ на $$$t$$$?

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

В первой строке входных данных дано единственное целое число $$$T$$$ ($$$1 \le T \le 10^4$$$) — количество наборов входных данных в тесте.

Далее следуют описания наборов входных данных.

В первой строке содержится два целых числа $$$n, k$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$1 \le k \le 2 \cdot 10^5$$$) — длина заклинаний и число $$$k$$$ такое, что Drahyrt может менять буквы в заклинании на расстоянии $$$k$$$ или $$$k+1$$$.

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

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

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

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

Для каждого набора входных данных выведите в отдельной строке «YES» если Drahyrt может изменить заклинание $$$s$$$ на $$$t$$$ и «NO» иначе.

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

Пример
Входные данные
7
6 3
talant
atltna
7 1
abacaba
aaaabbc
12 6
abracadabraa
avadakedavra
5 3
accio
cicao
5 4
lumos
molus
4 3
uwjt
twju
4 3
kvpx
vxpk
Выходные данные
YES
YES
NO
YES
NO
YES
NO
Примечание

Первый пример разобран в условии.

Во втором примере можно менять соседние буквы местами, так что можем отсортировать строку например с помощью сортировки пузырьком.

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

В четвертом примере подходит например следующая последовательность преобразований:

  • «accio» $$$\rightarrow$$$ «aocic» $$$\rightarrow$$$ «cocia» $$$\rightarrow$$$ «iocca» $$$\rightarrow$$$ «aocci» $$$\rightarrow$$$ «aicco» $$$\rightarrow$$$ «cicao».

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

В шестом примере достаточно поменять местами две крайние буквы.