← 返回题目列表

Codeforces · 1800/E2

E2. 不可饶恕的诅咒(硬版)

中文机器翻译题面 查看原题

这是问题的复杂版本。此版本对 $$$k$$$ 数量没有额外限制。

威森加摩的首席巫师曾经抓住了邪恶巫师德拉赫特,但邪恶巫师又回来了,想要向首席巫师报仇。所以他从他的学生哈利那里偷了咒语$$$s$$$。

拼写 — 是 $$$n$$$ 长度的小写拉丁字母字符串。

Drahyrt 想要用不可饶恕的诅咒来代替咒语——字符串 $$$t$$$。

Dragirt,使用古老的魔法,可以在咒语中任意多次交换距离 $$$k$$$ 或 $$$k+1$$$ 的字母。换句话说,如果 $$$|i-j|=k$$$ 或 $$$|i-j|=k+1$$$,Drahyrt 可以更改拼写 $$$s$$$ 中位置 $$$i$$$ 和 $$$j$$$ 的字母。

例如,如果 $$$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$$$ 值的总和没有限制。

输出

对于每个测试用例,如果 Drahyrt 可以将拼写 $$$s$$$ 更改为 $$$t$$$,则在单独的行上输出“YES”,否则输出“NO”。

您可以在任何情况下输出答案(例如,“yEs”、“yes”、“Yes”和“YES”行将被识别为肯定答案)。

示例

输入 #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

输出 #1

YES
YES
NO
YES
NO
YES
NO

注意

条件中解释了第一种情况。

在第二种情况下,我们可以交换相邻的字母,因此我们可以使用冒泡排序对字符串进行排序。

在第三种情况下,我们可以证明,从字符串 $$$s$$$ 中,我们无法通过交换距离 $$$6$$$ 或 $$$7$$$ 的字母来得到字符串 $$$t$$$。

例如,在第四种情况下,以下转换顺序是合适的:

- “accio” $$$\rightarrow$$$ “aocic” $$$\rightarrow$$$ “cocia” $$$\rightarrow$$$ “iocca” $$$\rightarrow$$$ “aocci” $$$\rightarrow$$$ “aicco” $$$\rightarrow$$$ “cicao”

在第五种情况下,我们可以证明不可能从字符串$$$t$$$中得到字符串$$$s$$$。

在第六个示例中,交换最外面的两个字母就足够了。