Description

The KMP algorithm describes how we can derive failure function given a pattern.  Reversely, here we want to design an algorithm that can

1. Produce the first valid pattern (in dictionary order) that satisfies a given KMP's failure function, if such a pattern exist
2. Report an error if such a pattern does not exist

By first valid pattern in dictionary order, we mean that, for example, although  abbb, abbc, abcb, abcc, abcd ... all satisfy the failure function 0000, we want the program to pick the first one, abbb, instead of others.

Input

Input consists of multiple lines.  Each line is a failure function consisting of many integers.

Integers are separated by spaces.

The failure funcitons given in the input are 0-based (the first number is 0 in a failure funciton), while in some textbooks, failure functions are -1-based (the first number is -1).  If you prefer the latter one, please subtract each number by 1. 

Output

For each input failure function, please do the follows:

1. Output the failure function again
2. Print the first valid pattern (in dictionary order) that satisfies the failure function if available.
   Please insert single space between every two characters for better readibility.
3. Print a lowercase x if the patter is unavailable (i.e, the failure function is not valid)
4. Print "-----" and a newline character as a separator line

 

Sample Input  Download

Sample Output  Download

Tags

Add Tag

Discuss