ABACABA зіставлення
Розгляньмо перестановку літер англійського алфавіту в нижньому регістрі: P = {p[1], p[2], ..., p[26]}. Використовуючи P, можна побудувати таку послідовність рядків:
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]
Легко побачити, що довжина S[26] становить 2^26 - 1 символів. Початок S[26] виглядає як p[1]p[2]p[1]p[3]p[1]p[2]p[1]....
Вам надано рядок T, що складається з літер англійського алфавіту в нижньому регістрі. За фіксованої перестановки P ви можете отримати S[26], після чого дозволено замінити деякі літери в T так, щоб отриманий рядок став підрядком S[26]. Ваше завдання — мінімізувати кількість замін у T, вибравши найбільш підходящу перестановку P.
Вхідні дані
Один рядок T (1 ≤ |T| ≤ 20000), що містить літери англійського алфавіту в нижньому регістрі.
Вихідні дані
У першому рядку виведіть мінімальну кількість літер, які потрібно замінити. У другому рядку виведіть позицію в рядку S[26], з якої починається отриманий підрядок (індекси починаються з 1). У третьому рядку виведіть перестановку P.