← 返回题目列表

Codeforces · 1620/C

C. BA 字符串

中文机器翻译题面 查看原题

给定一个整数 $$$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$$$ 和 $$$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 字符串。

示例

输入 #1

3
2 4 3
a*
4 1 3
a**a
6 3 20
**a***

输出 #1

abb
abba
babbbbbbbbb

注意

在示例的第一个测试用例中,按字典顺序排序的 BA 字符串为:

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

在示例的第二个测试用例中,按字典顺序排序的 BA 字符串为:

1.aa
2.aba
3.阿爸

请注意,字符串“aba”仅计算一次,尽管有两种方法可以用字符“b”替换星号来获取它。