content: import Aoc
  import Data.List.Split
  import Data.Function
  
  input = "sw,s,se,se,se,se,se,nw,ne,ne,ne,ne,ne,n,n,ne,n,n,n,n,n,sw,sw,n,ne,nw,n,n,nw,nw,n,nw,nw,nw,nw,nw,nw,nw,ne,sw,s,nw,sw,se,nw,sw,sw,nw,nw,nw,sw,sw,s,nw,nw,sw,sw,sw,sw,n,sw,sw,sw,sw,sw,sw,sw,sw,s,s,sw,sw,s,sw,s,sw,sw,sw,sw,ne,s,s,ne,sw,s,sw,s,s,n,ne,sw,s,sw,s,s,s,s,s,s,s,s,s,s,s,s,sw,s,s,n,s,s,s,se,se,s,s,sw,s,se,se,se,s,n,s,s,se,s,se,se,se,se,ne,s,n,sw,se,se,se,se,se,s,se,nw,nw,se,se,se,se,se,se,se,n,ne,se,s,se,se,se,ne,se,nw,se,se,s,ne,se,n,se,se,ne,sw,se,ne,se,se,se,nw,nw,ne,se,se,s,n,n,se,se,ne,se,ne,se,se,ne,se,se,ne,ne,ne,ne,ne,se,ne,se,nw,se,se,s,s,se,ne,ne,se,ne,ne,ne,ne,ne,ne,nw,ne,ne,ne,s,ne,n,ne,se,ne,n,ne,nw,n,ne,n,ne,ne,ne,ne,ne,n,nw,ne,ne,ne,ne,s,ne,ne,s,ne,ne,n,n,se,n,ne,n,ne,nw,ne,s,ne,n,ne,ne,ne,n,ne,s,s,ne,ne,ne,ne,ne,nw,ne,n,ne,ne,ne,n,ne,ne,n,ne,ne,n,n,ne,ne,ne,n,s,n,s,ne,ne,n,n,n,n,n,n,n,n,ne,n,n,sw,n,n,n,nw,n,ne,ne,sw,n,n,n,s,n,n,n,n,n,n,n,n,n,nw,se,n,s,s,n,n,n,ne,n,n,nw,n,n,nw,nw,n,n,nw,nw,n,nw,n,n,n,n,se,nw,n,nw,n,nw,nw,n,n,nw,nw,n,nw,n,n,nw,nw,n,nw,ne,n,n,n,n,nw,nw,nw,n,nw,n,nw,s,nw,n,n,n,n,nw,nw,n,n,nw,n,nw,nw,se,nw,ne,n,n,ne,n,nw,nw,n,n,n,nw,n,nw,n,n,nw,ne,nw,s,n,ne,n,nw,n,nw,nw,n,nw,n,n,nw,nw,nw,n,n,nw,nw,nw,nw,nw,n,nw,n,sw,n,n,nw,nw,nw,nw,s,nw,s,nw,nw,nw,n,nw,nw,nw,se,s,nw,nw,sw,nw,nw,n,se,ne,nw,nw,nw,sw,sw,ne,nw,nw,nw,nw,nw,nw,s,nw,nw,nw,nw,nw,sw,nw,nw,nw,s,nw,nw,se,nw,nw,nw,nw,sw,nw,ne,nw,nw,nw,nw,s,nw,nw,nw,nw,nw,n,nw,sw,sw,n,nw,nw,sw,nw,nw,sw,sw,se,nw,nw,nw,s,sw,nw,se,nw,sw,se,n,sw,sw,nw,sw,nw,nw,nw,nw,nw,ne,nw,nw,sw,nw,nw,nw,nw,sw,nw,sw,n,nw,nw,sw,nw,sw,sw,nw,sw,nw,nw,sw,sw,sw,sw,nw,ne,sw,nw,sw,sw,sw,sw,nw,sw,nw,sw,sw,sw,nw,sw,nw,nw,nw,sw,nw,sw,sw,sw,sw,sw,sw,nw,sw,n,sw,sw,sw,ne,sw,ne,sw,sw,nw,nw,sw,nw,sw,sw,sw,nw,sw,sw,s,sw,sw,ne,ne,s,sw,n,nw,sw,nw,ne,ne,se,sw,sw,sw,nw,nw,sw,nw,sw,n,sw,nw,s,sw,sw,sw,n,nw,sw,sw,ne,sw,sw,s,sw,se,s,sw,ne,s,sw,sw,sw,sw,sw,sw,sw,sw,sw,nw,n,n,sw,sw,ne,sw,sw,sw,n,sw,se,sw,sw,nw,n,sw,n,s,s,s,sw,sw,s,nw,sw,n,sw,sw,sw,sw,sw,sw,sw,sw,nw,sw,s,ne,n,sw,sw,sw,sw,sw,sw,sw,ne,sw,sw,s,sw,sw,s,sw,sw,sw,s,nw,s,sw,n,sw,sw,s,s,sw,s,sw,sw,ne,s,sw,s,sw,sw,n,n,s,sw,sw,sw,s,sw,s,s,sw,se,sw,sw,n,s,sw,sw,n,s,sw,sw,s,sw,sw,sw,s,sw,sw,se,sw,sw,sw,nw,s,sw,s,sw,sw,sw,s,sw,sw,n,s,s,s,s,ne,sw,sw,s,sw,s,s,sw,se,sw,nw,sw,sw,n,n,sw,n,s,s,se,s,sw,s,sw,s,s,ne,se,sw,s,se,sw,s,s,s,s,s,ne,se,sw,sw,sw,sw,nw,s,s,s,sw,s,s,se,sw,s,s,sw,n,sw,ne,n,s,sw,s,sw,s,s,s,s,sw,sw,se,sw,sw,s,s,s,s,sw,s,n,n,nw,nw,sw,se,s,sw,sw,sw,s,s,s,s,s,s,s,s,sw,se,s,n,n,s,s,s,s,s,s,ne,n,s,s,sw,s,s,s,s,s,sw,se,se,s,ne,sw,s,s,nw,s,sw,s,n,nw,sw,s,s,s,s,sw,s,s,sw,s,s,sw,s,s,s,s,s,s,sw,s,s,s,s,s,sw,s,s,n,s,s,ne,s,s,s,s,s,s,sw,n,s,s,s,ne,s,s,s,s,n,ne,s,s,s,s,s,s,n,sw,s,nw,s,s,s,se,s,s,s,n,s,s,sw,nw,nw,n,sw,s,s,s,s,s,s,s,s,se,s,se,n,s,se,s,nw,se,ne,s,s,s,s,s,se,s,s,nw,s,se,s,s,sw,se,s,se,s,s,n,s,s,s,s,s,s,s,se,se,se,nw,se,se,se,se,s,se,nw,s,s,s,s,ne,nw,se,s,s,n,s,s,se,ne,s,s,n,s,s,nw,se,n,nw,ne,ne,se,s,ne,se,se,s,s,ne,s,s,ne,s,s,se,n,se,se,s,s,n,se,s,se,s,se,nw,se,s,sw,s,ne,s,s,s,sw,se,s,s,se,s,s,se,se,s,se,sw,se,s,se,ne,s,sw,se,se,s,se,se,se,ne,s,n,s,n,se,ne,s,ne,s,n,s,ne,sw,ne,s,s,nw,s,sw,se,s,se,s,se,s,se,se,nw,s,se,se,n,sw,s,se,se,se,se,s,nw,n,se,s,s,s,s,s,se,se,s,se,se,se,nw,s,se,se,se,se,se,s,s,s,se,s,se,n,s,se,s,se,se,se,se,ne,s,s,se,s,s,se,s,se,s,se,nw,nw,s,se,se,s,ne,s,ne,se,nw,n,se,sw,se,s,n,se,se,s,s,se,se,se,se,s,se,ne,se,se,s,se,ne,sw,sw,nw,se,n,s,ne,se,se,se,s,se,sw,s,nw,se,se,se,se,se,nw,se,se,sw,se,se,se,sw,se,ne,se,se,ne,s,se,se,se,se,se,se,n,s,ne,se,s,s,se,se,se,se,se,se,se,se,se,se,se,se,se,se,se,se,se,s,ne,se,s,se,ne,se,se,se,s,ne,se,se,se,ne,n,s,se,se,se,se,se,se,se,s,se,se,s,se,se,ne,se,ne,ne,se,se,se,sw,se,se,ne,se,se,n,se,se,se,se,se,sw,se,se,se,nw,se,se,se,se,se,se,se,se,se,ne,se,se,se,se,se,se,se,se,se,se,se,n,se,ne,se,nw,se,ne,se,s,s,se,se,se,se,se,se,s,se,se,se,ne,se,se,nw,s,ne,se,s,ne,se,n,s,se,se,se,se,se,se,se,se,ne,se,se,se,se,se,se,se,n,ne,se,se,se,se,se,nw,se,ne,nw,se,se,se,ne,ne,se,se,nw,n,se,se,se,se,sw,se,nw,se,se,ne,se,se,se,se,sw,ne,se,n,se,se,se,se,n,se,se,se,ne,se,se,se,s,ne,se,se,sw,ne,se,se,se,ne,ne,n,n,s,se,ne,ne,sw,ne,n,se,ne,se,se,se,se,n,ne,sw,se,se,se,ne,se,n,nw,se,n,ne,ne,n,ne,ne,se,n,se,ne,s,se,ne,sw,se,s,se,ne,se,n,ne,ne,se,se,se,n,ne,sw,se,ne,sw,se,se,se,se,se,s,sw,ne,se,se,se,se,sw,se,se,se,se,sw,n,ne,n,se,se,s,ne,se,se,ne,ne,se,se,se,ne,se,ne,se,s,se,s,ne,se,n,n,se,se,nw,se,sw,se,n,s,se,se,sw,se,ne,ne,ne,s,se,se,ne,nw,se,ne,se,n,se,se,ne,ne,se,se,nw,se,ne,nw,ne,ne,ne,ne,ne,ne,ne,n,n,se,se,se,n,se,sw,se,n,se,ne,se,se,se,sw,se,ne,ne,ne,se,sw,se,se,n,se,se,ne,se,s,se,se,ne,ne,se,se,ne,se,se,ne,ne,ne,se,nw,se,se,se,ne,ne,se,se,s,nw,s,ne,se,se,se,se,ne,se,se,se,sw,ne,ne,ne,ne,ne,ne,ne,se,se,s,ne,s,se,se,nw,ne,sw,sw,ne,ne,se,ne,ne,se,se,ne,ne,ne,ne,sw,ne,ne,ne,ne,n,ne,ne,se,ne,sw,n,se,ne,ne,s,se,se,n,nw,se,ne,se,ne,ne,nw,ne,se,s,ne,ne,nw,se,ne,se,s,se,nw,ne,se,se,n,ne,se,ne,ne,se,se,sw,ne,se,ne,se,sw,se,n,ne,se,ne,se,ne,nw,ne,se,sw,ne,se,se,ne,sw,ne,ne,ne,ne,ne,ne,ne,n,ne,ne,n,ne,sw,ne,sw,ne,se,ne,ne,sw,ne,n,se,n,sw,ne,ne,s,ne,ne,ne,ne,ne,ne,ne,ne,ne,nw,se,ne,ne,ne,se,ne,s,n,ne,se,ne,ne,ne,ne,ne,ne,se,ne,ne,sw,ne,ne,se,n,ne,se,ne,ne,ne,nw,ne,ne,ne,ne,ne,ne,ne,ne,ne,ne,ne,ne,ne,nw,ne,ne,ne,nw,ne,nw,sw,ne,sw,ne,se,s,ne,ne,ne,ne,ne,ne,se,ne,n,ne,ne,ne,ne,ne,sw,ne,ne,ne,ne,ne,sw,nw,se,se,ne,ne,sw,ne,n,ne,ne,ne,ne,s,ne,ne,ne,ne,ne,ne,ne,ne,s,nw,ne,n,ne,ne,ne,s,ne,nw,ne,ne,ne,ne,ne,ne,ne,ne,ne,sw,ne,ne,ne,ne,n,ne,ne,ne,nw,ne,ne,ne,ne,ne,se,ne,se,ne,ne,ne,ne,ne,ne,ne,n,ne,ne,ne,ne,ne,ne,ne,ne,ne,ne,ne,ne,ne,ne,nw,ne,n,n,ne,n,ne,s,ne,ne,ne,ne,ne,n,ne,ne,ne,se,ne,s,sw,ne,ne,ne,ne,ne,ne,ne,n,ne,ne,n,n,ne,ne,sw,n,ne,nw,n,s,n,ne,nw,nw,ne,se,nw,sw,ne,ne,ne,ne,ne,ne,ne,ne,ne,ne,ne,se,ne,sw,n,ne,ne,n,ne,ne,ne,ne,ne,se,n,ne,s,ne,ne,ne,n,ne,ne,ne,ne,ne,s,ne,ne,nw,ne,ne,s,se,ne,ne,se,sw,s,ne,ne,ne,ne,ne,n,sw,nw,s,ne,n,ne,n,ne,ne,sw,ne,ne,ne,ne,se,n,ne,ne,ne,ne,ne,ne,ne,ne,sw,ne,n,n,s,nw,s,ne,n,n,ne,ne,sw,ne,ne,n,nw,n,nw,s,ne,se,ne,ne,n,ne,n,n,ne,ne,n,ne,sw,ne,n,n,s,ne,ne,n,nw,ne,n,ne,n,n,ne,n,ne,s,sw,n,ne,nw,n,ne,ne,ne,n,ne,nw,n,ne,ne,ne,n,ne,n,n,s,se,s,s,nw,ne,ne,ne,ne,ne,se,ne,se,ne,ne,s,n,n,ne,sw,n,ne,n,ne,ne,n,ne,ne,ne,n,ne,ne,ne,n,n,ne,n,ne,n,ne,ne,ne,n,sw,ne,n,ne,n,ne,n,ne,s,ne,n,nw,ne,ne,ne,n,ne,n,n,ne,sw,ne,ne,ne,ne,n,ne,n,s,ne,ne,n,ne,ne,n,ne,ne,n,ne,n,nw,s,ne,ne,n,n,ne,n,nw,n,s,ne,ne,n,se,n,s,n,ne,ne,ne,n,ne,ne,se,n,n,ne,ne,n,n,ne,ne,ne,ne,n,n,ne,n,n,n,s,se,n,n,n,n,ne,ne,ne,ne,ne,se,ne,n,n,s,ne,ne,n,ne,ne,s,se,ne,se,n,n,ne,ne,s,n,n,se,ne,s,ne,s,ne,sw,n,ne,n,n,s,ne,ne,ne,ne,ne,ne,n,n,ne,ne,n,ne,ne,se,s,n,ne,nw,n,ne,nw,n,ne,n,ne,n,n,ne,n,n,n,n,n,ne,n,n,ne,ne,n,n,se,sw,ne,ne,ne,nw,ne,n,sw,ne,s,ne,n,sw,ne,n,n,n,n,n,ne,ne,n,ne,ne,ne,n,n,ne,n,ne,n,ne,s,sw,n,n,ne,ne,ne,n,sw,s,ne,n,se,s,n,n,ne,n,se,n,ne,ne,sw,se,n,ne,n,ne,ne,n,n,n,ne,nw,ne,s,n,n,ne,ne,se,ne,se,nw,nw,nw,sw,n,ne,n,n,n,n,n,n,s,n,nw,n,ne,ne,n,ne,ne,n,ne,s,n,n,ne,sw,n,ne,n,n,n,ne,nw,n,ne,sw,n,n,n,ne,n,ne,n,ne,n,n,ne,n,n,s,n,ne,ne,se,ne,n,n,n,n,nw,n,n,n,n,n,s,n,n,n,n,n,n,ne,se,n,sw,n,n,n,n,ne,n,n,n,n,n,n,n,sw,n,ne,ne,s,n,n,ne,n,n,n,n,n,nw,n,sw,n,n,n,n,n,se,n,n,n,n,n,ne,n,n,n,s,n,n,ne,n,n,n,n,se,n,n,n,ne,n,n,n,n,n,n,n,ne,n,n,n,n,n,ne,s,n,se,n,n,n,n,ne,n,sw,n,n,nw,n,ne,n,se,n,ne,ne,n,n,ne,n,s,n,n,n,n,s,n,nw,n,n,n,nw,n,n,s,n,n,n,sw,n,n,n,ne,n,ne,n,s,n,n,n,n,ne,n,n,n,n,n,n,n,n,sw,n,n,n,s,n,s,nw,n,sw,n,se,se,nw,n,n,n,se,n,ne,n,n,ne,n,n,ne,n,ne,n,n,n,n,n,n,se,se,n,se,nw,s,n,n,sw,n,n,n,n,n,n,n,nw,n,nw,n,n,n,n,se,sw,n,n,n,n,n,n,s,n,n,s,n,n,n,n,n,n,n,se,n,n,n,n,n,se,n,n,n,n,ne,n,s,n,n,n,n,n,se,n,n,n,se,n,n,n,n,n,n,n,se,ne,n,n,n,n,n,n,n,n,nw,sw,n,se,n,se,n,se,nw,s,n,nw,sw,n,nw,se,n,nw,n,n,n,n,n,nw,ne,n,ne,n,n,n,n,n,sw,n,n,sw,nw,n,se,n,n,n,se,n,ne,ne,n,n,n,n,n,sw,n,n,n,n,nw,s,ne,n,sw,n,n,n,n,n,n,n,nw,n,n,nw,n,n,n,n,n,n,n,n,sw,ne,n,s,n,n,n,nw,n,nw,n,se,n,n,nw,n,n,n,n,nw,se,n,n,nw,ne,n,n,sw,sw,n,nw,n,se,n,n,se,n,n,n,n,ne,nw,nw,n,sw,nw,n,ne,ne,n,n,n,n,n,nw,n,n,n,n,nw,n,sw,sw,n,se,sw,n,nw,n,n,n,nw,nw,n,n,nw,n,nw,nw,nw,nw,n,n,n,n,n,nw,nw,nw,n,n,n,n,n,n,n,n,ne,nw,n,n,s,n,n,n,nw,nw,n,n,sw,n,n,n,n,n,n,n,n,se,ne,nw,n,nw,nw,s,s,nw,s,n,n,nw,nw,n,n,n,n,n,s,nw,n,ne,n,nw,s,n,nw,n,n,n,n,n,se,n,n,nw,n,n,nw,nw,n,n,nw,n,nw,n,nw,n,nw,nw,sw,n,nw,ne,n,n,n,n,n,n,n,sw,s,n,n,n,n,n,nw,nw,nw,nw,se,n,se,se,nw,nw,nw,nw,n,se,n,n,nw,nw,n,se,n,n,n,n,n,n,n,nw,nw,n,n,nw,s,ne,ne,n,n,n,n,s,nw,n,n,n,n,nw,sw,sw,nw,nw,nw,nw,nw,n,n,n,n,n,s,s,n,nw,n,n,n,n,n,nw,n,n,nw,nw,s,nw,n,n,nw,n,n,nw,nw,n,nw,n,nw,nw,sw,n,n,s,n,ne,n,s,n,n,n,n,nw,nw,n,n,n,n,n,nw,nw,n,nw,nw,n,nw,se,s,n,n,nw,sw,n,n,nw,nw,n,nw,n,s,nw,nw,nw,nw,ne,n,n,n,nw,n,n,s,nw,sw,sw,se,n,n,n,nw,se,nw,n,n,nw,nw,nw,n,nw,nw,ne,n,n,nw,n,n,nw,n,nw,n,ne,n,nw,se,sw,nw,nw,sw,n,n,n,n,n,n,n,n,n,n,n,n,nw,nw,se,n,nw,n,nw,nw,ne,ne,n,n,ne,nw,n,nw,nw,n,nw,n,n,nw,sw,nw,se,nw,sw,nw,nw,n,n,nw,n,nw,n,n,sw,sw,n,se,n,n,n,nw,n,n,nw,n,sw,se,sw,nw,n,sw,n,s,nw,nw,nw,n,n,nw,n,nw,nw,nw,nw,nw,nw,n,nw,nw,se,s,s,sw,n,nw,sw,nw,nw,n,n,n,nw,nw,nw,n,nw,nw,n,nw,nw,n,nw,nw,nw,nw,nw,nw,n,n,nw,nw,ne,s,nw,n,s,n,nw,nw,sw,nw,n,n,sw,nw,n,sw,ne,n,n,nw,se,sw,n,n,nw,n,ne,n,nw,se,s,s,n,nw,nw,n,nw,nw,n,n,n,n,sw,sw,nw,n,n,n,n,sw,s,se,n,nw,n,nw,nw,se,nw,n,ne,n,nw,n,ne,se,nw,nw,nw,n,sw,ne,n,n,nw,n,se,n,n,sw,nw,ne,n,nw,nw,nw,s,nw,nw,n,nw,ne,nw,nw,nw,n,se,nw,nw,n,nw,nw,nw,nw,n,nw,n,n,ne,n,sw,nw,n,n,nw,nw,nw,n,nw,s,n,nw,nw,nw,nw,se,n,n,nw,n,n,nw,s,ne,n,nw,n,s,se,nw,sw,nw,nw,nw,s,nw,nw,n,nw,n,se,s,nw,nw,nw,sw,n,nw,n,se,n,s,nw,nw,nw,n,nw,nw,n,n,sw,nw,nw,nw,n,nw,sw,nw,nw,s,se,nw,nw,nw,ne,s,nw,nw,nw,nw,nw,nw,nw,nw,nw,nw,n,n,nw,nw,nw,nw,nw,nw,n,nw,n,nw,nw,n,sw,nw,sw,nw,nw,n,n,n,nw,ne,nw,n,nw,nw,nw,n,nw,nw,nw,nw,nw,n,nw,n,nw,n,nw,n,nw,nw,nw,nw,nw,nw,nw,nw,ne,nw,nw,n,nw,sw,n,nw,nw,nw,nw,nw,nw,s,nw,nw,nw,nw,nw,nw,nw,nw,nw,nw,n,nw,nw,n,s,n,se,nw,nw,se,n,nw,ne,n,n,nw,nw,ne,nw,n,ne,nw,nw,n,n,ne,ne,sw,nw,nw,nw,n,sw,n,n,ne,nw,sw,nw,nw,nw,ne,se,sw,nw,ne,nw,nw,n,nw,nw,nw,nw,nw,ne,nw,n,s,nw,nw,nw,nw,nw,nw,ne,n,s,nw,n,nw,nw,s,n,nw,ne,s,nw,nw,nw,sw,nw,nw,nw,n,nw,nw,nw,n,n,nw,nw,nw,n,nw,n,sw,nw,nw,nw,nw,nw,n,n,nw,nw,nw,ne,s,nw,sw,nw,se,nw,nw,nw,n,nw,se,nw,ne,nw,nw,n,nw,se,nw,n,sw,sw,nw,se,nw,nw,nw,nw,n,nw,s,nw,n,nw,nw,se,nw,s,n,se,n,sw,nw,nw,nw,n,nw,ne,n,nw,nw,nw,nw,nw,nw,nw,nw,nw,nw,nw,nw,ne,nw,n,nw,nw,nw,s,sw,nw,nw,s,sw,nw,nw,nw,nw,nw,nw,nw,nw,n,se,nw,n,nw,nw,nw,nw,nw,nw,n,nw,nw,nw,nw,nw,sw,nw,se,nw,nw,nw,nw,nw,ne,nw,nw,nw,nw,nw,nw,nw,nw,nw,nw,nw,s,nw,nw,nw,n,nw,nw,ne,nw,nw,nw,nw,nw,se,nw,nw,nw,nw,nw,nw,nw,nw,nw,nw,nw,nw,nw,n,nw,se,nw,nw,n,s,s,nw,nw,n,nw,nw,nw,se,nw,nw,nw,ne,nw,se,nw,nw,nw,se,nw,nw,nw,s,se,n,nw,nw,nw,n,s,nw,nw,nw,nw,nw,n,nw,nw,ne,se,nw,nw,nw,nw,nw,nw,nw,nw,nw,ne,nw,ne,sw,sw,s,ne,nw,nw,nw,nw,n,nw,nw,se,nw,nw,nw,n,nw,nw,nw,nw,nw,nw,nw,s,sw,nw,nw,nw,nw,nw,n,nw,s,sw,nw,nw,nw,nw,nw,s,n,nw,nw,nw,nw,n,nw,nw,nw,nw,nw,sw,nw,sw,nw,se,sw,nw,ne,nw,sw,nw,ne,sw,nw,nw,nw,nw,nw,nw,sw,nw,nw,nw,sw,nw,sw,s,s,nw,nw,nw,nw,nw,nw,nw,nw,nw,nw,nw,nw,s,se,nw,nw,nw,nw,nw,n,ne,sw,nw,nw,nw,nw,nw,sw,nw,nw,ne,nw,nw,nw,nw,nw,nw,sw,nw,nw,nw,nw,sw,s,nw,nw,nw,ne,ne,nw,nw,nw,nw,nw,nw,sw,s,sw,se,nw,sw,ne,nw,nw,nw,nw,nw,nw,nw,nw,nw,nw,nw,nw,nw,sw,sw,nw,nw,nw,nw,s,sw,sw,se,se,nw,nw,s,nw,nw,sw,n,sw,sw,nw,sw,nw,nw,nw,nw,n,nw,nw,ne,nw,n,nw,nw,nw,sw,nw,ne,s,sw,s,nw,nw,nw,n,sw,nw,nw,nw,nw,nw,se,nw,sw,nw,nw,se,nw,nw,ne,sw,nw,nw,sw,nw,nw,nw,nw,sw,nw,sw,s,nw,nw,nw,sw,nw,nw,nw,nw,nw,nw,ne,nw,n,nw,nw,nw,nw,nw,nw,nw,se,s,n,s,s,ne,nw,sw,nw,nw,sw,nw,nw,nw,nw,nw,nw,sw,nw,se,nw,nw,nw,nw,se,nw,n,nw,n,sw,nw,nw,sw,nw,nw,nw,nw,nw,nw,se,nw,nw,nw,nw,nw,ne,nw,nw,nw,sw,nw,nw,nw,nw,nw,nw,nw,nw,nw,nw,sw,s,sw,nw,sw,nw,sw,nw,nw,nw,nw,nw,n,nw,nw,n,se,nw,sw,nw,nw,sw,se,s,nw,sw,sw,se,sw,nw,sw,sw,n,sw,nw,ne,nw,sw,nw,nw,sw,nw,sw,nw,nw,n,sw,sw,nw,nw,nw,sw,nw,sw,nw,n,nw,ne,nw,nw,nw,sw,s,nw,nw,se,n,nw,nw,nw,nw,sw,sw,ne,sw,nw,sw,nw,se,sw,nw,nw,nw,sw,n,sw,sw,sw,nw,ne,sw,sw,nw,nw,sw,se,nw,nw,se,nw,s,ne,sw,s,s,nw,nw,nw,nw,nw,nw,nw,n,nw,ne,sw,sw,sw,sw,s,sw,sw,nw,nw,nw,nw,nw,sw,ne,sw,nw,nw,ne,nw,sw,nw,nw,nw,sw,nw,nw,nw,nw,sw,nw,n,sw,nw,nw,nw,sw,s,sw,sw,nw,sw,n,nw,nw,nw,nw,nw,nw,nw,sw,nw,nw,sw,sw,nw,nw,nw,nw,s,sw,nw,s,n,nw,sw,sw,se,nw,nw,nw,nw,nw,nw,s,nw,nw,ne,nw,s,sw,sw,sw,nw,sw,sw,nw,nw,sw,se,sw,nw,nw,sw,sw,ne,nw,nw,nw,n,nw,sw,nw,nw,nw,nw,sw,sw,sw,nw,sw,sw,ne,nw,nw,nw,sw,nw,ne,sw,n,nw,nw,nw,nw,sw,nw,nw,sw,nw,nw,nw,sw,se,sw,nw,nw,nw,nw,nw,nw,sw,s,sw,sw,se,s,sw,ne,nw,ne,sw,sw,nw,nw,sw,sw,se,nw,n,nw,nw,nw,nw,sw,nw,ne,sw,n,sw,sw,sw,sw,se,se,sw,ne,sw,sw,nw,nw,sw,sw,sw,sw,nw,nw,nw,nw,sw,sw,nw,nw,sw,nw,nw,nw,nw,sw,sw,s,ne,sw,nw,sw,sw,sw,nw,n,nw,sw,nw,nw,nw,nw,sw,nw,sw,nw,nw,nw,se,sw,sw,sw,sw,s,ne,sw,sw,sw,sw,nw,sw,ne,ne,sw,nw,sw,nw,nw,se,sw,sw,nw,sw,nw,sw,n,sw,nw,nw,sw,sw,sw,sw,nw,sw,nw,sw,n,nw,s,sw,sw,sw,sw,sw,nw,se,s,sw,sw,sw,sw,sw,nw,sw,sw,nw,n,se,nw,sw,nw,nw,s,sw,nw,se,nw,sw,sw,s,s,nw,s,sw,nw,sw,nw,sw,sw,sw,sw,sw,nw,nw,nw,sw,sw,sw,n,s,se,sw,ne,s,sw,ne,sw,sw,nw,nw,sw,sw,sw,sw,sw,se,sw,nw,nw,se,sw,n,sw,s,nw,sw,sw,sw,nw,sw,se,ne,nw,sw,nw,sw,sw,sw,nw,sw,sw,sw,sw,nw,sw,sw,nw,nw,nw,n,sw,nw,nw,nw,s,nw,nw,nw,sw,s,se,sw,nw,sw,n,ne,se,nw,s,s,sw,se,s,sw,nw,sw,se,sw,sw,nw,nw,s,nw,n,nw,ne,nw,sw,sw,nw,sw,sw,n,nw,nw,s,ne,se,n,sw,n,nw,n,sw,ne,sw,nw,sw,sw,nw,ne,s,nw,nw,nw,nw,ne,sw,sw,se,nw,sw,sw,se,sw,nw,nw,sw,nw,sw,sw,nw,sw,sw,sw,sw,n,sw,nw,se,sw,s,ne,sw,sw,sw,sw,sw,se,sw,nw,ne,nw,sw,nw,ne,sw,se,sw,nw,nw,sw,nw,sw,ne,sw,ne,sw,nw,nw,nw,s,nw,n,sw,s,nw,nw,nw,nw,se,ne,sw,se,sw,sw,nw,sw,sw,nw,nw,ne,se,sw,nw,sw,se,nw,nw,nw,sw,s,sw,nw,sw,sw,nw,nw,sw,nw,nw,s,sw,sw,nw,sw,se,ne,sw,sw,se,s,nw,sw,sw,sw,nw,sw,nw,sw,sw,sw,nw,ne,nw,n,sw,se,n,sw,se,s,sw,nw,sw,sw,nw,s,sw,sw,nw,sw,sw,sw,ne,n,sw,s,ne,sw,sw,sw,sw,nw,sw,sw,sw,nw,sw,sw,sw,s,sw,sw,sw,nw,sw,sw,sw,sw,sw,nw,s,sw,nw,nw,n,sw,sw,sw,sw,nw,sw,sw,sw,sw,sw,sw,nw,nw,sw,nw,se,sw,nw,ne,nw,sw,nw,sw,sw,s,sw,nw,sw,sw,sw,nw,sw,sw,sw,nw,sw,nw,sw,ne,nw,ne,sw,nw,sw,sw,sw,nw,nw,nw,nw,sw,s,sw,nw,se,nw,sw,nw,sw,sw,sw,sw,sw,sw,sw,sw,nw,sw,s,nw,sw,sw,nw,nw,nw,sw,sw,sw,sw,sw,sw,ne,sw,se,sw,sw,nw,sw,ne,nw,sw,sw,nw,sw,n,s,nw,sw,sw,se,sw,n,nw,ne,nw,nw,sw,sw,sw,sw,sw,ne,ne,sw,sw,nw,nw,sw,nw,n,sw,sw,sw,nw,n,sw,n,sw,sw,s,nw,nw,ne,sw,sw,sw,sw,sw,sw,sw,sw,sw,sw,ne,nw,sw,s,sw,sw,s,nw,sw,sw,ne,nw,sw,sw,sw,nw,s,sw,sw,sw,sw,nw,sw,sw,sw,sw,nw,sw,sw,sw,sw,sw,sw,nw,sw,sw,nw,sw,sw,se,sw,sw,nw,sw,sw,se,se,sw,s,nw,sw,sw,nw,sw,se,sw,se,sw,s,sw,ne,nw,s,s,sw,sw,sw,sw,sw,sw,sw,nw,se,sw,s,sw,sw,sw,ne,sw,sw,nw,nw,nw,sw,nw,sw,s,sw,ne,sw,sw,sw,sw,nw,sw,sw,ne,nw,sw,nw,sw,sw,ne,sw,sw,sw,s,nw,sw,sw,nw,sw,sw,sw,sw,sw,ne,se,nw,sw,sw,s,n,ne,sw,sw,nw,sw,se,sw,sw,sw,sw,sw,ne,sw,sw,nw,sw,sw,sw,sw,sw,sw,sw,nw,sw,sw,sw,nw,sw,sw,sw,sw,nw,s,sw,se,sw,sw,sw,n,nw,sw,sw,sw,sw,sw,sw,sw,sw,sw,sw,sw,sw,ne,sw,sw,sw,sw,sw,sw,sw,nw,nw,sw,sw,se,se,s,sw,ne,sw,sw,n,s,sw,sw,sw,sw,sw,sw,sw,sw,ne,se,sw,sw,sw,sw,sw,sw,sw,sw,sw,sw,sw,sw,sw,sw,n,nw,sw,ne,sw,nw,sw,sw,nw,sw,sw,sw,sw,n,sw,sw,sw,sw,nw,sw,sw,s,sw,sw,sw,sw,nw,sw,sw,sw,sw,sw,sw,sw,sw,nw,sw,sw,sw,sw,sw,sw,sw,s,sw,sw,sw,sw,se,sw,sw,sw,ne,sw,sw,sw,sw,se,sw,sw,s,se,sw,sw,sw,n,sw,sw,sw,sw,sw,sw,n,sw,sw,sw,sw,sw,sw,sw,sw,sw,sw,ne,sw,sw,sw,sw,ne,sw,sw,sw,sw,sw,sw,sw,sw,sw,sw,sw,sw,sw,sw,sw,sw,s,sw,sw,nw,sw,sw,ne,n,sw,sw,sw,sw,sw,sw,n,sw,sw,sw,sw,sw,sw,sw,sw,nw,n,nw,n,sw,nw,ne,se,se,se,s,se,s,sw,s,nw,s,s,s,s,se,se,nw,sw,sw,sw,s,s,s,sw,sw,n,se,sw,s,sw,sw,sw,sw,sw,sw,nw,sw,sw,nw,sw,nw,s,sw,s,nw,s,nw,nw,nw,s,nw,nw,nw,nw,nw,nw,n,ne,nw,sw,nw,n,sw,nw,nw,n,n,nw,n,nw,n,n,nw,n,sw,n,sw,n,ne,n,n,n,n,n,sw,n,n,n,se,n,se,n,n,ne,n,ne,se,n,ne,n,n,n,n,n,nw,s,ne,ne,n,ne,se,ne,ne,ne,ne,s,ne,n,ne,ne,se,s,ne,ne,se,ne,ne,n,n,ne,sw,s,n,ne,ne,ne,ne,ne,ne,ne,ne,ne,n,ne,ne,ne,ne,ne,sw,se,nw,se,s,ne,se,ne,se,ne,ne,ne,se,sw,ne,ne,ne,s,nw,ne,se,ne,se,ne,s,se,ne,se,se,ne,se,se,se,ne,nw,ne,se,ne,sw,se,se,ne,se,nw,se,se,se,ne,se,se,se,n,ne,ne,se,se,se,ne,se,se,se,nw,se,se,se,se,se,se,se,se,se,se,se,sw,se,se,sw,se,s,se,se,se,se,se,se,se,se,ne,se,se,se,se,nw,s,s,ne,se,se,se,sw,s,nw,s,se,s,s,s,se,s,nw,se,sw,sw,s,se,se,s,se,se,nw,se,s,se,s,se,s,s,s,s,se,se,s,s,s,s,se,se,se,sw,s,s,s,ne,ne,s,sw,sw,s,s,s,s,nw,s,nw,se,ne,s,se,s,ne,s,s,s,s,s,s,s,sw,s,s,sw,s,se,se,s,s,s,s,s,nw,s,se,s,s,sw,s,s,s,s,s,s,s,sw,s,s,s,s,s,s,s,s,se,s,nw,s,sw,s,s,sw,s,s,se,s,s,sw,s,s,sw,sw,sw,sw,s,sw,n,n,sw,ne,sw,sw,s,sw,ne,s,sw,nw,nw,s,s,sw,sw,sw,s,s,sw,s,sw,sw,sw,s,se,nw,s,s,sw,s,sw,sw,s,nw,sw,s,s,sw,sw,sw,sw,s,s,sw,sw,ne,sw,sw,s,se,sw,n,sw,se,sw,sw,s,sw,sw,sw,se,sw,sw,sw,sw,sw,s,n,s,n,sw,sw,sw,sw,nw,sw,sw,nw,sw,s,sw,sw,nw,ne,sw,sw,sw,sw,sw,sw,se,n,sw,sw,sw,nw,sw,sw,sw,sw,nw,sw,s,sw,sw,sw,sw,sw,sw,sw,se,n,nw,sw,ne,nw,ne,sw,sw,nw,nw,nw,sw,sw,sw,sw,sw,sw,sw,nw,sw,sw,n,nw,sw,sw,nw,sw,sw,sw,se,nw,s,sw,nw,s,n,nw,sw,sw,s,sw,sw,ne,sw,sw,nw,sw,n,sw,se,sw,nw,nw,nw,sw,nw,sw,sw,sw,ne,sw,nw,sw,n,nw,nw,sw,sw,sw,nw,nw,se,nw,nw,sw,se,sw,sw,nw,sw,sw,sw,nw,sw,nw,nw,sw,sw,sw,sw,sw,nw,nw,se,sw,ne,nw,sw,sw,sw,nw,n,sw,nw,sw,nw,ne,nw,nw,s,nw,nw,nw,sw,s,sw,sw,sw,nw,nw,n,nw,nw,nw,nw,nw,sw,sw,nw,n,nw,sw,sw,sw,se,sw,sw,nw,ne,nw,nw,n,nw,nw,nw,nw,nw,sw,nw,nw,nw,ne,nw,ne,nw,nw,sw,sw,nw,nw,nw,nw,nw,sw,nw,nw,nw,nw,nw,ne,nw,nw,nw,nw,nw,sw,sw,nw,se,se,sw,nw,nw,nw,nw,s,nw,nw,nw,nw,nw,nw,nw,nw,nw,nw,sw,nw,ne,nw,nw,ne,nw,sw,nw,nw,nw,nw,nw,nw,ne,nw,nw,nw,nw,nw,sw,nw,nw,nw,nw,nw,nw,nw,nw,nw,nw,sw,nw,nw,nw,sw,n,nw,nw,n,nw,se,se,s,nw,nw,n,ne,nw,ne,nw,nw,n,nw,sw,nw,s,s,nw,nw,n,nw,nw,se,nw,n,n,nw,ne,n,nw,nw,n,n,n,sw,n,nw,nw,nw,nw,sw,n,se,nw,s,sw,n,nw,nw,n,nw,nw,nw,n,n,nw,ne,n,s,se,n,s,n,nw,n,se,ne,nw,sw,n,se,nw,nw,s,se,n,n,ne,sw,s,n,nw,nw,nw,sw,nw,n,nw,nw,s,nw,n,n,n,n,n,n,n,n,nw,n,s,nw,n,nw,n,n,nw,se,s,nw,n,ne,sw,nw,sw,nw,nw,nw,nw,n,n,nw,n,n,n,nw,n,n,s,n,sw,n,sw,ne,n,n,n,nw,nw,n,nw,n,nw,nw,n,nw,n,s,n,n,s,n,nw,sw,nw,sw,nw,n,se,nw,s,nw,s,n,se,n,nw,n,n,n,n,n,n,ne,n,ne,n,n,n,n,nw,nw,s,n,n,ne,n,ne,n,n,n,n,n,n,sw,nw,n,n,n,n,nw,n,n,nw,n,n,n,n,se,n,n,n,n,n,n,nw,n,n,n,ne,n,n,n,n,n,s,n,n,sw,n,n,n,se,n,n,se,n,sw,n,n,se,n,n,s,se,nw,n,n,n,n,n,n,n,n,n,n,ne,n,n,n,n,n,se,ne,n,n,n,n,n,n,n,n,ne,n,n,n,n,n,n,n,s,n,s,se,n,n,n,n,ne,ne,n,n,s,n,n,n,n,n,n,nw,n,n,ne,n,n,n,ne,n,n,sw,se,n,n,n,ne,s,n,ne,n,n,n,n,n,s,n,se,n,se,s,n,n,n,n,ne,n,n,n,n,sw,se,n,n,nw,sw,nw,ne,n,n,se,n,n,n,se,n,n,n,ne,n,n,sw,nw,n,n,ne,n,ne,ne,n,n,n,ne,n,n,n,sw,n,sw,se,n,n,ne,s,n,ne,ne,n,n,n,se,sw,n,n,ne,s,ne,ne,ne,ne,ne,n,n,n,n,n,n,nw,ne,n,n,n,ne,ne,ne,sw,n,n,n,n,n,n,ne,ne,n,n,n,n,n,n,ne,s,ne,ne,ne,n,ne,n,n,ne,ne,se,ne,n,nw,ne,ne,s,ne,ne,n,ne,n,n,ne,n,ne,n,n,ne,ne,ne,se,n,ne,ne,nw,ne,n,ne,ne,n,ne,n,ne,ne,n,se,n,n,ne,n,n,ne,ne,n,ne,n,ne,ne,nw,n,ne,ne,ne,n,ne,ne,ne,s,nw,ne,ne,n,ne,n,ne,n,ne,ne,ne,sw,s,n,ne,ne,ne,n,sw,ne,nw,se,nw,ne,ne,n,ne,n,ne,ne,ne,ne,ne,ne,sw,ne,ne,se,ne,n,ne,ne,n,n,ne,ne,ne,ne,ne,ne,n,ne,ne,n,ne,ne,ne,se,sw,sw,nw,ne,ne,n,ne,nw,ne,ne,ne,ne,ne,ne,se,nw,ne,ne,ne,ne,n,ne,ne,n,ne,ne,ne,n,sw,ne,ne,s,n,ne,nw,ne,n,ne,s,ne,ne,ne,ne,ne,ne,n,sw,ne,sw,sw,se,ne,n,ne,s,ne,ne,s,n,ne,ne,ne,ne,ne,n,ne,ne,ne,ne,ne,sw,ne,ne,ne,ne,ne,ne,sw,n,ne,ne,ne,se,n,ne,nw,ne,nw,se,ne,s,ne,ne,ne,ne,ne,ne,ne,ne,ne,ne,ne,ne,ne,s,ne,ne,s,ne,ne,ne,se,ne,ne,nw,ne,sw,n,ne,ne,se,ne,sw,se,ne,ne,ne,ne,ne,ne,ne,ne,ne,ne,ne,ne,ne,nw,ne,ne,ne,sw,ne,ne,ne,ne,ne,ne,ne,ne,s,ne,se,ne,ne,se,ne,ne,s,ne,ne,ne,ne,ne,ne,se,ne,ne,ne,sw,ne,ne,se,se,ne,ne,se,ne,se,nw,ne,ne,ne,ne,ne,se,ne,ne,ne,se,ne,ne,ne,ne,se,se,ne,se,ne,s,n,s,ne,ne,ne,ne,ne,ne,ne,ne,ne,ne,se,se,s,ne,n,se,ne,ne,ne,se,n,n,ne,se,nw,n,ne,ne,s,nw,ne,ne,se,ne,s,se,ne,se,ne,ne,ne,ne,ne,sw,n,ne,ne,ne,ne,ne,ne,ne,se,ne,ne,ne,s,ne,ne,ne,ne,se,se,se,ne,se,se,ne,ne,se,ne,ne,se,se,ne,ne,se,ne,s,ne,n,ne,ne,se,se,ne,n,ne,nw,se,ne,se,se,n,ne,s,se,ne,se,ne,se,se,se,se,se,se,sw,se,se,se,ne,sw,ne,ne,ne,ne,ne,nw,ne,se,s,se,ne,se,se,se,ne,sw,ne,se,ne,se,nw,se,ne,n,se,se,sw,ne,ne,se,sw,ne,se,se,se,se,ne,ne,ne,se,se,ne,se,ne,se,ne,se,se,se,se,n,n,se,se,ne,ne,se,se,se,se,ne,ne,s,s,ne,se,se,se,ne,sw,se,ne,se,sw,ne,ne,se,se,nw,se,ne,nw,ne,se,se,ne,se,se,ne,ne,se,se,sw,se,se,n,se,se,ne,se,ne,se,se,se,ne,se,n,se,se,ne,se,ne,ne,se,ne,se,se,se,se,s,se,sw,se,se,se,ne,se,ne,se,ne,ne,se,s,ne,ne,se,se,se,se,s,se,se,ne,se,ne,se,se,se,ne,se,s,ne,se,se,ne,se,ne,se,se,ne,se,se,n,se,s,ne,ne,se,se,ne,s,se,se,nw,n,ne,ne,se,ne,sw,ne,s,s,sw,sw,ne,se,se,n,nw,se,n,se,n,ne,se,ne,se,se,nw,ne,se,se,ne,nw,se,se,ne,se,sw,ne,ne,se,se,se,se,se,se,s,se,ne,se,se,se,nw,se,se,n,se,se,ne,sw,se,se,se,se,se,ne,se,nw,nw,ne,se,se,se,se,ne,s,se,se,sw,se,se,se,se,n,n,se,se,n,se,se,se,se,n,se,se,se,n,se,ne,se,ne,nw,se,n,se,ne,se,se,se,se,se,se,se,se,nw,se,se,se,n,se,se,se,se,ne,se,se,se,se,se,se,n,nw,ne,ne,se,se,ne,sw,se,sw,se,se,se,ne,se,n,n,nw,se,se,sw,n,se,s,s,se,se,se,se,se,se,nw,se,sw,ne,se,s,se,se,se,se,se,ne,se,s,se,n,se,se,se,se,se,se,ne,se,sw,se,sw,se,se,se,se,se,se,se,ne,s,se,se,n,n,se,se,se,se,se,se,se,se,se,se,nw,s,se,se,nw,se,n,se,nw,se,s,sw,se,se,se,nw,se,sw,se,se,s,ne,se,se,se,se,se,sw,se,se,se,se,se,se,se,se,ne,ne,se,nw,s,se,se,se,s,se,se,se,se,se,se,se,se,se,se,nw,s,n,se,se,se,se,nw,se,se,se,se,se,se,se,ne,se,se,se,se,s,se,se,se,sw,nw,se,se,se,n,se,ne,se,se,se,se,se,se,se,sw,n,se,se,se,se,se,se,se,se,se,se,se,se,ne,se,se,se,se,se,se,se,se,ne,se,se,se,se,se,se,se,s,ne,ne,ne,se,ne,s,se,se,se,s,se,s,se,s,se,se,se,se,se,s,se,s,nw,se,se,se,sw,ne,s,se,ne,se,se,se,s,se,se,s,s,se,s,se,se,sw,n,se,ne,s,s,se,s,se,se,nw,se,s,se,n,ne,se,se,se,se,s,se,se,s,s,s,se,se,sw,s,se,se,s,n,se,n,se,se,ne,s,ne,se,se,s,se,se,ne,s,sw,sw,s,se,s,se,nw,se,ne,se,se,se,n,se,s,nw,se,n,se,s,se,se,se,s,s,se,se,se,s,se,se,se,s,se,se,s,se,s,se,se,se,se,se,se,se,s,se,s,se,s,se,n,s,se,se,se,se,s,se,se,se,se,nw,s,n,s,se,s,se,s,se,s,se,se,se,s,se,s,s,s,se,s,se,se,se,ne,se,se,nw,se,s,se,se,se,s,s,s,se,se,s,sw,ne,se,s,s,se,se,s,se,se,s,se,nw,s,s,se,se,nw,s,se,s,se,se,se,s,se,se,nw,se,n,se,se,se,se,ne,se,se,n,se,s,s,s,s,se,se,s,s,s,s,se,n,se,s,s,se,se,s,sw,se,s,ne,n,s,se,sw,se,se,n,sw,se,ne,se,s,se,s,se,se,se,nw,ne,se,se,se,se,s,s,se,se,s,se,se,s,s,ne,nw,s,s,nw,sw,sw,s,se,sw,nw,se,se,s,se,sw,s,s,ne,se,s,s,se,se,s,se,se,sw,se,se,s,se,s,se,s,s,s,s,nw,s,s,s,se,se,s,se,se,s,s,se,se,s,s,se,s,s,s,n,s,se,se,s,n,sw,s,se,se,s,se,s,s,s,s,se,se,s,s,sw,s,se,s,sw,s,s,s,s,se,n,s,se,se,s,se,s,se,s,s,s,s,se,se,se,ne,s,s,s,s,se,s,s,s,ne,s,s,nw,s,s,s,se,se,se,s,s,s,s,s,s,s,s,se,nw,se,se,s,s,se,s,s,se,se,s,s,s,se,s,s,se,s,se,s,se,s,s,s,se,s,s,n,se,s,s,ne,s,s,s,se,s,s,s,s,n,s,se,n,sw,se,se,s,s,s,s,se,s,s,s,s,s,se,se,se,s,s,s,s,ne,ne,s,s,se,s,s,se,s,se,s,se,sw,s,s,se,s,s,se,nw,s,s,s,s,s,s,se,se,s,s,ne,s,s,s,s,s,se,s,ne,s,s,s,s,s,s,s,se,s,s,se,s,s,s,sw,nw,s,se,n,se,s,s,s,ne,ne,s,s,s,s,s,se,s,s,s,s,s,s,n,s,s,s,s,s,ne,s,n,s,se,s,s,s,se,s,s,s,sw,s,se,s,nw,s,se,se,s,sw,s,s,s,se,s,s,s,sw,nw,s,se,se,s,s,s,s,n,nw,sw,s,s,nw,sw,s,n,se,sw,se,s,ne,s,s,ne,s,s,s,s,s,s,se,s,s,sw,s,se,s,s,nw,s,s,s,s,s,s,sw,s,s,s,s,s,s,s,s,s,s,s,s"
  
  toHexDir :: String -> (Int,Int)
  toHexDir "n"  = (0, -1)
  toHexDir "ne" = (1,-1)
  toHexDir "se" = (1,0)
  toHexDir "s"  = (0,1)
  toHexDir "sw" = (-1,1)
  toHexDir "nw" = (-1,0)
  toHexDir s = error "invalid input"
  
  tupleAdd :: (Int,Int) -> (Int,Int) -> (Int,Int)
  tupleAdd (a,b) (c,d) = (a+c, b+d)
  
  tupleSize :: (Int,Int) -> Int
  tupleSize (a,b) = abs a + abs b
  
  solveParts :: Int -> (Int,Int)
  solveParts _ = (part1, part2)
    where
      dirs = splitOn "," input & map toHexDir
      part1 = foldl tupleAdd (0,0) dirs & tupleSize
      part2 = scanl tupleAdd (0,0) dirs & map tupleSize & maximum
  
  main = Aoc.timer solveParts
  