module type CapType = sig
    type t
    val zero : t
    val cap_max : t
    val add : t -> t -> t
    val sub : t -> t -> t
end ;;

module CapInt : CapType with type t = int = struct
    type t = int
    let zero = 0
    let cap_max = max_int
    let add = (+)
    let sub = (-)
end

module type S = sig
    type t
    type cap

    val create      : int -> int -> t
    val add_edge    : t -> int -> int -> cap -> t
    val get_edge    : t -> int -> int * int * cap * cap
    val edges       : t -> (int * int * cap * cap) array
    val change_edge : t -> int -> cap -> cap -> unit
    val flow        : t -> int -> int -> cap
end;;

module Mf_graph = struct
    module Make(Cap: CapType) : S with type cap = Cap.t = struct
        type cap = Cap.t

        type edge = { to_: int; rev: int; mutable cap : cap }
        type t = int * int * int list array * edge array

        let create n m =
            n, 0, Array.make n [], Array.init (m * 2) (fun _ -> { to_ = 0; rev = 0; cap = Cap.zero } )

        let get_edge (n, idx, g, pos) i =
            let _e = pos.(i * 2) in
            let _re = pos.(_e.rev) in
            _re.to_, _e.to_, Cap.add _e.cap _re.cap, _re.cap

        let edges ((n, idx, g, pos) as mf) =
            Array.init (idx / 2) (fun i -> get_edge mf i)

        let change_edge (n, idx, g, pos) i new_cap new_flow =
            let _e = pos.(i * 2) in
            let _re = pos.(_e.rev) in
            _e.cap <- Cap.sub new_cap new_flow;
            _re.cap <- new_flow

        let add_edge (n, idx, g, pos) from to_ cap =
            pos.(idx)     <- { to_ = to_;  rev = idx + 1; cap = cap  };
            pos.(idx + 1) <- { to_ = from; rev = idx;     cap = Cap.zero };
            g.(from) <- idx :: g.(from);
            g.(to_)  <- (idx + 1) :: g.(to_);
            n, idx + 2, g, pos

        let flow mf s t =
            let flow (n, idx, g, pos) s t flow_limit =
                let bfs () =
                    let level = Array.make n (-1) in
                    level.(s) <- 0;

                    let rec loop fq bq =
                        match fq with
                        | [] -> if bq = [] then level else loop (List.rev bq) []
                        | v :: vs -> (
                            let rec loop2 bq = function
                                | [] -> loop vs bq
                                | e :: es ->
                                        let e = pos.(e) in
                                        if e.cap = Cap.zero || level.(e.to_) >= 0 then loop2 bq es else (
                                            level.(e.to_) <- level.(v) + 1;
                                            if e.to_ = t then level else loop2 (e.to_ :: bq) es
                                        )
                            in
                            loop2 bq g.(v)
                        )
                    in
                    loop [ s ] []
                in
                let rec dfs level iter v up =
                    if v = s then up else
                        let level_v = level.(v) in
                        let rec loop res iis =
                            iter.(v) <- iis;
                            match iis with
                            | [] -> res
                            | i :: is ->
                                let e = pos.(i) in
                                if level_v <= level.(e.to_) || pos.(e.rev).cap = Cap.zero then loop res is else
                                    let d = dfs level iter e.to_ (min (Cap.sub up res) pos.(e.rev).cap) in
                                    if d <= Cap.zero then loop res is else (
                                        pos.(i).cap     <- Cap.add pos.(i).cap d;
                                        pos.(e.rev).cap <- Cap.sub pos.(e.rev).cap d;
                                        let res = Cap.add res d in
                                        if res = up then res else loop res is
                                    )
                        in
                        loop Cap.zero iter.(v)
                in
                let rec flow_loop flow =
                    if flow >= flow_limit then flow else
                        let level = bfs () in
                        if level.(t) = -1 then flow else
                            let iter = Array.copy g in
                            let rec loop flow =
                                if flow < flow_limit then (
                                    let f = dfs level iter t (Cap.sub flow_limit flow) in
                                    if f = Cap.zero then flow else
                                        loop (Cap.add flow f)
                                ) else flow
                            in
                            flow_loop (loop flow)
                in
                flow_loop Cap.zero

            in
            flow mf s t Cap.cap_max
    end
end;;

Scanf.scanf "%d %d" (fun n m ->
    let ss = Array.init n (fun _ -> Scanf.scanf " %s" (fun s -> s)) in

    let module MF = Mf_graph.Make (CapInt) in
    let mf = MF.create (n * m + 2) (n * m * 3) in
    let s = n * m in
    let t = n * m + 1 in
    let rec loop_y y mf =
        let rec loop_x x mf =
            if x = m then loop_y (y + 1) mf else
                let pivot = y * m + x in
                let mf = if ss.(y).[x] = '#' then mf else (
                    if (x + y) mod 2 <> 0 then MF.add_edge mf pivot t 1 else (
                        let mf = MF.add_edge mf s pivot 1 in
                        let mf = if y > 0     && ss.(y - 1).[x] = '.' then MF.add_edge mf pivot ((y - 1) * m + x) 1 else mf in
                        let mf = if y < n - 1 && ss.(y + 1).[x] = '.' then MF.add_edge mf pivot ((y + 1) * m + x) 1 else mf in
                        let mf = if x > 0     && ss.(y).[x - 1] = '.' then MF.add_edge mf pivot (y * m + x - 1)   1 else mf in
                        let mf = if x < m - 1 && ss.(y).[x + 1] = '.' then MF.add_edge mf pivot (y * m + x + 1)   1 else mf in
                        mf
                    )
                )
                in
                loop_x (x + 1) mf
        in
        if y = n then mf else loop_x 0 mf
    in
    let mf = loop_y 0 mf in
    let f = MF.flow mf s t in
    let ar = MF.edges mf in
    let map = Array.make_matrix n m ' ' in
    for y = 0 to n - 1 do
        for x = 0 to m - 1 do
            map.(y).(x) <- ss.(y).[x]
        done
    done;
    Array.iter (fun (from, to_, c1, c2) -> if c2 > 0 && from <> s && to_ <> t then (
        let prt p1 c1 p2 c2 =
            let prt2 p c =
                let y = p / m in
                let x = p mod m in
                map.(y).(x) <- c
            in
            prt2 p1 c1; prt2 p2 c2
        in
        if from + m = to_  then prt from 'v' to_ '^' else
        if to_  + m = from then prt from '^' to_ 'v' else
        if from + 1 = to_  then prt from '>' to_ '<' else
        if to_  + 1 = from then prt from '<' to_ '>'
    )) ar;
    Printf.printf "%d\n" f;
    Array.iter (fun arr ->
        Array.iter print_char arr;
        print_newline ()
    ) map
)

Measured memory_bytes: 13288