Это сложная версия задачи. В этой версии нет дополнительных ограничений на число \(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\)?
Выходные данные
Для каждого набора входных данных выведите в отдельной строке «YES» если Drahyrt может изменить заклинание \(s\) на \(t\) и «NO» иначе.
Вы можете выводить ответ в любом регистре (например, строки «yEs», «yes», «Yes» и «YES» будут распознаны как положительный ответ).
Примечание
Первый пример разобран в условии.
Во втором примере можно менять соседние буквы местами, так что можем отсортировать строку например с помощью сортировки пузырьком.
Во третьем примере можно показать, что из строки \(s\) невозможно получить строку \(t\) меняя местами буквы на расстоянии \(6\) или \(7\).
В четвертом примере подходит например следующая последовательность преобразований:
- «accio» \(\rightarrow\) «aocic» \(\rightarrow\) «cocia» \(\rightarrow\) «iocca» \(\rightarrow\) «aocci» \(\rightarrow\) «aicco» \(\rightarrow\) «cicao».
В пятом примере можно показать, что невозможно получить из строки \(s\) строку \(t\).
В шестом примере достаточно поменять местами две крайние буквы.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|