Decrypting the Special Command String

You are given a string S consisting of only lowercase English letters and an integer K. The string is special because among the 26 letters there is one unknown special character which acts as a string command.

For a candidate special character c, whenever you encounter x consecutive occurrences of c in S, it means you should take the following x characters (or all remaining characters if there are fewer than x) as a block T and replace those x consecutive c characters along with the block T by T repeated x times. Formally, if the special character is c and you have

[ \underbrace{c,c,\cdots,c}_{x}, T, ]

then it gets transformed into

[ \underbrace{T,T,\cdots,T}_{x}. ]

Note:

• If there are fewer than x characters following the sequence of c's, take all the remaining characters as T.
• It is guaranteed that immediately following any sequence of exactly x consecutive c's, none of the next x characters is c again. This ensures that the special character is never copied as part of the repeating block.

Since you do not know which letter is the special character, for each possible candidate from a to z you are to determine the Kth character of the decrypted string. If the decrypted string has fewer than K characters, output -1 for that candidate.

Input/Output Formatting Guidelines: See the Input and Output sections below.

inputFormat

The input consists of two lines:

1. The first line contains the string S consisting of only lowercase English letters.
2. The second line contains an integer K (1-indexed) representing the position in the decrypted string.

outputFormat

Output a single line containing 26 tokens separated by a single space. The ith token corresponds to the answer assuming the candidate special character is the ith lowercase letter from a to z. For each candidate, if the decrypted string has at least K characters then output the Kth character; otherwise, output -1.

sample

wwabc
3

a a a a a a a a a a a a a a a a a a a a a a a a a a