미하일의 반격

주의: 이 문제의 메모리 제한은 일반적인 문제와 다릅니다.

바샤는 정보 올림피아드에 참가하는 것을 매우 좋아한다. 그는 문자열 문제를 가장 즐긴다는 것을 깨달았다. 최근 새로 발명된 자료구조인 팰린드롬 트리에 깊은 인상을 받았다. 팰린드롬 트리는 팰린드롬이 없는 곳에서도 팰린드롬을 찾아낸다.

바샤는 팰린드롬 트리가 팰린드롬을 찾는 대신 문자열로부터 팰린드롬을 만들어 내기를 바란다. 그는 문자열의 임의의 위치에 문자를 삽입하기만 하려 하고, 기존 문자를 삭제하거나 바꾸지는 않으려 한다. 그가 주어진 문자열을 팰린드롬으로 바꾸는 방법을 찾도록 도와 달라.

첫 번째이자 유일한 줄에 소문자 영문자로 이루어진 비어 있지 않은 문자열 $s$가 주어진다. 길이 $|s|$는 $15\,000$을 넘지 않는다.

첫 줄에는 $s$에 문자를 추가해 팰린드롬으로 만드는 데 필요한 최소 문자 수 $a$를 출력한다. 둘째 줄에는 $s$에 정확히 $a$개의 문자를 추가해 얻은 팰린드롬 $t$를 출력한다. 이때 $|s| + a = |t|$이어야 한다.

팰린드롬은 양방향으로 같게 읽히는 문자열이다. 예를 들어 "a"와 "abraarba"는 팰린드롬이고, "ab"와 "abracadabra"는 팰린드롬이 아니다.