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

문제

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

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

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

입력

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

출력

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

힌트

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