다음 특별한 문자열

시간 제한2초메모리 제한512 MB

요약

이진 특수 문자열(모든 분할에서 U < V)이 주어질 때, 같은 길이의 다음 특수 문자열을 사전순으로 구하고 없으면 -1을 출력한다.

난이도: 보통10점 중 7점
유형: 문자열, 그리디, 조합론, 구현
정답자: 아직 제출이 없습니다

문제

문자열 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을 출력한다.

예제3

예제 1
입력
```
01
```
예상 출력
```
-1
```
예제 2
입력
```
00101
```
예상 출력
```
00111
```
예제 3
입력
```
0010111
```
예상 출력
```
0011011
```