30773번 - Михаил наносит ответный удар 스페셜 저지다국어

문제

Обратите внимание на нестандартное ограничение по памяти в данной задаче.

Вася очень любит участвовать в олимпиадах по информатике. Он уже давно понял, что больше всего ему нравится решать задачи, связанные со строками. Особенное впечатление на него произвела недавно изобретенная структура данных --- дерево палиндромов. Оказалось, что практически любую задачу на строки можно решить с помощью этой поистине всесильной структуры, ведь она умеет находить палиндромы даже там, где их нет и в помине!

Васе никак не удается заставить дерево палиндромов не искать, а создавать палиндромы из строк. А ведь так хочется! При этом, так как Вася очень ценит встречающиеся ему строки, он хочет лишь добавлять в них символы в произвольных местах, но не удалять и не изменять их. Помогите ему найти способ превращать обычные строки в палиндромы!

입력

В первой и единственной строке входных данных содержится непустая строка $s,ドル состоящая из строчных английских букв. Её длина, обозначаемая $|s|,ドル не превышает 15ドル,000円$ символов.

출력

В первой строке выведите единственное число $a$ --- минимальное количество символов, которые необходимо добавить в строку $s,ドル чтобы получился палиндром. Во второй строке выведите строку $t,ドル являющуюся палиндромом и получающуюся из $s$ добавлением указанного Вами числа символов (иными словами, должно быть верно $|s| + a = |t|$).

제한

노트

Палиндромом называется строка, одинаково читающаяся в обоих направлениях. Так, например, строки "a", "abraarba" являются палиндромами, а "ab" и "abracadabra" нет.