According to a tale, in the sacred Indian city of Benares, beneath a temple
that marked the center of the world, Brahma put three diamond needles and
placed 64 gold disks on them. Priests of the temple are busy transferring the
disks from needle to needle. It is believed that the world will perish as soon
as the task is done.
Another legend is known in Ural. It is said that a monastery is lost in woods
at the boundary of Europe and Asia, where the mythical stone flower grew. The
monks who live there are doomed to write positive integers on parchment until
the Last Judgement. Nobody knows when and where they started this work. There
is a legend among monks that when the monastery had been built its first abbot
was visited in his dream by the Archangel Gabriel, who showed a stone on the
slopes of the Ural mountains where a string of digits was carved. Gabriel
ordered to write all the integers starting from the smallest integer that was
not a substring of that string. If this legend is true, which integer was
written by the monks first?
The only input line contains the nonempty string consisting of decimal digits carved on the
stone. The length of the string does not exceed 105.
Output the positive integer that is the first number written by the
Problem Author: Daniil Ayzenshteyn
Problem Source: The 14th Urals Collegiate Programing Championship, April 10, 2010