-- Trie, yet another implementation
-- (c) Vadim Vinnik, 2011

data Trie = Trie Bool [TrieEdge] deriving Show
data TrieEdge = TrieEdge Char Trie deriving Show

trieEmpty = Trie False []

trieInsert :: Trie -> String -> Trie
trieInsert (Trie _ l) [] = Trie True l
trieInsert (Trie x l) s = Trie x (f l s) where
    f [] (a:b) = [h a b]
    f l1@(e@(TrieEdge c1 t):l2) s@(c2:s2)
        | c1 == c2   = (TrieEdge c1 (trieInsert t s2)):l2
        | c1  > c2   = (h c2 s2) : l1
        | otherwise  = e : (f l2 s)
    h a b = TrieEdge a (trieInsert trieEmpty b)

trieExists :: Trie -> String -> Bool
trieExists (Trie x _) [] = x
trieExists (Trie _ l) s = f l s where
    f [] _ = False
    f ((TrieEdge c1 t):l2) s@(c2:s2)
        | c1 == c2   = trieExists t s2
        | otherwise  = f l2 s

trieToString :: Trie -> String
trieToString t = h t " " where
    h (Trie x l) s = (if x then "#" else "") ++ '\n' : (foldl (++) "" (map f l)) where
        f (TrieEdge c t) = (s ++ (c:[]) ++ (h t (" " ++ s)))

trieFromText :: String -> Trie
trieFromText s = foldl trieInsert trieEmpty (words s)

trieAllWords :: Trie -> [String]
trieAllWords (Trie x l) = (if x then "":r else r) where
    r = foldl (++) [] (map f l) where
        f (TrieEdge c t) = map (c:) (trieAllWords t)

trieEndings :: Trie -> String -> [String]
trieEndings t [] = trieAllWords t
trieEndings (Trie _ l) s = f l s where
    f [] _ = []
    f ((TrieEdge c1 t1):l1) s1@(c2:s2)
        | c1 == c2  = trieEndings t1 s2
        | c1  < c2  = f l1 s1
        | otherwise = []

trieCompletions :: Trie -> String -> [String]
trieCompletions t s = map (s++) (trieEndings t s)

main = do s <- getLine
          let t = trieFromText s
          putStr (trieToString t)
          print (trieAllWords t)
          print (trieEndings t "wh")
          print (trieCompletions t "wi")