숫자 끈

하나의 숫자 문자열이 주어진다. 이 문자열을 2개 이상의 부분으로 나누어, 각 부분이 정수로 해석될 때 엄격하게 증가하는 수열이 되도록 하려고 한다.

예를 들어 "1234"는 1, 2, 3, 4로 나눌 수 있다. "91011"은 9, 10, 11로 나눌 수 있다.

여러 가지 분할 방법이 가능한 경우, 마지막 수를 최소화하는 분할을 선택한다. 마지막 수가 같은 경우 사전순으로 가장 뒤인 분할을 선택한다.

유효한 분할 결과를 출력하는 프로그램을 작성하시오. 단, 두 자리 이상의 수는 0으로 시작할 수 없다.

입력

첫째 줄에 숫자 문자열이 주어진다. (길이 2 이상, 30 이하)

출력

나눈 수들을 공백으로 구분하여 출력한다. 유효한 분할이 없으면 -1을 출력한다.

입출력 예시

입력 1

1234

출력 1

1 2 3 4

입력 2

258

출력 2

2 5 8