eolymp
bolt
Try our new interface for solving problems
Problems

ABACABA Matching

ABACABA Matching

Time limit 1 second
Memory limit 128 MiB

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 data

The only line contains the string T (1 ≤ |T| ≤ 20000) consisting of lowercase English letters.

Output data

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.

Examples

Input example #1
baca
Output example #1
0
2
abcdefghijklmnopqrstuvwxyz
Input example #2
bcdbaaac
Output example #2
3
2
cbdaefghijklmnopqrstuvwxyz
Source 2013 Petrozavodsk, Moscow SU ST + NNSU Contest, Day 2, August 24, Problem G