这是问题的复杂版本。此版本对 $$$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$$$。
在第六个示例中,交换最外面的两个字母就足够了。