시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 82 10 8 66.667%

문제

숫자로 이루어진 문자열이 있다. 이 숫자를 적절히 나누어서 증가수열을 만들고자 한다. 예를 들어 3546을 나눈다면 3,5,46 또는 35,46으로 나눌 수 있다. 이 증가수열 중 마지막 숫자를 가장 작게 하려 할 때, 어떻게 나누어야 하는지 구하는 프로그램을 작성하시오. (단, 앞자리에 0이 오는 것을 허용한다.)

입력

첫째 줄에 문자열이 주어진다. (단, 이 문자열의 자릿수는 80자리를 넘지 않는다)

출력

수열의 마지막 숫자를 출력하시오. (앞자리에 0이 있는 경우에는 0을 생략하고 출력한다.)

예제 입력 1

3456

예제 출력 1

6
W3sicHJvYmxlbV9pZCI6IjIwMzUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM5OWRcdWFjMDBcdWMyMThcdWM1ZjQiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzIyYlx1Yzc5MFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzc0IFx1Yzc4OFx1YjJlNC4gXHVjNzc0IFx1YzIyYlx1Yzc5MFx1Yjk3YyBcdWM4MDFcdWM4MDhcdWQ3ODggXHViMDk4XHViMjA0XHVjNWI0XHVjMTFjIFx1Yzk5ZFx1YWMwMFx1YzIxOFx1YzVmNFx1Yzc0NCBcdWI5Y2NcdWI0ZTRcdWFjZTBcdWM3OTAgXHVkNTVjXHViMmU0LiBcdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0IDM1NDZcdWM3NDQgXHViMDk4XHViMjA4XHViMmU0XHViYTc0IDMsNSw0NiBcdWI2MTBcdWIyOTQgMzUsNDZcdWM3M2NcdWI4NWMgXHViMDk4XHViMjBjIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1Yzc3NCBcdWM5OWRcdWFjMDBcdWMyMThcdWM1ZjQgXHVjOTExIFx1YjljOFx1YzljMFx1YjljOSBcdWMyMmJcdWM3OTBcdWI5N2MgXHVhYzAwXHVjN2E1IFx1Yzc5MVx1YWM4YyBcdWQ1NThcdWI4MjQgXHVkNTYwIFx1YjU0YywgXHVjNWI0XHViNWJiXHVhYzhjIFx1YjA5OFx1YjIwNFx1YzViNFx1YzU3YyBcdWQ1NThcdWIyOTRcdWM5YzAgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuIChcdWIyZTgsIFx1YzU1ZVx1Yzc5MFx1YjlhY1x1YzVkMCAwXHVjNzc0IFx1YzYyNFx1YjI5NCBcdWFjODNcdWM3NDQgXHVkNWM4XHVjNmE5XHVkNTVjXHViMmU0Lik8XC9wPiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoXHViMmU4LCBcdWM3NzQgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzU4IFx1Yzc5MFx1YjliZlx1YzIxOFx1YjI5NCA4MFx1Yzc5MFx1YjlhY1x1Yjk3YyBcdWIxMThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0KTxcL3A+Iiwib3V0cHV0IjoiPHA+XHVjMjE4XHVjNWY0XHVjNzU4IFx1YjljOFx1YzljMFx1YjljOSBcdWMyMmJcdWM3OTBcdWI5N2MgXHVjZDljXHViODI1XHVkNTU4XHVjMmRjXHVjNjI0LiAoXHVjNTVlXHVjNzkwXHViOWFjXHVjNWQwIDBcdWM3NzQgXHVjNzg4XHViMjk0IFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCAwXHVjNzQ0IFx1YzBkZFx1YjdiNVx1ZDU1OFx1YWNlMCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuKTxcL3A+IiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMjAzNSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkluY3JlYXNpbmcgU2VxdWVuY2VzIiwiZGVzY3JpcHRpb24iOiI8cD5HaXZlbiBhIHN0cmluZyBvZiBkaWdpdHMsIGluc2VydCBjb21tYXMgdG8gY3JlYXRlIGEgc2VxdWVuY2Ugb2Ygc3RyaWN0bHkgaW5jcmVhc2luZyBudW1iZXJzIHNvIGFzIHRvIG1pbmltaXplIHRoZSBtYWduaXR1ZGUgb2YgdGhlIGxhc3QgbnVtYmVyLiBGb3IgdGhpcyBwcm9ibGVtLCBsZWFkaW5nIHplcm9zIGFyZSBhbGxvd2VkIGluIGZyb250IG9mIGEgbnVtYmVyLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+SW5wdXQgd2lsbCBjb25zaXN0IG9mIG11bHRpcGxlIHRlc3QgY2FzZXMuIEVhY2ggY2FzZSB3aWxsIGNvbnNpc3Qgb2Ygb25lIGxpbmUsIGNvbnRhaW5pbmcgYSBzdHJpbmcgb2YgZGlnaXRzIG9mIG1heGltdW0gbGVuZ3RoIDgwLiBBIGxpbmUgY29uc2lzdGluZyBvZiBhIHNpbmdsZSAwIHRlcm1pbmF0ZXMgaW5wdXQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggaW5zdGFuY2UsIG91dHB1dCB0aGUgY29tbWEgc2VwYXJhdGVkIHN0cmljdGx5IGluY3JlYXNpbmcgc2VxdWVuY2UsIHdpdGggbm8gc3BhY2VzIGJldHdlZW4gY29tbWFzIG9yIG51bWJlcnMuIElmIHRoZXJlIGFyZSBzZXZlcmFsIHN1Y2ggc2VxdWVuY2VzLCBwaWNrIHRoZSBvbmUgd2hpY2ggaGFzIHRoZSBsYXJnZXN0IFx1ZmIwMXJzdCB2YWx1ZTsgaWYgdGhlcmUmcnNxdW87cyBhIHRpZSwgdGhlIGxhcmdlc3Qgc2Vjb25kIG51bWJlciwgZXRjLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==