{-# LANGUAGE LambdaCase #-}
{-# LANGUAGE Strict #-}

module Main where

import Control.Lens
import Control.Monad
import qualified Data.ByteString.Char8 as BS
import qualified Data.Char as Char
import qualified Data.List as List
import qualified Data.Vector.Unboxed as VU
import qualified Data.Vector.Unboxed.Mutable as VUM

type Point = (Int, Int)

type Strawberry = Point

type LeftTop = Point

type RightBottom = Point

type Area = (LeftTop, RightBottom)

main :: IO ()
main = do
  h : w : _ <- BS.getLine <&> toListOf (unfolded (BS.readInt . BS.dropWhile Char.isSpace))
  ipts <- replicateM h BS.getLine
  let strawberries :: [Strawberry]
      strawberries = ipts ^.. (indexing each <.> indexing each) . filtered (== fromIntegral (Char.ord '#')) . asIndex
  let answer = solve ((0, 0), (h - 1, w - 1)) strawberries
  prettyPrint h w answer

solve :: Area -> [Strawberry] -> [Area]
solve _ [] = error "program error"
solve cake [_] = [cake]
solve cake strawberries@(a : b : _) =
  if a ^. _1 == b ^. _1
    then verticalSplit (a ^. _2) strawberries
    else horizontalSplit (a ^. _1) strawberries
  where
    horizontalSplit p ss =
      let (top, bottom) = List.partition (\s -> s ^. _1 <= p) ss
       in solve (cake & _2 . _1 .~ p) top <> solve (cake & _1 . _1 .~ p + 1) bottom
    verticalSplit p ss =
      let (left, right) = List.partition (\s -> s ^. _2 <= p) ss
       in solve (cake & _2 . _2 .~ p) left <> solve (cake & _1 . _2 .~ p + 1) right

prettyPrint :: Int -> Int -> [Area] -> IO ()
prettyPrint h w cakes =
  let nums :: [Int]
      nums = VU.toList $ VU.create $ do
        vec <- VUM.new (h * w)
        ifor_ cakes $ \i cake ->
          sequence
            [ VUM.write vec (w * h' + w') (i + 1)
              | h' <- [cake ^. _1 . _1 .. cake ^. _2 . _1],
                w' <- [cake ^. _1 . _2 .. cake ^. _2 . _2]
            ]
        pure vec
   in putStrLn $
        nums ^.. unfolded (\case [] -> Nothing; xs -> Just $ List.splitAt w xs)
          & each . each %~ show
          & each %~ unwords
          & unlines
