Михаил наносит ответный удар

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

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

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

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

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

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