BA-String
Contest: Educational Codeforces Round 119 (Rated for Div. 2)
Difficulty rating: 1800
Tags: brute force, dp, greedy, implementation, math

You are given an integer $$$k$$$ and a string $$$s$$$ that consists only of characters 'a' (a lowercase Latin letter) and '*' (an asterisk).

Each asterisk should be replaced with several (from $$$0$$$ to $$$k$$$ inclusive) lowercase Latin letters 'b'. Different asterisk can be replaced with different counts of letter 'b'.

The result of the replacement is called a BA-string.

Two strings $$$a$$$ and $$$b$$$ are different if they either have different lengths or there exists such a position $$$i$$$ that $$$a_i \neq b_i$$$.

A string $$$a$$$ is lexicographically smaller than a string $$$b$$$ if and only if one of the following holds:

- $$$a$$$ is a prefix of $$$b$$$, but $$$a \ne b$$$;
- in the first position where $$$a$$$ and $$$b$$$ differ, the string $$$a$$$ has a letter that appears earlier in the alphabet than the corresponding letter in $$$b$$$.

Now consider all different BA-strings and find the $$$x$$$-th lexicographically smallest of them.

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 2000$$$) — the number of testcases.

The first line of each testcase contains three integers $$$n$$$, $$$k$$$ and $$$x$$$ ($$$1 \le n \le 2000$$$; $$$0 \le k \le 2000$$$; $$$1 \le x \le 10^{18}$$$). $$$n$$$ is the length of string $$$s$$$.

The second line of each testcase is a string $$$s$$$. It consists of $$$n$$$ characters, each of them is either 'a' (a lowercase Latin letter) or '*' (an asterisk).

The sum of $$$n$$$ over all testcases doesn't exceed $$$2000$$$. For each testcase $$$x$$$ doesn't exceed the total number of different BA-strings. String $$$s$$$ contains at least one character 'a'.

Output format:
For each testcase, print a single string, consisting only of characters 'b' and 'a' (lowercase Latin letters) — the $$$x$$$-th lexicographically smallest BA-string.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first testcase of the example, BA-strings ordered lexicographically are:

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

In the second testcase of the example, BA-strings ordered lexicographically are:

1. aa
2. aba
3. abba

Note that string "aba" is only counted once, even though there are two ways to replace asterisks with characters 'b' to get it.

Example input:
3
2 4 3
a*
4 1 3
a**a
6 3 20
**a***

Example output:
abb
abba
babbbbbbbbb

Editorial:
Find all segments of asterisks in the string. Let there be $$$t$$$ of them, and the number of asterisks in them be $$$c_1, c_2, \dots, c_t$$$. That tells us that the $$$i$$$-th segment of asterisks can be replaced with at most $$$c_i \cdot k$$$ letters 'b'.
Notice that we can compare two strings lexicographically using just the number of letters 'b' that replace each of $$$t$$$ segments of asterisks. Let that sequence for some string $$$a$$$ be $$$A_1, A_2, \dots, A_t$$$ and that sequence for some string $$$b$$$ be $$$B_1, B_2, \dots, B_t$$$. Then $$$a < b$$$ if and only if $$$A < B$$$. That is, there exists such position $$$i$$$ that $$$A_i < B_i$$$. The proof is trivial.
So we can actually look at the sequence $$$A_1, A_2, \dots, A_t$$$ as some kind of number in a mixed base. The lowest "digit" $$$A_t$$$ can be of one of $$$c_t \cdot k + 1$$$ values (from $$$0$$$ to $$$c_t \cdot k$$$). The second lowest — one of $$$c_{t-1} \cdot k + 1$$$. And so on. Then, comparison of two strings is the same as comparison of these two mixed base numbers.
Thus, the task is to convert number $$$x-1$$$ to this mixed base. Turns out, it's not that hard. In base $$$10$$$, for example, the lowest digit can be determined as the remainder of the number of dividing by $$$10$$$. Here it will be the remainder of dividing by $$$c_t \cdot k + 1$$$. After that, divide and floor the number and proceed to the next "digit".
After $$$t$$$ steps are done, the "digits" of that mixed base number tell exactly how many letters 'b' should replace each segment of asterisks.
Overall complexity: $$$O(n)$$$ per testcase to recover the string, $$$O(nk)$$$ to print it.