E2. Удаляй и удлиняй (сложная версия)
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это сложная версия задачи. Единственное отличие — это ограничения на $$$n$$$ и $$$k$$$. Вы можете делать взломы, только если все версии задачи решены.

У вас есть строка $$$s$$$, и вы можете выполнять над ней два типа операций:

  • Удалить последний символ строки.
  • Дублировать строку: $$$s:=s+s$$$, где $$$+$$$ обозначает конкатенацию.

Вы можете использовать каждую операцию любое количество раз (возможно, ни одного).

Ваша задача — найти лексикографически наименьшую строку длины ровно $$$k$$$, которую можно получить, выполнив эти операции над строкой $$$s$$$.

Строка $$$a$$$ лексикографически меньше строки $$$b$$$ тогда и только тогда, когда выполняется одно из следующих условий:

  • $$$a$$$ является префиксом $$$b$$$, но $$$a\ne b$$$;
  • В первой позиции, где $$$a$$$ и $$$b$$$ отличаются, строка $$$a$$$ имеет букву, которая появляется раньше в алфавите, чем соответствующая буква в $$$b$$$.
Входные данные

Первая строка содержит два целых числа $$$n$$$, $$$k$$$ ($$$1 \leq n, k \leq 5\cdot 10^5$$$) — длину исходной строки $$$s$$$ и длину желаемой строки.

Вторая строка содержит строку $$$s$$$, состоящую из $$$n$$$ строчных английских букв.

Выходные данные

Выведите лексикографически наименьшую строку длины $$$k$$$, которая может быть получена путем выполнения операций над строкой $$$s$$$.

Примеры
Входные данные
8 16
dbcadabc
Выходные данные
dbcadabcdbcadabc
Входные данные
4 5
abcd
Выходные данные
aaaaa
Примечание

В первом тесте оптимально сделать одно дублирование: «dbcadabc» $$$\to$$$ «dbcadabcdbcadabc».

Во втором тесте оптимально удалить последние $$$3$$$ символа, затем продублировать строку $$$3$$$ раза, затем удалить последние $$$3$$$ символов, чтобы строка имела длину $$$k$$$.

«abcd» $$$\to$$$ «abc» $$$\to$$$ «ab» $$$\to$$$ «a» $$$\to$$$ «aa» $$$\to$$$ «aaaa» $$$\to$$$ «aaaa» $$$\to$$$ «aaaa» $$$\to$$$ «aaaa» $$$\to$$$ «aaaa».