{-# LANGUAGE MultiWayIf #-}

module Main where

import           Control.Monad
import           Control.Monad.Extra
import qualified Data.Array as A
import qualified Data.Array.IO as AIO
import qualified Data.Array.Unboxed as AU
import           Data.Bits
import           Data.Bool
import qualified Data.ByteString as BS
import qualified Data.ByteString.Char8 as BSC8
import           Data.Char
import           Data.Either
import           Data.Function
import qualified Data.Graph.Inductive.Graph as G
import qualified Data.Graph.Inductive.PatriciaTree as G
import qualified Data.Heap as H
import           Data.Int
import           Data.List
import qualified Data.Map.Strict as M
import           Data.Maybe
import           Data.Monoid
import           Data.Ord
import qualified Data.Sequence as SQ
import qualified Data.Set as S
import           Data.Tuple
import qualified Data.Vector as V
import           Data.Vector.Algorithms.Search
import qualified Data.Vector.Mutable as VM
import qualified Data.Vector.Unboxed as VU
import qualified Data.Vector.Unboxed.Mutable as VUM
import           Debug.Trace
import           GHC.Base

main = do
  --aN       <- getI
  --[aA, aB] <- getIL
  --aS       <- getLine
  [aN, aM] <- getIL
  graphIniData <- aclMaxFlowGraph $ (aN * aM + 2 :: Int)
  let s = aN * aM
  let t = aN * aM + 1
  grid <- V.replicateM aN getVUC
  graphIniDataAdd1 <- VU.foldM
    (\acc1 i -> VU.foldM
       (\acc2 j -> let v = i * aM + j
                   in if grid V.! i VU.! j == '#'
                      then return acc2
                      else if even (i + j)
                           then do
                             (m, ret) <- aclMaxFlowAddEdge acc2 s v 1
                             return ret
                           else do
                             (m, ret) <- aclMaxFlowAddEdge acc2 v t 1
                             return ret)
       acc1
       (VU.enumFromN 0 aM))
    graphIniData
    (VU.enumFromN 0 aN)
    :: IO (Int, VM.IOVector (SQ.Seq (Int, Int, Int)), SQ.Seq (Int, Int))
  graphIniDataAdd2@(_, _, pos1) <- VU.foldM
    (\acc1 i -> VU.foldM
       (\acc2 j
        -> let v0 = i * aM + j
           in VU.foldM
                (\acc3 k@(ky, kx)
                 -> let v1 = kx + (ky * aM)
                    in if odd (i + j) || grid V.! i VU.! j == '#'
                       then return acc3
                       else if grid V.! ky VU.! kx == '.'
                            then do
                              (m, ret) <- aclMaxFlowAddEdge acc3 v0 v1 1
                              return ret
                            else return acc3)
                acc2
              $ aroundSquare i j aN aM)
       acc1
       (VU.enumFromN 0 aM))
    graphIniDataAdd1
    (VU.enumFromN 0 aN)
  graphData@(_, graph, pos2) <- aclMaxFlowConvertIniData graphIniDataAdd2
  {-
  print "graph1"
  V.imapM_
    (\i x -> do
       fx <- VU.freeze x
       print $ show i ++ ":" ++ show fx)
    =<< (V.freeze graph)
    -}
  flow <- aclMaxFlowFlow graphData s t
  print flow
  {-
  print "graph2"
  V.imapM_
    (\i x -> do
       fx <- VU.freeze x
       print $ show i ++ ":" ++ show fx)
    =<< (V.freeze graph)
  -}
  edges <- aclMaxFlowEdges graphData
  --print edges
  --print =<< VU.freeze pos2
  newGrid <- V.thaw =<< (V.generateM aN $ \i -> VU.thaw $ grid V.! i)
  VU.mapM_
    (\e@(from, to, cap, flow) -> do
       if from == s || to == t || flow == 0
         then return ()
         else do
           let i0 = div from aM
               j0 = mod from aM
               i1 = div to aM
               j1 = mod to aM
           newGridI0 <- VM.unsafeRead newGrid i0
           newGridI1 <- VM.unsafeRead newGrid i1
           if
             | i0 == i1 + 1 -> do
               VUM.unsafeWrite newGridI1 j1 'v'
               VUM.unsafeWrite newGridI0 j0 '^'
             | j0 == j1 + 1 -> do
               VUM.unsafeWrite newGridI1 j1 '>'
               VUM.unsafeWrite newGridI0 j0 '<'
             | i0 == i1 - 1 -> do
               VUM.unsafeWrite newGridI0 j0 'v'
               VUM.unsafeWrite newGridI1 j1 '^'
             | otherwise -> do
               VUM.unsafeWrite newGridI0 j0 '>'
               VUM.unsafeWrite newGridI1 j1 '<')
    edges
  V.mapM_ (\newGridI -> putStrLn =<< VU.toList <$> VU.freeze newGridI)
    =<< V.freeze newGrid
  return ()

--雑多系
t :: Int -> (Int, Int)
t x = (x, 1)

i def f t = bool t def $ f t

shiftRCnt k = shiftRCntP k 1

shiftRCntP k c = let nk = shiftR k 1
                 in if nk == 0
                    then c
                    else shiftRCntP nk (c + 1)

myVUmap f vu =
  if vu == VU.empty
  then VU.empty
  else VU.unfoldr
    (\x -> let ret = f $ VU.head x
               tailx = VU.tail x
           in if x == VU.empty
              then Nothing
              else if isLeft ret
                   then Just (either id id ret, tailx)
                   else Just (either id id ret, VU.empty))
    vu

myVUmapM f vu =
  if vu == VU.empty
  then return VU.empty
  else VU.unfoldrM
    (\x -> do
       ret <- f $ VU.head x
       let tailx = VU.tail x
       if x == VU.empty
         then return Nothing
         else if isLeft ret
              then return $ Just (either id id ret, tailx)
              else return $ Just (either id id ret, VU.empty))
    vu

myVUmapM_ f vu =
  if vu == VU.empty
  then return ()
  else do
    ret1 <- VU.unfoldrM
      (\x -> do
         ret2 <- f $ VU.head x
         let tailx = VU.tail x
         if x == VU.empty
           then return Nothing
           else if isLeft ret2
                then return $ Just (either id id ret2, tailx)
                else return $ Just (either id id ret2, VU.empty))
      vu
    return ()

myVUfor vu f = myVUmap f vu

myVUforM vu f = myVUmapM f vu

myVUforM_ vu f = myVUmapM_ f vu

myVUfoldl f acc vu =
  if vu == VU.empty
  then return acc
  else do
    let ret = f acc (VU.head vu)
    if isLeft ret
      then myVUfoldl f (either id id ret) (VU.tail vu)
      else return $ either id id ret

myVUfoldr f acc vu =
  if vu == VU.empty
  then return acc
  else do
    let ret = f acc (VU.last vu)
    if isLeft ret
      then myVUfoldr f (either id id ret) (VU.init vu)
      else return $ either id id ret

myVUfoldM f acc vu =
  if vu == VU.empty
  then return acc
  else do
    ret <- f acc (VU.head vu)
    if isLeft ret
      then myVUfoldM f (either id id ret) (VU.tail vu)
      else return $ either id id ret

--周りのマス
aroundSquare y x h w = VU.concatMap
  (\a -> VU.mapMaybe
     (\b -> let ya = y + a
                xb = x + b
            in if abs a + abs b == 1
               then if ya < 0 || ya >= h || xb < 0 || xb >= w
                    then Nothing
                    else Just (ya, xb)
               else Nothing)
   $ VU.enumFromN (-1) 3)
  $ VU.enumFromN (-1) 3

--入力系
splitReadBSC8 :: BSC8.ByteString -> [Int]
splitReadBSC8 bs = let (bs1, newBs) = BSC8.splitAt 1 bs
                   in if newBs == BSC8.empty
                      then [test $ BSC8.readInt bs1]
                      else test (BSC8.readInt bs1):splitReadBSC8 newBs
  where
    test (Just (i, _)) = i

read2DimChar :: VM.IOVector (VUM.IOVector Char) -> Int -> Int -> IO Char
read2DimChar vec y x = do
  vecY <- VM.unsafeRead vec y
  VUM.unsafeRead vecY x

write2DimChar :: VM.IOVector (VUM.IOVector Char) -> Int -> Int -> Char -> IO ()
write2DimChar vec y x t = do
  vecY <- VM.unsafeRead vec y
  VUM.unsafeWrite vecY x t

readTwoDimVec :: VM.IOVector (VUM.IOVector Int) -> Int -> Int -> IO Int
readTwoDimVec vec y x = do
  vecY <- VM.unsafeRead vec y
  VUM.unsafeRead vecY x

writeTwoDimVec :: VM.IOVector (VUM.IOVector Int) -> Int -> Int -> Int -> IO ()
writeTwoDimVec vec y x t = do
  vecY <- VM.unsafeRead vec y
  VUM.unsafeWrite vecY x t

getVUI :: IO (VU.Vector Int)
getVUI = VU.unfoldr (BSC8.readInt . BSC8.dropWhile isSpace) <$> BSC8.getLine

getRepVUI :: Int -> IO (VU.Vector Int)
getRepVUI n = VU.unfoldr (BSC8.readInt . BSC8.dropWhile isSpace) . BSC8.unlines
  <$> replicateM n BSC8.getLine

getVS :: IO (V.Vector Char)
getVS = V.fromList <$> getLine

getVUC :: IO (VU.Vector Char)
getVUC = VU.fromList <$> getLine

readI :: BSC8.ByteString -> Int
readI = fst . fromJust . BSC8.readInt

readInteger :: BSC8.ByteString -> Integer
readInteger = fst . fromJust . BSC8.readInteger

readIL :: BSC8.ByteString -> [Int]
readIL = map readI . BSC8.words

readIT2 :: BSC8.ByteString -> (Int, Int)
readIT2 bs = let words = BSC8.words bs
             in (readI $ head words, readI $ last words)

readIT3 :: BSC8.ByteString -> (Int, Int, Int)
readIT3 bs = let words = BSC8.words bs
             in (readI $ head words, readI $ words !! 1, readI $ words !! 2)

getI :: IO Int
getI = readI <$> BSC8.getLine

getInteger :: IO Integer
getInteger = readInteger <$> BSC8.getLine

getIL :: IO [Int]
getIL = readIL <$> BSC8.getLine

getIT2 :: IO (Int, Int)
getIT2 = readIT2 <$> BSC8.getLine

getIT3 :: IO (Int, Int, Int)
getIT3 = readIT3 <$> BSC8.getLine

getIT2Order :: IO (Int, Int)
getIT2Order = getIL
  >>= \x@[xz, xo] -> if xz > xo
                     then return (xo, xz)
                     else return (xz, xo)

getNIS :: Int -> IO [(Int, BSC8.ByteString)]
getNIS 0 = return []
getNIS n = do
  [aFst, aSnd] <- BSC8.words <$> BSC8.getLine
  next <- getNIS (n - 1)
  return ((readI aFst, aSnd):next)

il2Words :: [Int] -> String
il2Words = unwords . map show

il2Lines :: [Int] -> String
il2Lines = unlines . map show

---MaxFlow
{-aclMaxFlowGraph n = (,,) n <$> VM.replicateM n (VUM.replicate 0 (0, 0, 0))
  <*> VU.thaw VU.empty
-}
aclMaxFlowGraph
  :: Int -> IO (Int, VM.IOVector (SQ.Seq (Int, Int, Int)), SQ.Seq (Int, Int))
aclMaxFlowGraph n = do
  graphIni <- VM.replicate n (SQ.empty)
  return (n, graphIni, SQ.empty)

aclMaxFlowAddEdge
  :: (Int, VM.IOVector (SQ.Seq (Int, Int, Int)), SQ.Seq (Int, Int))
  -> Int
  -> Int
  -> Int
  -> IO (Int, (Int, VM.IOVector (SQ.Seq (Int, Int, Int)), SQ.Seq (Int, Int)))
aclMaxFlowAddEdge graphIniData@(iniN, iniGraph, iniPos) from to cap = if
  | from < 0 || iniN <= from -> error
    "aclMaxFlowAddEdge:fromを0以上nより小さい値になるように見直してください。"
  | to < 0 || iniN <= to -> error
    "aclMaxFlowAddEdge:toを0以上nより小さい値になるように見直してください。"
  | cap < 0 -> error
    "aclMaxFlowAddEdge:capを0以上の値になるように見直してください。"
  | otherwise -> do
    let m = SQ.length iniPos
    graphFrom <- VM.unsafeRead iniGraph from
    graphTo <- VM.unsafeRead iniGraph to
    let graphFromSize = SQ.length graphFrom
    let graphToSize = SQ.length graphTo
    VM.unsafeWrite iniGraph from (graphFrom SQ.|> (to, graphToSize, cap))
    VM.unsafeWrite iniGraph to (graphTo SQ.|> (from, graphFromSize, 0))
    return (m, (iniN, iniGraph, iniPos SQ.|> (from, graphFromSize)))

aclMaxFlowConvertIniData
  :: (Int, VM.IOVector (SQ.Seq (Int, Int, Int)), SQ.Seq (Int, Int))
  -> IO
    (Int, VM.IOVector (VUM.IOVector (Int, Int, Int)), VUM.IOVector (Int, Int))
aclMaxFlowConvertIniData graphIniData@(iniN, iniGraph, iniPos) = do
  graph <- V.thaw
    =<< (V.generateM
           iniN
           (\i -> do
              seq <- VM.unsafeRead iniGraph i
              VU.thaw
                $ VU.unfoldr
                  (\x -> let (s SQ.:< sn) = SQ.viewl x
                         in if x == SQ.empty
                            then Nothing
                            else Just (s, sn))
                  seq))
  pos <- VU.thaw
    $ VU.unfoldr
      (\x -> let (s SQ.:< sn) = SQ.viewl x
             in if x == SQ.empty
                then Nothing
                else Just (s, sn))
      iniPos
  return (iniN, graph, pos)

                                                                                     --TODO:可変長の可変データどうやって持とう？時間かかりすぎなので最後に見直す。
                                                                                     {-aclMaxFlowAddEdge graphData from to cap =
  aclMaxFlowAddAllEdges graphData $ VU.singleton (from, to, cap)

bkaclMaxFlowAddAllEdges graphData@(n, graph, pos) edges = do
  (addPos, addGraphMap) <- VU.foldM
    (\acc@(accPos, accGraphMap) edge@(from, to, cap) -> if
       | from < 0 || n <= from -> error
         "aclMaxFlowAddEdge:fromを0以上nより小さい値になるように見直してください。"
       | to < 0 || n <= to -> error
         "aclMaxFlowAddEdge:toを0以上nより小さい値になるように見直してください。"
       | cap < 0 -> error
         "aclMaxFlowAddEdge:capを0以上の値になるように見直してください。"
       | otherwise -> do
         gFrom <- VM.unsafeRead graph from
         gTo <- VM.unsafeRead graph to
         let gFromSize = VUM.length gFrom
             gToSize = VUM.length gTo
             accGFrom = M.findWithDefault [] from accGraphMap
             accGTo = M.findWithDefault [] to accGraphMap
             accGFromSize = length accGFrom
             accGToSize = length accGTo
             sumGFromSize = gFromSize + accGFromSize
             sumGToSize = gToSize + accGToSize
         return
           ( (from, sumGFromSize):accPos
           , M.insert
               to
               ((from, sumGFromSize, 0):accGTo)
               (M.insert from ((to, sumGToSize, cap):accGFrom) accGraphMap)))
    ([], M.empty)
    edges
  nGraph <- V.thaw
    =<< V.mapM
      (\i -> do
         oGraph <- VU.freeze =<< VM.unsafeRead graph i
         let nGraph = oGraph
               VU.++ (VU.fromList
                      $ reverse (M.findWithDefault [] i addGraphMap))
         VU.thaw nGraph)
      (V.enumFromN 0 n)
  nPos <- VU.thaw =<< ((VU.++ VU.fromList addPos) <$> VU.freeze pos)
  return (n, nGraph, nPos)
-}
aclMaxFlowGetEdge graphData@(n, graph, pos) i =
  let m = VUM.length pos
  in if i < 0 || m <= i
     then error
       "aclMaxFlowAddEdge:iを0以上mより小さい値になるように見直してください。"
     else do
       posi <- VUM.unsafeRead pos i
       graphi <- VM.unsafeRead graph (fst posi)
       e@(eTo, eRev, eCap) <- VUM.unsafeRead graphi (snd posi)
       graphTo <- VM.unsafeRead graph eTo
       re@(reTo, reRev, reCap) <- VUM.unsafeRead graphTo eRev
       return (fst posi, eTo, eCap + reCap, reCap)

aclMaxFlowEdges graphData@(n, graph, pos) =
  let m = VUM.length pos
  in VU.mapM (aclMaxFlowGetEdge graphData) $ VU.enumFromN 0 m

aclMaxFlowChangeEdge graphData@(n, graph, pos) i newCap newFlow = do
  let m = VUM.length pos
  if i < 0 || m <= i
    then error
      "aclMaxFlowAddEdge:iを0以上mより小さい値になるように見直してください。"
    else do
      posi <- VUM.unsafeRead pos i
      graphA <- VM.unsafeRead graph (fst posi)
      e@(eTo, eRev, eCap) <- VUM.unsafeRead graphA (snd posi)
      graphB <- VM.unsafeRead graph eTo
      re@(reTo, reRev, reCap) <- VUM.unsafeRead graphB eRev
      return ()

aclMaxFlowFlow graphData@(n, graph, pos) s t =
  aclMaxFlowFlowLimit graphData s t maxInt

aclMaxFlowFlowLimit graphData@(n, graph, pos) s t flowLimit
  | s < 0 || n <= s = error
    "aclMaxFlowFlow:sを0以上nより小さい値になるように見直してください。"
  | t < 0 || n <= t = error
    "aclMaxFlowFlow:tを0以上nより小さい値になるように見直してください。"
  | otherwise = do
    levelIni <- VUM.new n :: IO (VUM.IOVector Int)
    iter <- VUM.new n :: IO (VUM.IOVector Int)
    aloop graph levelIni iter 0
  where
    aloop graph levelIni iter flow =
      if flow >= flowLimit
      then return flow
      else do
        VUM.set levelIni (-1)
        VUM.unsafeWrite levelIni s 0
        level <- bfs graph levelIni (SQ.singleton s)
        levelt <- VUM.unsafeRead level t
        if levelt == -1
          then return flow
          else do
            VUM.set iter 0
            nFlow <- bloop graph level iter flow
            aloop graph levelIni iter nFlow

    bfs graph level sq
      | sq == SQ.empty = return level
      | otherwise = do
        let (sqh SQ.:< sqt) = SQ.viewl sq
        edges <- VM.unsafeRead graph sqh
        nSq <- cloop level edges 0 sqh sqt
        bfs graph level nSq

    cloop level edges i v sqt = do
      if i >= VUM.length edges
        then return sqt
        else do
          edge@(to, rev, cap) <- VUM.unsafeRead edges i
          levelTo <- VUM.unsafeRead level to
          if cap == 0 || levelTo >= 0
            then cloop level edges (i + 1) v sqt
            else do
              levelv <- VUM.unsafeRead level v
              VUM.unsafeWrite level to (levelv + 1)
              if to == t
                then return SQ.empty
                else cloop level edges (i + 1) v (to SQ.<| sqt)

    bloop graph level iter flow
      | flow >= flowLimit = return flow
      | otherwise = do
        f <- if t == s
             then return (flowLimit - flow)
             else do
               levelV <- VUM.unsafeRead level t
               graphV <- VM.unsafeRead graph t
               dfs graph graphV level 0 levelV t iter (flowLimit - flow) 0
        if f == 0
          then return flow
          else bloop graph level iter (flow + f)

    dfs graph graphV level i levelV v iter up res = do
      let lenGraphV = VUM.length graphV
      if i >= lenGraphV
        then return res
        else do
          edge@(to, rev, cap) <- VUM.unsafeRead graphV i
          levelTo <- VUM.unsafeRead level to
          graphTo <- VM.unsafeRead graph to
          graphToRev@(nTo, nRev, nCap) <- VUM.unsafeRead graphTo rev
          if levelV <= levelTo || nCap == 0
            then do
              VUM.modify iter succ v
              dfs graph graphV level (i + 1) levelV v iter up res
            else do
              d <- if to == s
                   then do
                     return (min (up - res) nCap)
                   else do
                     ni <- VUM.unsafeRead iter to
                     dfs
                       graph
                       graphTo
                       level
                       ni
                       levelTo
                       to
                       iter
                       (min (up - res) nCap)
                       0
              if d <= 0
                then do
                  VUM.modify iter succ v
                  dfs graph graphV level (i + 1) levelV v iter up res
                else do
                  edge@(to2, rev2, cap2) <- VUM.unsafeRead graphV i
                  graphToRev@(nTo2, nRev2, nCap2) <- VUM.unsafeRead graphTo rev
                  VUM.unsafeWrite graphV i (to2, rev2, cap2 + d)
                  VUM.unsafeWrite graphTo rev (nTo2, nRev2, nCap2 - d)
                  let nres = res + d
                  if nres == up
                    then do
                      VUM.modify iter succ v
                      return nres
                    else do
                      VUM.modify iter succ v
                      dfs graph graphV level (i + i) levelV v iter up nres

aclMaxFlowMinCut graphData@(n, graph, pos) s = do
  visited <- VUM.replicate n False
  let sq = SQ.singleton s
  aloop visited sq
  VU.freeze visited
  where
    aloop visited sq
      | sq == SQ.empty = return ()
      | otherwise = do
        let (sqh SQ.:< sqt) = SQ.viewl sq
        VUM.unsafeWrite visited sqh True
        edges <- VM.unsafeRead graph sqh
        bloop visited edges 0 sq

    bloop visited edges i sq = do
      edge@(to, rev, cap) <- VUM.unsafeRead edges i
      visitedTo <- VUM.unsafeRead visited to
      if cap /= 0 && visitedTo == False
        then do
          VUM.unsafeWrite visited to True
          bloop visited edges i (to SQ.<| sq)
        else bloop visited edges i sq
---MinCostFlow後回し
---Convolution

Measured memory_bytes: 28060