Задана строка \(t\) длины \(n\), состоящая из строчных букв латинского алфавита, и целое число \(k\).
Определим подстроку какой-либо строки \(s\) с индексами от \(l\) до \(r\) как \(s[l \dots r]\).
Ваша задача — составить такую строку \(s\) минимальной возможной длины, что в ней существует ровно \(k\) позиций \(i\) таких, что \(s[i \dots i + n - 1] = t\). Другими словами, ваша задача — составить такую строку \(s\) минимальной возможной длины, что ровно \(k\) подстрок строки \(s\) равны \(t\).
Гарантируется, что существует один возможный ответ.
Выходные данные
Выведите такую строку \(s\) минимально возможной длины, что ровно \(k\) подстрок строки \(s\) равны \(t\).
Гарантируется, что существует один возможный ответ.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 4
aba
|
ababababa
|
|
2
|
3 2
cat
|
catcat
|