import Control.Applicative
import Control.Monad.State.Lazy
import qualified Data.HashMap as HM
import Data.Monoid
import Data.List

data Subsequence = Subsequence
    { str :: String
    , indicies :: [Int] } deriving Show

emptySubseq :: Subsequence
emptySubseq = Subsequence "" []

allStrings :: [String] -> [String]
allStrings alphabet =  alphabet <> ((++) <$> allStrings alphabet <*> alphabet)

dict = allStrings $ map (: []) ['a'..'z']

{-
insertAndReturnSeqIdx :: Int -> [Int] -> Int -> ([Int], Int)
insertAndReturnSeqIdx i [] a = ([i], a)
insertAndReturnSeqIdx i ix a
    | i < head ix = (i : ix, a)
    | not $ null ix = let
        (res, newA) = insertAndReturnSeqIdx i (tail ix) (a + 1) in
        (head ix : res, newA)
    | null ix = ([i], a)

-- recurrence relation between subsequences
-- TODO: Tabulation
reccur :: V.Vector Char -> Subsequence -> Int -> Subsequence
reccur input prevSeq idx = Subsequence newStr newIndicies
      where (newIndicies, seqIdx) =
                insertAndReturnSeqIdx idx (indicies prevSeq) 0
            (front, end) = splitAt seqIdx $ str prevSeq
            newStr = front ++ ((input V.! idx) : end)

isSubseq Subsequence sx = 
-}

{-
search :: V.Vector Char -> String -> Either String Int
search input target = do
    let limit = length target
    let inputLen = V.length input
    map 
-}

betterIsSubsequenceOf :: String -> String -> State (HM.Map String Bool) Bool
betterIsSubsequenceOf part all = do
    hm <- get
    let res = HM.lookup part hm
    case res of
        Nothing -> do
            let newMap = HM.insert part res
            return $ isSubsequenceOf part all
        Just s -> return s

search :: String -> [String] -> State (HM.Map String Bool) String
search input dict = do
    isSubsequence <- betterIsSubsequenceOf (head dict) input
    if isSubsequence then
        search input (tail dict)
    else
        return $ head dict


{-
solve :: V.Vector Char -> Int
solve input = 
-}
    

main = do
    --input <- V.fromList <$> getLine
    input <- getLine
    let res = evalState (search input dict) HM.empty
    putStrLn res
