다음 특별한 문자열

문자열 S가 다음 두 조건을 모두 만족하면 특별한 문자열이라고 한다.

• S의 모든 글자가 '0' 또는 '1'이다.
• S를 비어 있지 않은 두 부분 U와 V로 나누어 S = UV로 쓸 때, 어떻게 나누어도 U가 V보다 사전순으로 앞선다.

예를 들어 S = "00101"은 특별한 문자열이다. "0" < "0101", "00" < "101", "001" < "01", "0010" < "1"이 모두 성립하기 때문이다. 길이가 1인 문자열은 두 부분으로 나눌 수 없으므로 "0"과 "1"은 둘 다 특별한 문자열이다.

길이가 $N$인 특별한 문자열 S가 주어진다. 길이가 $N$인 특별한 문자열을 모두 사전순으로 정렬했을 때 S 바로 다음에 오는 문자열을 구하는 프로그램을 작성하시오.

첫째 줄에 특별한 문자열 S가 주어진다. S의 길이 $N$은 $1 \le N \le 50$을 만족하는 자연수이다.

길이가 $N$인 특별한 문자열 중 사전순으로 S 바로 다음에 오는 문자열을 출력한다. S가 사전순으로 마지막에 오는 특별한 문자열이면 -1을 출력한다.