CF1800E2 Unforgivable Curse (hard version)

这是该问题的复杂版本。本版本对 $k$ 的数值没有额外限制。 Wizengamot 的首席巫师曾经抓住了邪恶巫师 Drahyrt，但邪恶巫师已经归来，并想要向首席巫师复仇。因此他从学生 Harry 那里偷走了咒语 $s$。 这个咒语是一个长度为 $n$ 的小写拉丁字母字符串。 Drahyrt 想要用一个不可饶恕的咒语——字符串 $t$——来替换原有的咒语。 Drahyrt 可以利用古老的魔法，无限次地交换咒语中距离为 $k$ 或 $k+1$ 的字母。换句话说，Drahyrt 可以交换咒语 $s$ 中第 $i$ 位和第 $j$ 位的字母，当且仅当 $|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$），表示咒语的长度和 Drahyrt 可以交换的距离 $k$。 第二行给出咒语 $s$，是一个长度为 $n$ 的小写拉丁字母字符串。 第三行给出咒语 $t$，是一个长度为 $n$ 的小写拉丁字母字符串。 保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。注意，所有测试用例中 $k$ 的总和没有限制。

对于每个测试用例，输出一行 "YES"（不区分大小写），如果 Drahyrt 能够将咒语 $s$ 变为 $t$，否则输出 "NO"。 你可以用任意大小写输出答案（例如 "yEs"、"yes"、"Yes" 和 "YES" 都会被认为是正确的肯定答案）。

第一个样例在题面中已经解释。 第二个样例中，我们可以交换相邻的字母，因此可以用冒泡排序等方法对字符串进行排序。 第三个样例中，可以证明无法通过交换距离为 $6$ 或 $7$ 的字母将字符串 $s$ 变为 $t$。 第四个样例中，例如可以按如下变换序列操作： - "accio" $\rightarrow$ "aocic" $\rightarrow$ "cocia" $\rightarrow$ "iocca" $\rightarrow$ "aocci" $\rightarrow$ "aicco" $\rightarrow$ "cicao" 第五个样例中，可以证明无法通过上述操作将 $s$ 变为 $t$。 第六个样例中，只需交换最外侧的两个字母即可。 由 ChatGPT 4.1 翻译