-- Lexicographical trie
-- (c) Vadim Vinnik, 2011

import Char

data TrieNode = TrieNode Char Bool Trie
    deriving Show

type Trie = [TrieNode]

--
trieInsert :: Trie -> String -> Trie

trieInsert [] (char:[]) = [TrieNode char True []]

trieInsert [] (char:wordRest) = [TrieNode char False (trieInsert [] wordRest)]

trieInsert (node@(TrieNode char1 bFinal trieChildren):trieSiblings) word@(char2:wordRest)
      | char1 == char2 && wordRest == [] = (TrieNode char1 True trieChildren):trieSiblings
      | char1 == char2                   = (TrieNode char1 bFinal (trieInsert trieChildren wordRest)):trieSiblings
      | char1 >  char2                   = (trieInsert [] word) ++ (node : trieSiblings)
      | otherwise                        = node : (trieInsert trieSiblings word)

--
trieExists :: Trie -> String -> Bool

trieExists [] _ = False

trieExists ((TrieNode char1 bFinal trieChildren):trieSiblings) word@(char2:wordRest)
      | char1 == char2 && wordRest == [] = bFinal
      | char1 == char2                   = trieExists trieChildren wordRest
      | otherwise                        = trieExists trieSiblings word

--
trieListAll :: Trie -> [String]

trieListAll [] = []

trieListAll ((TrieNode char bFinal trieChildren):trieSiblings) =
    (if bFinal then [[char]] else []) ++
    (map (char:) (trieListAll trieChildren)) ++
    (trieListAll trieSiblings)

--
trieEndings :: Trie -> String -> [String]

trieEndings [] _ = []

trieEndings trie [] = trieListAll trie

trieEndings (node@(TrieNode char1 bFinal trieChildren):trieSiblings) word@(char2:wordRest)
    | char1 == char2 = (if bFinal then [""] else []) ++ trieEndings trieChildren wordRest
    | otherwise      = trieEndings trieSiblings word

--
trieCompletions :: Trie -> String -> [String]

trieCompletions trie word = map (word++) (trieEndings trie word)

--
trieFromText :: String -> Trie

trieFromText string = foldl trieInsert [] (words string)


--
main = do s <- getLine
          let t = map (\c -> (if isAlpha c then c else ' ')) s
          let r = trieFromText t
          print (trieEndings r "wh")
          print (trieCompletions r "wh")
          print (trieEndings r "th")
          print (trieCompletions r "th")