给定一个整数 $$$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”替换星号来获取它。