题目内容

塔子哥是一名计算机科学家，他正在研究一种特殊的字符串。这个字符串由小写字母 ‘x’ 和特殊字符 ‘*’ 构成。现在，他想要将这个字符串中的每个字符 ‘*’ 替换成 $0$ 到 $m$ 个小写字母 ‘y’ ，并将替换后的字符串称为 "xy字符串" 。对于原始字符串 $s$ ，可以用不同替换方式可以得到多种不相同的 "xy字符串" ，塔子哥现在想知道第 $n$ 小的 "xy字符串" ，但是他现在忙于研究 "xy字符串” 的其他性质，你帮他解决这个问题吗？

假定有两个 "xy字符串" 分别为 $s1$ 、 $s2$ ，这两个 "xy字符串" 满足以下特性：

1. 如果 $s1$ 和 $s2$ 的长度不同，或者下标对应的字母不同，则认为 $s1$ 和 $s2$ 不相同
2. 如果 $s1$ 要小于 $s2$ 的话，需要满足任意条件之一
   • $s1$ 是 $s2$ 的前缀且 $s1$ 与 $s2$ 不相同
   • 比较 $s1$ 和 $s2$ ，从左往右第个字母不同， 且 $s1$ 的字母小于 $s2$ 的字母

输入描述

第一行输入一个数字 $T$ ( $1\le T \le 2500$ ) ，表示有 $T$ 组测试用例。对于每一组用例：

第一行分别有 $3$ 个数字， $l$ ( $1\le 1 \le 2500$ ) ， $m$ ( $0\le m \le 2500$ )， $n$ ( $1\le n \le 10^{18}$ )。

第二行有一个字符串 $s$ 由 $l$ 个字符构成，字符串由小写字母 'x' 和特殊字符 ‘*’ 构成。

输出描述

对于每组测试用例，输出一行字符串，表示第 $n$ 小的 "xy字符串"

样例

样例一：

输入

2
4 1 3
x**x
2 4 3
x*

输出

xyyx
xyy

备注

$T$ 组测试用例的字符串 $l$ 加起来不会超过 $2500$ 。对于每组测试用例，可以保证 $n$ 不会超过 不相同的 "xy字符串" 的数量