Это сложная версия задачи. Единственное отличие — это ограничения на \(n\) и \(k\). Вы можете делать взломы, только если все версии задачи решены.
У вас есть строка \(s\), и вы можете выполнять над ней два типа операций:
- Удалить последний символ строки.
- Дублировать строку: \(s:=s+s\), где \(+\) обозначает конкатенацию.
Вы можете использовать каждую операцию любое количество раз (возможно, ни одного).
Ваша задача — найти лексикографически наименьшую строку длины ровно \(k\), которую можно получить, выполнив эти операции над строкой \(s\).
Строка \(a\) лексикографически меньше строки \(b\) тогда и только тогда, когда выполняется одно из следующих условий:
- \(a\) является префиксом \(b\), но \(a\ne b\);
- В первой позиции, где \(a\) и \(b\) отличаются, строка \(a\) имеет букву, которая появляется раньше в алфавите, чем соответствующая буква в \(b\).
Выходные данные
Выведите лексикографически наименьшую строку длины \(k\), которая может быть получена путем выполнения операций над строкой \(s\).
Примечание
В первом тесте оптимально сделать одно дублирование: «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».
Примеры
| № | Входные данные | Выходные данные |
|
1
|
8 16
dbcadabc
|
dbcadabcdbcadabc
|
|
2
|
4 5
abcd
|
aaaaa
|