시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 53 16 15 37.500%

문제

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

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

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

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

상민 : 닉네임이 뭔데?

대영 : dy2000

상민 : dY2000SYb

대영 : !

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

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

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

원본 대칭 원본 대칭 원본 대칭 원본 대칭 원본 대칭
A A N   a   n n 0 0
B   O O b d o o 1 1
C   P   c   p q 2 S
D   Q   d b q p 3 E
E 3 R   e   r 7 4  
F   S 2 f   s   5 Z
G   T T g   t   6  
H H U U h   u u 7 r
I I V V i i v v 8 8
J   W W j   w w 9  
K   X X k   x x    
L   Y Y l l y      
M M Z 5 m m z      

입력

첫 줄에 원본 닉네임 S를 입력받는다.

출력

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

제한

|S| ≤ 1,000,000

예제 입력 1

qilip

예제 출력 1

qilip

"qIlIp" 도 정답으로 인정된다.

예제 입력 2

dy2000

예제 출력 2

dY2000SYb

"dY20000000000SYb" 도 멋진 퀼린드롬 이지만, 가장 짧은 퀼린드롬은 아니다.

예제 입력 3

7owo

예제 출력 3

7owor

7r이 완전히 거울 대칭으로 보이지는 않지만, 상민이는 이 정도로 비슷하면 인정하기 때문에 거울 대칭 표에 7r은 거울 대칭이라고 적었다.

출처

University > 아주대학교 > 2020 아주대학교 프로그래밍 경시대회 APC - Div.1 E3번