퀼린드롬 (Hard)

입력 제한 외 난이도에 따른 문제의 차이는 없다.

상민이는 오랜 고민 끝에 아주 멋진 닉네임 "qilip"을 생각해냈다. 오, 팰린드롬!.. 이라고 생각했지만..

이 닉네임이 팰린드롬이 되려면 거꾸로 읽어도 "qilip"이어야 한다. 하지만 거꾸로 읽으면 "piliq"이므로 이 닉네임은 팰린드롬이 아니다. 가운데를 기준으로 완전히 거울 대칭처럼 보이는 이 기묘한 문자열을 '퀼린드롬'이라고 부르자. 예를 들어 "dad"는 팰린드롬이지만 퀼린드롬은 아니며, "mom"은 팰린드롬인 동시에 퀼린드롬이다. 모두가 퀼린드롬 닉네임을 탐낸다.

대영: 상민아, 내 닉네임도 퀼린드롬으로 만들어줘!

상민: 닉네임이 뭔데?

대영: dy2000

상민: dY2000SYb

대영: !

상민이는 멋진 퀼린드롬 닉네임을 만들어달라는 요청이 쏟아져 일상생활마저 힘들어졌다. 멋진 퀼린드롬 닉네임이란 원본 닉네임을 부분 문자열로 포함하면서 퀼린드롬인 닉네임이다. 즉, 만들어진 멋진 퀼린드롬 닉네임의 양쪽 끝을 적절히 지우면 원본 닉네임을 얻을 수 있다. 모두가 퀼린드롬에 미쳐 있으므로, 퀼린드롬으로 만들 수만 있다면 대소문자가 바뀌는 것은 개의치 않는다. 예를 들어 "yoy"는 퀼린드롬이 아니지만, 대문자로 바꾼 "YoY"는 퀼린드롬이므로 사람들은 충분히 만족한다.

상민이를 위해 가장 짧고 멋진 퀼린드롬 닉네임을 만들어주는 프로그램을 작성하자! 특별히, 원본과 대칭이 같은 문자는 홀수 길이 퀼린드롬의 가운데에 놓일 수 있다.

완전히 같은 모양은 아니더라도 "이 정도면 인정이지!"라며 상민이가 작성한 거울 대칭 표는 다음과 같다.

첫 줄에 원본 닉네임 $S$가 주어진다.

가장 짧고 멋진 퀼린드롬 닉네임을 출력한다. 만약 멋진 퀼린드롬 닉네임을 만들 수 없다면 "-1"을 출력한다.

$|S| \le 1,000,000$