Lektira

Mario는 학교 숙제로 도스토옙스키를 읽는 대신 또 실없는 게임을 만들어 내고 있다. 그의 최신 게임의 규칙은 다음과 같다.

먼저 책에서 아무 단어나 하나 고른다. 그런 다음 그 단어를 임의의 두 곳에서 잘라 세 개의 단어로 나눈다.

그 후 세 단어 각각에서 글자의 순서를 뒤집는다(첫 글자와 마지막 글자를 바꾸고, 둘째 글자와 뒤에서 둘째 글자를 바꾸는 식이다).

마지막으로 세 단어를 자르기 전과 같은 순서로 다시 이어 붙인다.

게임의 목표는 사전순으로 가능한 한 가장 앞서는 단어를 얻는 것이다. 다시 말해, 위 과정으로 얻을 수 있는 모든 단어 중 사전에서 가장 먼저 나올 단어를 찾는 것이다.

Mario의 게임을 완벽하게 플레이하는 프로그램을 작성하시오.

입력의 첫째 줄이자 유일한 줄에 Mario가 고른 단어, 즉 공백 없는 영어 알파벳 소문자 문자열이 주어진다.

입력 단어의 길이는 \(3\) 이상 \(50\) 이하이다.

가장 좋은 단어를 한 줄에 출력한다.

riseoj 작성

출처 COCI 2007/2008 Contest 4