Erase and Extend (Hard Version)

题意翻译

你有一个字符串 $s$，你可以进行两种操作。 - 删去字符串的最后一个字符。 - 将 $s$ 变为 $s+s$，$+$ 表示字符串连接，也就是复制一次字符串。 你可以随意的进行操作，也可以不进行操作。 你需要找到 $s$ 进行操作后获得的所有长度为 $k$ 的字符串中**字典序最小**的字符串。

题目描述

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

输入输出样例

输入样例 #1

8 16
dbcadabc

输出样例 #1

dbcadabcdbcadabc

输入样例 #2

4 5
abcd

输出样例 #2

aaaaa

说明

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