小X接到了一个破译任务。他收到了一个仅包含小写英文字母字符串。
这个字符串十分特殊:在26个英文字母中,潜藏着一个特殊字符,这个字符的实际意义是一个字符串指令!
x个特殊字符相连的含义是:把后面x个字符组成的字符串变成它本身复制x遍的结果。例如,若特殊字符是”w”,那么字符串”wwabc”的破译结果就是”ababc”。
特殊的,若后面字符总数已经不足x个,则字符串改为由后面所有字符组成。例如,若特殊字符是”w”,那么字符串”wwwwabc”的破译结果就是”abcabcabcabc”。
字符串保证连续x个c字符后的x个字符都不会是c字符。例如”aaaba”不会是你要破解的字符串。(也就是特殊字符是不可能被复制的)
但是小X还不知道特殊字符是什么。所以他想问问你,对于每一种可能的特殊字符,破译结果的第K位是什么。
第一行两个整数n,K,分别表示字符串的长度和询问第K位。
第二行一个字符串。
输出一行包含一个长度为26字符串,分别表示若特殊字符是”a”,”b”,...,”z”那么破译结果的第K位是什么。
若破译结果长度小于K,输出”*”。
10 10
aaaabbbccd
bd**dddddddddddddddddddddd
样例解释
若特殊字符是”a”,破译结果是”bbbcbbbcbbbcbbbccd”
若特殊字符是”b”,破译结果是”aaaaccdccdccd”
若特殊字符是”c”,破译结果是”aaaabbbdd”
若特殊字符是”d”,破译结果是”aaaabbbcc”
若特殊字符是其他,破译结果是”aaaabbbccd”
数据范围
本题共有10个测试点,每个测试点10分。
对于测试点1-4 :n<=500,K<=500
对于测试点5-7 :n<=10^6,K<=10^6
对于测试点8-10:n<=10^6,K<=10^9