codeforces#P1537E2. Erase and Extend (Hard Version)

    ID: 32172 远端评测题 2000ms 256MiB 尝试: 0 已通过: 0 难度: 8 上传者: 标签>binary searchdata structuresgreedyhashingstring suffix structuresstringstwo pointers*2200

Erase and Extend (Hard Version)

Description

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$.

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.

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

Input

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.

Output

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

Samples

8 16
dbcadabc
dbcadabcdbcadabc
4 5
abcd
aaaaa

Note

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".