CF1620C.BA-String

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.

给你一个整数 $k$ 和一个字符串 $s$，该字符串仅由字符 'a'（一个小写拉丁字母）和 '*'（一个星号）组成。

每个星号应被替换为若干个（从 $0$ 到 $k$ 个，含端点）小写拉丁字母 'b'。不同的星号可以被替换成不同数量的字母 'b'。

这种替换所得的结果称为一个 BA-字符串。

两个字符串 $a$ 和 $b$ 被认为是不同的，当且仅当它们的长度不同，或存在某个位置 $i$ 使得 $a_i \neq b_i$。

字符串 $a$ 在字典序上小于字符串 $b$，当且仅当满足以下条件之一：

• $a$ 是 $b$ 的真前缀（即 $a$ 是 $b$ 的前缀但 $a \ne b$）；
• 在 $a$ 与 $b$ 首次出现差异的位置上，$a$ 中对应位置的字母在字母表中早于 $b$ 中对应位置的字母。

现在考虑所有互不相同的 BA-字符串，并找出其中字典序第 $x$ 小的字符串。

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'.

第一行包含一个整数 $t$（$1 \le t \le 2000$）—— 表示测试用例的数量。

每个测试用例的第一行包含三个整数 $n$、$k$ 和 $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'。

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

对于每个测试用例，输出一个仅由字符 'b' 和 'a'（小写拉丁字母）组成的字符串——字典序第 $x$ 小的 BA 字符串。

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.

在示例的第一个测试用例中，按字典序排列的 BA 字符串为：

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

在示例的第二个测试用例中，按字典序排列的 BA 字符串为：

1. aa
2. aba
3. abba

注意：字符串 "aba" 仅被计数一次，尽管存在两种方式将星号替换为字符 'b' 以得到该字符串。