CF1620C BA-String

给定一个整数 $k$ 和一个只包含小写拉丁字母 'a' 和星号 '*' 的字符串 $s$。 每个星号都应被替换为若干（从 $0$ 到 $k$，包括 $0$ 和 $k$）个小写拉丁字母 'b'。不同的星号可以被替换为不同数量的字母 'b'。 替换后的结果称为 BA-字符串。 如果两个字符串 $a$ 和 $b$ 长度不同，或者存在某个位置 $i$ 满足 $a_i \neq b_i$，则认为这两个字符串不同。 如果满足以下任一条件，则字符串 $a$ 的字典序小于字符串 $b$： - $a$ 是 $b$ 的前缀，且 $a \ne b$； - 在第一个不同的位置，$a$ 的字母在字母表中比 $b$ 的对应字母更靠前。 现在，考虑所有不同的 BA-字符串，找出其中字典序第 $x$ 小的字符串。

第一行包含一个整数 $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$ 的长度。 每个测试用例的第二行是一个长度为 $n$ 的字符串 $s$，只包含字符 'a' 或 '*'。 所有测试用例中 $n$ 的总和不超过 $2000$。对于每个测试用例，$x$ 不会超过不同 BA-字符串的总数。字符串 $s$ 至少包含一个字符 'a'。

对于每个测试用例，输出一行，仅包含小写字母 'a' 和 'b' 的字符串，即字典序第 $x$ 小的 BA-字符串。

在第一个样例中，按字典序排列的 BA-字符串为： 1. a 2. ab 3. abb 4. abbb 5. abbbb 在第二个样例中，按字典序排列的 BA-字符串为： 1. aa 2. aba 3. abba 注意，字符串 "aba" 只计数一次，尽管有两种方式用 'b' 替换星号得到它。 由 ChatGPT 4.1 翻译