CF1800E2.Unforgivable Curse (hard version)

This is a complex version of the problem. This version has no additional restrictions on the number $k$.

The chief wizard of the Wizengamot once caught the evil wizard Drahyrt, but the evil wizard has returned and wants revenge on the chief wizard. So he stole spell $s$ from his student Harry.

The spell — is a $n$-length string of lowercase Latin letters.

Drahyrt wants to replace spell with an unforgivable curse — string $t$.

Dragirt, using ancient magic, can swap letters at a distance $k$ or $k+1$ in spell as many times as he wants. In other words, Drahyrt can change letters in positions $i$ and $j$ in spell $s$ if $|i-j|=k$ or $|i-j|=k+1$.

For example, if $k = 3, s = $ "talant" and $t = $ "atltna", Drahyrt can act as follows:

• swap the letters at positions $1$ and $4$ to get spell "aaltnt".
• swap the letters at positions $2$ and $6$ to get spell "atltna".

You are given spells $s$ and $t$. Can Drahyrt change spell $s$ to $t$?

这是一个该问题的复杂版本。本版本对数字 $k$ 没有任何额外限制。

威森加摩首席巫师曾抓获了邪恶巫师德拉赫特，但这位邪恶巫师已卷土重来，并意图向首席巫师复仇。因此，他从首席巫师的学生哈利那里窃取了咒语 $s$。

该咒语是一个长度为 $n$ 的、由小写拉丁字母组成的字符串。

德拉赫特希望将咒语 $s$ 替换为不可饶恕的诅咒——字符串 $t$。

德拉赫特借助远古魔法，可以任意多次地交换咒语中距离为 $k$ 或 $k+1$ 的两个字母。换言之，德拉赫特可以在咒语 $s$ 中交换位置 $i$ 和 $j$ 上的字母，当且仅当 $|i-j|=k$ 或 $|i-j|=k+1$。

例如，若 $k = 3$，$s = $ "talant"，且 $t = $ "atltna"，则德拉赫特可按如下方式操作：

• 交换位置 $1$ 和 $4$ 上的字母，得到咒语 "aaltnt"；
• 交换位置 $2$ 和 $6$ 上的字母，得到咒语 "atltna"。

现给定咒语 $s$ 和 $t$。德拉赫特能否将咒语 $s$ 变为 $t$？

The first line of input gives a single integer $T$ ($1 \le T \le 10^4$) — the number of test cases in the test.

Descriptions of the test cases are follow.

The first line contains two integers $n, k$ ($1 \le n \le 2 \cdot 10^5$, $1 \le k \le 2 \cdot 10^5$) — the length spells and the number $k$ such that Drahyrt can change letters in a spell at a distance $k$ or $k+1$.

The second line gives spell $s$ — a string of length $n$ consisting of lowercase Latin letters.

The third line gives spell $t$ — a string of length $n$ consisting of lowercase Latin letters.

It is guaranteed that the sum of $n$ values over all test cases does not exceed $2 \cdot 10^5$. Note that there is no limit on the sum of $k$ values over all test cases.

输入的第一行包含一个整数 $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$）——分别表示咒语的长度以及 Drahyrt 可以在距离为 $k$ 或 $k+1$ 处修改字母的参数 $k$。

第二行给出咒语 $s$ —— 一个长度为 $n$ 的字符串，仅由小写拉丁字母组成。

第三行给出咒语 $t$ —— 一个长度为 $n$ 的字符串，仅由小写拉丁字母组成。

保证所有测试用例中 $n$ 值的总和不超过 $2 \cdot 10^5$。注意：对所有测试用例而言，$k$ 值的总和没有限制。

For each test case, output on a separate line "YES" if Drahyrt can change spell $s$ to $t$ and "NO" otherwise.

You can output the answer in any case (for example, lines "yEs", "yes", "Yes" and "YES" will be recognized as positive answer).

对于每个测试用例，如果 Drahyrt 可以将咒语 $s$ 变为 $t$，则在单独一行输出 "YES"；否则输出 "NO"。

你可以以任意大小写形式输出答案（例如，"yEs"、"yes"、"Yes" 和 "YES" 均会被识别为肯定回答）。

The first case is explained in the condition.

In the second case, we can swap adjacent letters, so we can sort the string using bubble sorting, for example.

In the third case, we can show that from the string $s$ we cannot get the string $t$ by swapping letters at a distance of $6$ or $7$.

In the fourth case, for example, the following sequence of transformations is appropriate:

• "accio" $\rightarrow$ "aocic" $\rightarrow$ "cocia" $\rightarrow$ "iocca" $\rightarrow$ "aocci" $\rightarrow$ "aicco" $\rightarrow$ "cicao"

In the fifth case, we can show that it is impossible to get the string $s$ from the string $t$.

In the sixth example, it is enough to swap the two outermost letters.

第一种情况已在题目条件中说明。

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

第三种情况下，我们可以证明：从字符串 $s$ 出发，无法通过交换距离为 $6$ 或 $7$ 的字母得到字符串 $t$。

第四种情况下，例如以下变换序列是可行的：

• "accio" $\rightarrow$ "aocic" $\rightarrow$ "cocia" $\rightarrow$ "iocca" $\rightarrow$ "aocci" $\rightarrow$ "aicco" $\rightarrow$ "cicao"

第五种情况下，我们可以证明：无法从字符串 $t$ 得到字符串 $s$。

第六个例子中，只需交换最外侧的两个字母即可。