import Data.Maybe
import Data.List
import Data.Ratio
 
first' "" _ = Just 0
first' _ "" = Nothing
first' (x:xs) ys = let 
    (zs,ws) = break (==x) ys 
    in if ws == ""
        then Nothing
        else ((length zs)+) <$> (first' xs $ tail ws)
 
first x y =  fromMaybe 0 $ (negate.(1%).(+1)) <$> first' x y
 
trickOrTreat x = case compare (first "trick" x) (first "treat" x) of
    LT -> "trick"
    GT -> "treat"
    otherwise -> "Happy Halloween" 
 
main = mapM_ (print.trickOrTreat) ["trick or treat", ". tr   ick","ttrriecatk","tri kc eat","my money"]
 

aW1wb3J0IERhdGEuTWF5YmUKaW1wb3J0IERhdGEuTGlzdAppbXBvcnQgRGF0YS5SYXRpbwoKZmlyc3QnICIiIF8gPSBKdXN0IDAKZmlyc3QnIF8gIiIgPSBOb3RoaW5nCmZpcnN0JyAoeDp4cykgeXMgPSBsZXQgCiAgICAoenMsd3MpID0gYnJlYWsgKD09eCkgeXMgCiAgICBpbiBpZiB3cyA9PSAiIgogICAgICAgIHRoZW4gTm90aGluZwogICAgICAgIGVsc2UgKChsZW5ndGggenMpKykgPCQ+IChmaXJzdCcgeHMgJCB0YWlsIHdzKQoKZmlyc3QgeCB5ID0gIGZyb21NYXliZSAwICQgKG5lZ2F0ZS4oMSUpLigrMSkpIDwkPiBmaXJzdCcgeCB5Cgp0cmlja09yVHJlYXQgeCA9IGNhc2UgY29tcGFyZSAoZmlyc3QgInRyaWNrIiB4KSAoZmlyc3QgInRyZWF0IiB4KSBvZgogICAgTFQgLT4gInRyaWNrIgogICAgR1QgLT4gInRyZWF0IgogICAgb3RoZXJ3aXNlIC0+ICJIYXBweSBIYWxsb3dlZW4iIAoKbWFpbiA9IG1hcE1fIChwcmludC50cmlja09yVHJlYXQpIFsidHJpY2sgb3IgdHJlYXQiLCAiLiB0ciAgIGljayIsInR0cnJpZWNhdGsiLCJ0cmkga2MgZWF0IiwibXkgbW9uZXkiXQo=