Inverse Common Superstring

Given a set of strings S = {S1, S2, ..., Sn}, a common superstring R of S is a string such that every string in S appears as a substring of R. For example, if S is {"abb", "baab", "bbc"}, then one common superstring R of S is "abbbaabbbc", which has length 10. Notice that every string in S appears as a substring of R. To check: "abb" appears in "[abb]baabbbc", "baab" appears in "abb[baab]bbc", and "bbc" appears in "abbbaab[bbc]". The string "abbbaabbbc" is also a common superstring of S; you can verify this yourself.

Among all common superstrings, the shortest one is usually the most interesting. It has many real-world applications, such as sparse matrix compression and DNA sequencing. In the example above, the shortest common superstring is "baabbc", which has length 6. To check: "aab" appears in "b[aab]bc", "baab" appears in "[baab]bc", and "bbc" appears in "baa[bbc]".

Unfortunately, finding the shortest common superstring is known to be NP-hard. That is, no polynomial-time algorithm for this problem is known at present.

The inverse problem of finding the shortest common superstring is: given a string R, find a set of strings S such that R is the shortest common superstring of S. Of course, this inverse problem is very easy and trivial. The set S can simply contain a single string equal to R. Note that a string is also a substring of itself.

Now you are going to solve a more challenging problem. Given a string R, find the lexicographically (alphabetically) smallest string that does not appear as a substring of R. To simplify the problem, a string is defined as a non-empty sequence of lowercase alphabetical characters (a-z). For example, if R is "icpc", then the lexicographically smallest string that does not appear as a substring of R is "a".

A string S = S1S2S3... is lexicographically smaller than a string T = T1T2T3... if one of the following holds:

• |S| < |T| and Si = Ti for all 1 ≤ i ≤ |S|, or
• there is an index i such that Si < Ti and Sj = Tj for all 1 ≤ j < i.

The first line contains a string whose length is between 1 and 1000, inclusive. The string consists only of lowercase alphabetical characters (a-z).

Print the lexicographically smallest string that is not a substring of the input string, on a single line. The output string must consist only of lowercase alphabetical characters.