1464번 - 뒤집기 3

세준이는 어떤 문자열 S를 뒤집으려고 한다. 문자열을 뒤집는 방법은 문자열의 길이를 N이라고 하자. i만큼을 뒤집는다는 소리는 그 문자열의 처음부터 정확하게 i개의 문자를 역순으로 뒤집는 것이다. 세준이는 1부터 N까지 수를 차례대로 생각한다. 그리고, 뒤집을지 안 뒤집을지 선택할 수 있다.

예를 들어, S="BCDAF" 이고, 세준이가 길이 1만큼을 뒤집지 않고, 길이 2만큼도 뒤집지 않고 세준이가 길이 3만큼을 뒤집는다고 하면 문자열은 DCBAF가 된다. 다시 여기서 4만큼 뒤집으면 ABCDF가 된다. 그리고, 마지막으로 길이를 5만큼 뒤집지 않으면 주어진 문자열 S를 사전순으로 가장 앞서게 만들 수 있다.

문자열 S가 주어졌을 때, 위와같은 뒤집기 방법으로 만들 수 있는 문자열 중 사전순으로 제일 앞서는 것을 출력하시오.

첫째 줄에 문자열 S가 주어진다. 문자열의 길이는 최대 50이다. 알파벳 대문자만 들어온다.

첫째 줄에 사전순으로 가장 앞서는 정답을 출력한다.