STRSEQ - String Subsequence

Given a string of digits, find the smallest nonnegative integer that does not occur in the given string as a subsequence. The length of the string is between 1 and 100000, inclusive.

Input

The input consists of several lines (at most 200), each with a single string S, with between 1 and 10^5 digits.

Output

Print a single line for each string containing the smallest nonnegative integer that does not occur in the given string as a subsequence.

Example

Input
9876543210
21698921085321984125
12345678901

Output
11
7
22

Added by:Marcos Kawakami
Date:2012-02-18
Time limit:4.920s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Author: Guilherme Souza (guirns)

hide comments
2012-06-05 23:34:08 Miguel Oliveira
0 is a nonnegative integer.

The digit order is preserved.
2012-06-02 13:35:38 Swapnil R.Mehta
Do we have to consider '0' also to be a nonnegative integer?
2012-03-13 13:21:44 Jinhui
Is the digit order preserved?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.