암호문

페챠와 바샤는 스파이 놀이를 좋아한다. 스파이 놀이에는 비밀 암호문이 빠질 수 없다. 바샤는 최근 메시지를 암호화하는 새로운 방법을 생각해 냈다. 그는 암호화 방법을 비밀로 두고, 페챠가 언제든 쓸 수 있도록 복호화 방법만 페챠에게 알려 주었다.

페챠가 복호화하려면 바샤가 보낸 암호문에서 사전순으로 가장 큰 부분 문자열을 찾아야 한다. 그 부분 문자열이 원래 텍스트다. 페챠는 이 탐색을 빨리 하지 못하므로, 그를 도와줄 프로그램을 작성해 달라.

첫 번째이자 유일한 줄에 비어 있지 않은 암호문이 주어진다. 암호문은 영어 소문자로만 이루어지며, 길이는 1000 이하이다.

복호화된 메시지를 출력 파일에 쓴다.