STRSEQ - String Subsequence

no tags 

 

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


hide comments
Miguel Oliveira: 2012-06-05 23:34:08

0 is a nonnegative integer.

The digit order is preserved.

Swapnil R.Mehta: 2012-06-02 13:35:38

Do we have to consider '0' also to be a nonnegative integer?

Jinhui: 2012-03-13 13:21:44

Is the digit order preserved?


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)