18245번 - 이상한 나라의 암호

소설을 좋아하는 하영이는 평소와 같이 이상한 나라의 앨리스라는 소설을 읽고 있었다.

책을 읽던 하영이는 정신이 멍해지더니 갑자기 자신이 이상한 나라에 떨어져 있다는 것을 깨닫게 되었다!

이상한 나라에서 길을 헤매던 하영이는 이상한 나라의 트럼프 병사들을 만나게 되었다.

하트 여왕의 부하인 트럼프 병사들은 하영이에게 자신들이 말하는 암호 문장을 제대로 해석하여 맞추면 살려주고, 하나라도 틀린다면 하트 여왕의 명령에 따라 처형하겠다고 말한다!

하영이는 이 길고 많은 줄로 이루어진 문장을 어떻게 해석해야 할지 고민하던 중, 풀숲 속에 놓인 석판을 발견하였다.

[ i번째 줄의 문장은 문장의 첫 번째 글자에서 시작하여 i칸씩 건너뛰며 읽어야 한다 ]

하지만, 하영이는 이 암호를 직접 해석하기에는 시간이 부족하다는 것을 깨달았다. 하영이를 살려주기 위해서 이 암호가 무슨 뜻인지 해석해주는 프로그램을 만들어주자!

첫째 줄부터 최대 100개의 줄에 알파벳 대문자로 이루어진 해석해야 할 문장이 주어진다. 문장의 길이는 10⁴이하인 자연수이다.

해석해야 할 문장이 모두 주어진 후, 마지막 문장은 Was it a cat I saw? 로 주어지고, 마지막 문장은 해석하지 않는다.

한 줄에 한 문장씩 해당 줄의 문장에서 해석한 암호를 출력한다.

"Was it a cat I saw?"는 실제 "이상한 나라의 앨리스" 소설에서 등장하는 회문(palindrome)이다.