Рассмотрим перестановку букв нижнего регистра английского алфавита: P = {p1, p2, ..., p26}. Используя P, можно сгенерировать следующую последовательность строк:

S1 = p1

S2 = S1 + p2 + S1

S3 = S2 + p3 + S2

...

S26 = S25 + p26 + S25

Легко обнаружить, что длина S26 равна 226 - 1 буквам. Начало S26 выглядит как p1p2p1p3p1p2p1....

Вам задана строка T из букв нижнего регистра английского алфавита. По фиксированной перестановке P Вы можете получить S26, после чего заменить некоторые буквы T другими так, чтобы результирующая строка стала подстрокой S26. Вам следует минимизировать количество букв, которое следует заменить в T выбрав наиболее подходящую перестановку P.

Входные данные

Одна строка T (1 ≤ |T| ≤ 20000), содержащая буквы нижнего регистра английского алфавита.

Выходные данные

В первой строке вывести наименьшее количество букв, которое следует заменить. Во второй строке вывести позицию в строке S26, где начинается результирующая подстрока (индексы нумеруются с 1).В третьей строке вывести перестановку P.