CF1537E2.Erase and Extend (Hard Version)

This is the hard version of the problem. The only difference is the constraints on $n$ and $k$. You can make hacks only if all versions of the problem are solved.

You have a string $s$, and you can do two types of operations on it:

• Delete the last character of the string.
• Duplicate the string: $s:=s+s$, where $+$ denotes concatenation.

You can use each operation any number of times (possibly none).

Your task is to find the lexicographically smallest string of length exactly $k$ that can be obtained by doing these operations on string $s$.

A string $a$ is lexicographically smaller than a string $b$ if and only if one of the following holds:

• $a$ is a prefix of $b$, but $a\ne b$;
• In the first position where $a$ and $b$ differ, the string $a$ has a letter that appears earlier in the alphabet than the corresponding letter in $b$.

这是该问题的困难版本。唯一区别在于 $n$ 和 $k$ 的约束条件。仅当该问题的所有版本均已被解决时，你才可以进行 hack。

你有一个字符串 $s$，可以对其执行以下两种操作：

• 删除字符串的最后一个字符；
• 复制字符串：$s:=s+s$，其中 $+$ 表示字符串连接。

每种操作均可使用任意多次（也可以一次都不使用）。

你的任务是：通过对字符串 $s$ 执行上述操作，得到长度恰好为 $k$ 的字典序最小的字符串。

字符串 $a$ 的字典序小于字符串 $b$，当且仅当满足以下任一条件：

• $a$ 是 $b$ 的真前缀（即 $a$ 是 $b$ 的前缀且 $a \ne b$）；
• 在 $a$ 与 $b$ 首次出现不同字符的位置上，$a$ 中该位置的字母在字母表中早于 $b$ 中对应位置的字母。

The first line contains two integers $n$, $k$ ($1 \leq n, k \leq 5\cdot 10^5$) — the length of the original string $s$ and the length of the desired string.

The second line contains the string $s$, consisting of $n$ lowercase English letters.

第一行包含两个整数 $n$、$k$（$1 \leq n, k \leq 5\cdot 10^5$）——分别为原字符串 $s$ 的长度和目标字符串的长度。

第二行包含字符串 $s$，由 $n$ 个小写英文字母组成。

Print the lexicographically smallest string of length $k$ that can be obtained by doing the operations on string $s$.

打印通过对字符串 $s$ 执行操作所能得到的长度为 $k$ 的字典序最小的字符串。

In the first test, it is optimal to make one duplication: "dbcadabc" $\to$ "dbcadabcdbcadabc".

In the second test it is optimal to delete the last $3$ characters, then duplicate the string $3$ times, then delete the last $3$ characters to make the string have length $k$.

"abcd" $\to$ "abc" $\to$ "ab" $\to$ "a" $\to$ "aa" $\to$ "aaaa" $\to$ "aaaaaaaa" $\to$ "aaaaaaa" $\to$ "aaaaaa" $\to$ "aaaaa".

在第一个测试用例中，最优操作是进行一次复制操作：“dbcadabc” $\to$ “dbcadabcdbcadabc”。

在第二个测试用例中，最优操作是：先删除最后 $3$ 个字符，然后将字符串复制 $3$ 次，再删除最后 $3$ 个字符，使字符串长度恰好为 $k$。

“abcd” $\to$ “abc” $\to$ “ab” $\to$ “a” $\to$ “aa” $\to$ “aaaa” $\to$ “aaaaaaaa” $\to$ “aaaaaaa” $\to$ “aaaaaa” $\to$ “aaaaa”。