ABACABA Matching
Consider a permutation of lowercase English letters: P = {p[1], p[2], ..., p[26]}. Using P, you can generate the following sequence of strings:
S[1] = p[1]
S[2] = S[1] + p[2] + S[1]
S[3] = S[2] + p[3] + S[2]
...
S[26] = S[25] + p[26] + S[25]
It is easy to show that the length of S[26] is 2^26 - 1 letters. The beginning of S[26] looks like p[1]p[2]p[1]p[3]p[1]p[2]p[1]....
You are given a string T consisting of lowercase English letters. For a fixed permutation P you can obtain S[26] and then substitute some of the letters in T by other letters so that the resulting string becomes a substring of S[26]. Your goal is to minimize the number of letters that you must replace in T by choosing the appropriate permutation P.
Input
The only line contains the string T (1 ≤ |T| ≤ 20000) consisting of lowercase English letters.
Output
On the first line, print the minimal number of letters that should be replaced. On the second line, print the position in string S[26] where the resulting substring starts (indices start from 1). On the third line, print the permutation P.