import Data.List
doSubst :: (String, String) -> String -> (Bool, String)
doSubst _ [] = (False, [])
doSubst (from, to) target@(t:ts) = case isPrefixOf from target of
	True -> (True, to ++ drop (length from) target)
	False -> let (b, s) = doSubst (from, to) ts in (b, t:s)
runThue :: [(String, String)] -> String -> String
runThue substs init = case runThue' substs init False of
	(False, _) -> init
	(True, newinit) -> runThue substs newinit
runThue' :: [(String, String)] -> String -> Bool -> (Bool, String)
runThue' [] init sure = (sure, init)
runThue' (subst:substs) init sure = case doSubst subst init of
	(False, _) -> runThue' substs init sure
	(True, newinit) -> runThue' substs newinit True