Заданы целое число \(k\) и строка \(s\), которая состоит только из символов 'a' (строчная латинская буква) и '*' (звездочка).
Каждая звездочка должна быть заменена на несколько (от \(0\) до \(k\) включительно) строчных латинских букв 'b'. Разные звездочки можно заменить на разные количества букв 'b'.
Результат замены называется BA-строкой.
Две строки \(a\) и \(b\) различные, если у них либо различная длина, либо существует такая позиция \(i\), что \(a_i \neq b_i\).
Строка \(a\) лексикографически меньше строки \(b\), если и только если выполняется один из следующих пунктов:
- \(a\) — префикс \(b\), но \(a \ne b\);
- в первой позиции, где \(a\) и \(b\) различны, в строке \(a\) находится буква, которая встречается в алфавите раньше, чем соответствующая буква в \(b\).
Рассмотрите все различные BA-строки и найдите из них \(x\)-ю лексикографически наименьшую.
Выходные данные
На каждый набор входных данных выведите одну строку, состоящую из символов 'b' и 'a' (строчные латинские буквы) — \(x\)-ю лексикографически наименьшую BA-строку.
Примечание
В первом наборе входных данных примера BA-строки, упорядоченные лексикографически, следующие:
- a
- ab
- abb
- abbb
- abbbb
Во втором наборе входных данных примера BA-строки, упорядоченные лексикографически, следующие:
- aa
- aba
- abba
Обратите внимание, что строка «aba» считается только один раз, хотя и есть два способа заменить звездочки на символы 'b' так, чтобы ее получить.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
2 4 3
a*
4 1 3
a**a
6 3 20
**a***
|
abb
abba
babbbbbbbbb
|