C. BA-строка
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Заданы целое число $$$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$$$-ю лексикографически наименьшую.

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

В первой строке записано одно целое число $$$t$$$ ($$$1 \le t \le 2000$$$) — количество наборов входных данных.

Во первой строке каждого набора входных данных записаны три целых числа $$$n$$$, $$$k$$$ and $$$x$$$ ($$$1 \le n \le 2000$$$; $$$0 \le k \le 2000$$$; $$$1 \le x \le 10^{18}$$$). $$$n$$$ — это длина строка $$$s$$$.

Во второй строке каждого набора входных данных содержится строка $$$s$$$. Она состоит из $$$n$$$ символов, каждый из них — либо 'a' (строчная латинская буква), либо '*' (звездочка).

Сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2000$$$. В каждом наборе входных данных $$$x$$$ не превосходит количество различных BA-строк. Строка $$$s$$$ содержит хотя бы один символ 'a'.

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

На каждый набор входных данных выведите одну строку, состоящую из символов 'b' и 'a' (строчные латинские буквы) — $$$x$$$-ю лексикографически наименьшую BA-строку.

Пример
Входные данные
3
2 4 3
a*
4 1 3
a**a
6 3 20
**a***
Выходные данные
abb
abba
babbbbbbbbb
Примечание

В первом наборе входных данных примера BA-строки, упорядоченные лексикографически, следующие:

  1. a
  2. ab
  3. abb
  4. abbb
  5. abbbb

Во втором наборе входных данных примера BA-строки, упорядоченные лексикографически, следующие:

  1. aa
  2. aba
  3. abba

Обратите внимание, что строка «aba» считается только один раз, хотя и есть два способа заменить звездочки на символы 'b' так, чтобы ее получить.