접두사 뒤집기 3

길이가 N인 문자열 S가 주어진다. 정수 i를 1부터 N까지 차례대로 보며, 각 i마다 현재 문자열의 앞에서 정확히 i개의 문자를 뒤집을지 그대로 둘지 선택할 수 있다.

모든 선택을 마친 뒤 만들 수 있는 문자열 중 사전순으로 가장 앞서는 문자열을 출력하라.

첫째 줄에 문자열 S가 주어진다.

S의 길이는 최대 50이고, 모든 문자는 알파벳 대문자이다.

만들 수 있는 문자열 중 사전순으로 가장 앞서는 문자열을 출력한다.