import qualified Data.Map as M
import IO
import List
import Random

type Key a = (Maybe a, Maybe a)
type Markov a = M.Map (Key a) [Maybe a]

buildTable :: (Ord a) => [a] -> Markov a
buildTable vals = let
    vals' = [Nothing,Nothing] ++ (map Just vals) ++ [Nothing]
    buildTable' (w1:ws@(w2:w3:_)) = M.insertWith (++) (w1,w2) [w3] $
        buildTable' ws
    buildTable' _ = M.empty
    in buildTable' vals'

generate :: (Ord a, RandomGen g) => Markov a -> g -> Key a -> [a]
generate m g seed = unfoldr (step m) (seed,g)

step :: (Ord a, RandomGen g)
        => Markov a -> (Key a,g) -> Maybe (a, (Key a,g))
step m (k,g) = let v = m M.! k
                   (i,g') = randomR (0,length v - 1) g
                   in do w <- v !! i
                         let k' = (snd k, Just w)
                         return (w, (k',g'))

main = do
    hSetBuffering stdin LineBuffering
    c <- getContents
    g <- getStdGen
    let table = buildTable $ words c
    let result = generate table g (Nothing,Nothing)
    putStrLn $ unwords result