B'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: 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: The first line contains two integers n , k ( 1 <= q n, k <= q 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 . 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". '...