AtCoder Library Practice Contest - Maxflow

You are given a grid of N rows and M columns. The square at the i-th row and j-th column will be denoted as (i,j). Some of the squares contain an object. All the remaining squares are empty. The state of the grid is represented by strings S_1,S_2,\cdots,S_N. The square (i,j) contains an object if S_{i,j}= `#` and is empty if S_{i,j}= `.`.

Consider placing 1 \times 2 tiles on the grid. Tiles can be placed vertically or horizontally to cover two adjacent empty squares. Tiles must not stick out of the grid, and no two different tiles may intersect. Tiles cannot occupy the square with an object.

Calculate the maximum number of tiles that can be placed and any configulation that acheives the maximum.

Constraints

* 1 \leq N \leq 100
* 1 \leq M \leq 100
* S_i is a string with length M consists of `#` and `.`.

Input

Input is given from Standard Input in the following format:


N M
S_1
S_2
\vdots
S_N


Output

On the first line, print the maximum number of tiles that can be placed.

On the next N lines, print a configulation that achieves the maximum. Precisely, output the strings t_1,t_2,\cdots,t_N constructed by the following way.

* t_i is initialized to S_i.
* For each (i,j), if there is a tile that occupies (i,j) and (i+1,j), change t_{i,j}:=`v`, t_{i+1,j}:=`^`.
* For each (i,j), if there is a tile that occupies (i,j) and (i,j+1), change t_{i,j}:=`>`, t_{i,j+1}:=`<`.



See samples for further information.

You may print any configulation that maximizes the number of tiles.

Examples

Input

3 3
#..
..#
...


Output

3
#><
vv#
^^.


Input

3 3
..
..#
...


Output

3
><
vv#
^^.

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
(N, M) = map(int, input().split())
S = [input() for i in range(N)]
P = N * M + 2
(src, dst) = (N * M, N * M + 1)
es = [[] for i in range(P)]
pos = []

def add_edge(fr, to, cap):
	pos.append((fr, len(es[fr])))
	es[fr].append([to, cap, len(es[to])])
	es[to].append([fr, 0, len(es[fr]) - 1])
for (i, row) in enumerate(S):
	for (j, c) in enumerate(row):
		if c == '#':
			continue
		if (i + j) % 2 == 0:
			add_edge(src, i * M + j, 1)
		else:
			add_edge(i * M + j, dst, 1)
for (i, row) in enumerate(S):
	for (j, c) in enumerate(row):
		if c == '#' or (i + j) % 2:
			continue
		v = i * M + j
		if i and S[i - 1][j] == '.':
			add_edge(v, (i - 1) * M + j, 1)
		if j and S[i][j - 1] == '.':
			add_edge(v, i * M + j - 1, 1)
		if i + 1 < N and S[i + 1][j] == '.':
			add_edge(v, (i + 1) * M + j, 1)
		if j + 1 < M and S[i][j + 1] == '.':
			add_edge(v, i * M + j + 1, 1)
INF = float('inf')
level = [0] * P
iters = [0] * P
from collections import deque

def dinic_max_flow(s, t):
	global iters

	def _bfs(s):
		global level
		level = [-1] * P
		level[s] = 0
		q = deque([s])
		while q:
			v = q.popleft()
			for (to, cap, rev) in es[v]:
				if cap > 0 and level[to] < 0:
					level[to] = level[v] + 1
					q.append(to)

	def _dfs(v, t, f):
		if v == t:
			return f
		for i in range(iters[v], len(es[v])):
			iters[v] += 1
			(to, cap, rev) = es[v][i]
			if es[v][i][1] > 0 and level[v] < level[to]:
				d = _dfs(to, t, min(f, es[v][i][1]))
				if d > 0:
					es[v][i][1] -= d
					es[to][rev][1] += d
					return d
		return 0
	flow = 0
	while True:
		_bfs(s)
		if level[t] < 0:
			return flow
		iters = [0] * P
		f = 0
		while True:
			f = _dfs(s, t, INF)
			if f <= 0:
				break
			flow += f
print(dinic_max_flow(src, dst))
ans = [list(row) for row in S]
for (fr, i) in pos:
	if fr == src:
		continue
	(to, cap, rev) = es[fr][i]
	if to == dst:
		continue
	flow = es[to][rev][1]
	if flow == 0:
		continue
	(i0, j0) = divmod(fr, M)
	(i1, j1) = divmod(to, M)
	if i0 == i1 + 1:
		ans[i1][j1] = 'v'
		ans[i0][j0] = '^'
	elif j0 == j1 + 1:
		ans[i1][j1] = '>'
		ans[i0][j0] = '<'
	elif i0 == i1 - 1:
		ans[i0][j0] = 'v'
		ans[i1][j1] = '^'
	else:
		ans[i0][j0] = '>'
		ans[i1][j1] = '<'
for row in ans:
	print(''.join(row))


from collections import deque

class mf_graph:
	__slots__ = ['N', 'graph', 'capacities', 'level', 'it']

	def __init__(self, N):
		self.N = N
		self.graph = [[] for _ in range(N)]
		self.capacities = [dict() for _ in range(N)]

	def add_edge(self, v, w, cap):
		self.graph[v].append(w)
		self.graph[w].append(v)
		self.capacities[v][w] = cap
		self.capacities[w][v] = 0

	def bfs(self, s, t):
		self.level = [-1] * self.N
		q = deque([s])
		self.level[s] = 0
		while q:
			v = q.popleft()
			lw = self.level[v] + 1
			for (w, cap) in self.capacities[v].items():
				if cap and self.level[w] == -1:
					self.level[w] = lw
					q.append(w)
		return self.level[t] != -1

	def dfs(self, s, t, up):
		st = [t]
		while st:
			v = st[-1]
			if v == s:
				st.pop()
				flow = up
				for w in st:
					v = self.graph[w][self.it[w]]
					flow = min(flow, self.capacities[v][w])
				for w in st:
					v = self.graph[w][self.it[w]]
					self.capacities[w][v] += flow
					self.capacities[v][w] -= flow
				return flow
			lv = self.level[v]
			while self.it[v] < len(self.graph[v]):
				w = self.graph[v][self.it[v]]
				cap = self.capacities[w][v]
				if cap and self.level[w] != -1:
					if lv > self.level[w]:
						st.append(w)
						break
				self.it[v] += 1
			if self.it[v] == len(self.graph[v]):
				st.pop()
				self.level[v] = self.N
		return 0

	def flow(self, s, t, flow_limit=float('inf')):
		flow = 0
		while flow < flow_limit and self.bfs(s, t):
			self.it = [0] * self.N
			while flow < flow_limit:
				f = self.dfs(s, t, flow_limit - flow)
				if not f:
					break
				flow += f
		return flow

	def min_cut(self, s):
		visited = [False] * self.N
		q = deque([s])
		while q:
			v = q.pop()
			visited[v] = True
			for (w, cap) in self.capacities[v].items():
				if cap and (not visited[w]):
					q.append(w)
(N, M) = map(int, input().split())
S = [list(input()) for i in range(N)]
dc = mf_graph(N * M + 2)
s = N * M
t = N * M + 1
for i in range(N):
	for j in range(M):
		if (i + j) % 2 == 0:
			dc.add_edge(s, M * i + j, 1)
		else:
			dc.add_edge(M * i + j, t, 1)
for i in range(N):
	for j in range(M):
		if j + 1 < M and S[i][j] == '.' and (S[i][j + 1] == '.'):
			(u, v) = (M * i + j, M * i + j + 1)
			if (i + j) % 2 == 1:
				(u, v) = (v, u)
			dc.add_edge(u, v, 1)
		if i + 1 < N and S[i][j] == '.' and (S[i + 1][j] == '.'):
			(u, v) = (M * i + j, M * (i + 1) + j)
			if (i + j) % 2 == 1:
				(u, v) = (v, u)
			dc.add_edge(u, v, 1)
print(dc.flow(s, t))
for u in range(N * M + 2):
	(ui, uj) = divmod(u, M)
	if (ui + uj) % 2 == 1:
		continue
	for (v, cap) in dc.capacities[u].items():
		if cap != 0:
			continue
		(vi, vj) = divmod(v, M)
		if u != s and u != t and (v != s) and (v != t):
			if ui + 1 == vi:
				S[ui][uj] = 'v'
				S[vi][vj] = '^'
			elif ui == vi + 1:
				S[ui][uj] = '^'
				S[vi][vj] = 'v'
			elif uj + 1 == vj:
				S[ui][uj] = '>'
				S[vi][vj] = '<'
			elif uj == vj + 1:
				S[ui][uj] = '<'
				S[vi][vj] = '>'
for res in S:
	print(''.join(res))


from collections import deque

class MaxFlow:

	def __init__(self, n):
		self.n = n
		self.graph = [[] for _ in range(n)]
		self.pos = []

	def add_edge(self, fr, to, cap):
		m = len(self.pos)
		self.pos.append((fr, len(self.graph[fr])))
		self.graph[fr].append([to, len(self.graph[to]), cap])
		self.graph[to].append([fr, len(self.graph[fr]) - 1, 0])
		return m

	def get_edge(self, idx):
		(to, rev, cap) = self.graph[self.pos[idx][0]][self.pos[idx][1]]
		(rev_to, rev_rev, rev_cap) = self.graph[to][rev]
		return (rev_to, to, cap + rev_cap, rev_cap)

	def edges(self):
		m = len(self.pos)
		for i in range(m):
			yield self.get_edge(i)

	def change_edge(self, idx, new_cap, new_flow):
		(to, rev, cap) = self.graph[self.pos[idx][0]][self.pos[idx][1]]
		self.graph[self.pos[idx][0]][self.pos[idx][1]][2] = new_cap - new_flow
		self.graph[to][rev][2] = new_flow

	def dfs(self, s, v, up):
		if v == s:
			return up
		res = 0
		lv = self.level[v]
		for i in range(self.iter[v], len(self.graph[v])):
			(to, rev, cap) = self.graph[v][i]
			if lv <= self.level[to] or self.graph[to][rev][2] == 0:
				continue
			d = self.dfs(s, to, min(up - res, self.graph[to][rev][2]))
			if d <= 0:
				continue
			self.graph[v][i][2] += d
			self.graph[to][rev][2] -= d
			res += d
			if res == up:
				break
		return res

	def max_flow(self, s, t):
		return self.max_flow_with_limit(s, t, 2 ** 63 - 1)

	def max_flow_with_limit(self, s, t, limit):
		flow = 0
		while flow < limit:
			self.level = [-1] * self.n
			self.level[s] = 0
			queue = deque()
			queue.append(s)
			while queue:
				v = queue.popleft()
				for (to, rev, cap) in self.graph[v]:
					if cap == 0 or self.level[to] >= 0:
						continue
					self.level[to] = self.level[v] + 1
					if to == t:
						break
					queue.append(to)
			if self.level[t] == -1:
				break
			self.iter = [0] * self.n
			while flow < limit:
				f = self.dfs(s, t, limit - flow)
				if not f:
					break
				flow += f
		return flow

	def min_cut(self, s):
		visited = [0] * self.n
		queue = deque()
		queue.append(s)
		while queue:
			p = queue.popleft()
			visited[p] = True
			for (to, rev, cap) in self.graph[p]:
				if cap and (not visited[to]):
					visited[to] = True
					queue.append(to)
		return visited
import sys
input = sys.stdin.readline
(N, M) = map(int, input().split())
S = [input() for _ in range(N)]
mf = MaxFlow(N * M + 2)
res = [['.' for j in range(M)] for i in range(N)]
for i in range(N):
	for j in range(M):
		if S[i][j] == '#':
			res[i][j] = '#'
			continue
		if (i + j) % 2 == 0:
			mf.add_edge(N * M, i * M + j, 1)
			for (di, dj) in ((1, 0), (0, 1), (-1, 0), (0, -1)):
				ni = i + di
				nj = j + dj
				if 0 <= ni < N and 0 <= nj < M and (S[ni][nj] == '.'):
					mf.add_edge(i * M + j, ni * M + nj, 1)
		else:
			mf.add_edge(i * M + j, N * M + 1, 1)
print(mf.max_flow(M * N, M * N + 1))
for (fr, to, cap, flow) in mf.edges():
	if flow == 0 or fr == N * M or to == N * M + 1:
		continue
	(si, sj) = divmod(fr, M)
	(ti, tj) = divmod(to, M)
	if si + 1 == ti:
		res[si][sj] = 'v'
		res[ti][tj] = '^'
	elif sj + 1 == tj:
		res[si][sj] = '>'
		res[ti][tj] = '<'
	elif si == ti + 1:
		res[si][sj] = '^'
		res[ti][tj] = 'v'
	else:
		res[si][sj] = '<'
		res[ti][tj] = '>'
for r in res:
	print(''.join(r))


import bisect
import heapq
import math
import random
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from fractions import Fraction
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations, accumulate
from operator import add, mul, sub, itemgetter, attrgetter
import queue
import sys
readline = sys.stdin.readline
INF = 2 ** 62 - 1

def read_int():
	return int(readline())

def read_int_n():
	return list(map(int, readline().split()))

def read_float():
	return float(readline())

def read_float_n():
	return list(map(float, readline().split()))

def read_str():
	return readline().strip()

def read_str_n():
	return readline().strip().split()

def ep(*args):
	print(*args, file=sys.stderr)

def mt(f):
	import time

	def wrap(*args, **kwargs):
		s = time.perf_counter()
		ret = f(*args, **kwargs)
		e = time.perf_counter()
		ep(e - s, 'sec')
		return ret
	return wrap

class Dinic:

	def __init__(self, v):
		self.V = v
		self.G = [list() for _ in range(v)]
		self.level = [0 for _ in range(v)]
		self.iter = [0 for _ in range(v)]
		self.pos = []

	def add_edge(self, from_, to, cap):
		self.pos.append((from_, len(self.G[from_])))
		self.G[from_].append([to, cap, len(self.G[to])])
		self.G[to].append([from_, 0, len(self.G[from_]) - 1])

	def edges(self):
		es = []
		for (f, t) in self.pos:
			e = self.G[f][t]
			re = self.G[e[0]][e[2]]
			e = [f, e[0], e[1] + re[1], re[1]]
			es.append(e)
		return es

	def bfs(self, s):
		self.level = [-1 for _ in range(self.V)]
		self.level[s] = 0
		que = queue.Queue()
		que.put(s)
		while not que.empty():
			v = que.get()
			for i in range(len(self.G[v])):
				e = self.G[v][i]
				if e[1] > 0 and self.level[e[0]] < 0:
					self.level[e[0]] = self.level[v] + 1
					que.put(e[0])

	def dfs(self, v, t, f):
		if v == t:
			return f
		for i in range(self.iter[v], len(self.G[v])):
			self.iter[v] = i
			e = self.G[v][i]
			if e[1] > 0 and self.level[v] < self.level[e[0]]:
				d = self.dfs(e[0], t, min(f, e[1]))
				if d > 0:
					e[1] -= d
					self.G[e[0]][e[2]][1] += d
					return d
		return 0

	def max_flow(self, s, t):
		flow = 0
		while True:
			self.bfs(s)
			if self.level[t] < 0:
				return flow
			self.iter = [0 for _ in range(self.V)]
			f = self.dfs(s, t, INF)
			while f > 0:
				flow += f
				f = self.dfs(s, t, INF)

@mt
def slv(N, M, S):
	S = [list(s) for s in S]
	g = Dinic(N * M + 2)
	s = N * M
	t = s + 1
	for i in range(N):
		for j in range(M):
			if S[i][j] == '#':
				continue
			v = i * M + j
			if (i + j) % 2 == 0:
				g.add_edge(s, v, 1)
			else:
				g.add_edge(v, t, 1)
	for i in range(N):
		for j in range(M):
			if S[i][j] == '#':
				continue
			if (i + j) % 2 == 1:
				continue
			v0 = i * M + j
			for (x, y) in [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]:
				if not (0 <= x < N and 0 <= y < M):
					continue
				v1 = x * M + y
				g.add_edge(v0, v1, 1)
	print(g.max_flow(s, t))
	for (from_, to, _, flow) in g.edges():
		if from_ in {s, t} or to in {s, t} or flow == 0:
			continue
		i0 = from_ // M
		j0 = from_ % M
		i1 = to // M
		j1 = to % M
		if i0 == i1 + 1:
			S[i1][j1] = 'v'
			S[i0][j0] = '^'
		elif j0 == j1 + 1:
			S[i1][j1] = '>'
			S[i0][j0] = '<'
		elif i0 == i1 - 1:
			S[i1][j1] = '^'
			S[i0][j0] = 'v'
		else:
			S[i1][j1] = '<'
			S[i0][j0] = '>'
	for s in S:
		print(''.join(s))

def main():
	(N, M) = read_int_n()
	S = [read_str() for _ in range(N)]
	slv(N, M, S)
main()


class maxflow:

	def __init__(self, n):
		self.pos = []
		self.g = [[] for _ in range(n)]
		self.n = n

	def add_edge(self, v, w, cap):
		e1 = [w, 0, cap]
		e2 = [v, e1, 0]
		e1[1] = e2
		self.g[v].append(e1)
		self.g[w].append(e2)

	def flow(self, s, t, flow_limit=-1):
		if flow_limit < 0:
			flow_limit = 10 ** 100

		def bfs():
			L = [-1] * self.n
			L[s] = 0
			Q = [s]
			while Q:
				v = Q.pop()
				for (w, _, cap) in self.g[v]:
					if cap == 0 or L[w] >= 0:
						continue
					L[w] = L[v] + 1
					if w == t:
						return L
					Q.append(w)
			return L

		def dfs(v, up):
			if v == s:
				return up
			res = 0
			lv = L[v]
			for i in range(it[v], len(self.g[v])):
				(w, rev, cap) = self.g[v][i]
				if lv <= L[w] or rev[2] == 0:
					continue
				d = dfs(w, min(up - res, rev[2]))
				if d <= 0:
					continue
				self.g[v][i][2] += d
				rev[2] -= d
				res += d
				if res == up:
					break
				it[v] += 1
			return res
		flow = 0
		while flow < flow_limit:
			L = bfs()
			if L[t] == -1:
				break
			it = [0] * self.n
			while flow < flow_limit:
				f = dfs(t, flow_limit - flow)
				if not f:
					break
				flow += f
		return (flow, self.g)

	def min_cut(self, s):
		visited = [0] * self.n
		Q = [s]
		while Q:
			p = Q.pop()
			visited[p] = 1
			for e in self.g[p]:
				if e[2] and visited[e[0]] == 0:
					visited[e[0]] = 1
					Q.append(e[0])
		return visited
(N, M) = map(int, input().split())
mf = maxflow(N * M + 2)
A = [[a for a in input()] for _ in range(N)]
X = [[1 if a == '.' else 0 for a in aa] for aa in A]
s = N * M
t = s + 1
for i in range(N):
	for j in range(M):
		if X[i][j]:
			if (i ^ j) & 1 == 0:
				mf.add_edge(s, i * M + j, 1)
			else:
				mf.add_edge(i * M + j, t, 1)
for i in range(N - 1):
	for j in range(M):
		if X[i][j] and X[i + 1][j]:
			a = i * M + j
			b = a + M
			if (i ^ j) & 1 == 0:
				mf.add_edge(a, b, 1)
			else:
				mf.add_edge(b, a, 1)
for i in range(N):
	for j in range(M - 1):
		if X[i][j] and X[i][j + 1]:
			a = i * M + j
			b = a + 1
			if (i ^ j) & 1 == 0:
				mf.add_edge(a, b, 1)
			else:
				mf.add_edge(b, a, 1)
(fl, g) = mf.flow(s, t)
for (v, gv) in enumerate(g):
	if v >= N * M:
		continue
	for (w, _, ca) in gv:
		if w >= N * M:
			continue
		(vi, vj) = (v // M, v % M)
		(wi, wj) = (w // M, w % M)
		if (vi ^ vj) % 2 == 0 and ca == 0:
			if v > w:
				(vi, vj, wi, wj) = (wi, wj, vi, vj)
			if vi == wi:
				A[vi][vj] = '>'
				A[wi][wj] = '<'
			else:
				A[vi][vj] = 'v'
				A[wi][wj] = '^'
print(fl)
for x in A:
	print(''.join(map(str, x)))


class mf_graph:

	def __init__(self, N):
		self.N = N
		self.graph = [[] for _ in range(N)]
		self.capacities = [dict() for _ in range(N)]

	def add_edge(self, v, w, cap):
		self.graph[v].append(w)
		self.graph[w].append(v)
		self.capacities[v][w] = cap
		self.capacities[w][v] = 0

	def bfs(self, s, t):
		self.level = [-1] * self.N
		q = [s]
		self.level[s] = 0
		while q:
			nq = []
			for v in q:
				if v == t:
					return True
				for (w, cap) in self.capacities[v].items():
					if cap and self.level[w] == -1:
						self.level[w] = self.level[v] + 1
						nq.append(w)
			q = nq
		return False

	def dfs(self, s, t, up):
		st = [t]
		while st:
			v = st[-1]
			if v == s:
				flow = up
				for i in range(len(st) - 2):
					if flow > self.capacities[st[i + 1]][st[i]]:
						flow = self.capacities[st[i + 1]][st[i]]
				for i in range(len(st) - 1):
					self.capacities[st[i]][st[i + 1]] += flow
					self.capacities[st[i + 1]][st[i]] -= flow
				return flow
			while self.it[v] < len(self.graph[v]):
				w = self.graph[v][self.it[v]]
				cap = self.capacities[w][v]
				if cap and self.level[w] != -1:
					if self.level[v] > self.level[w]:
						st.append(w)
						break
				self.it[v] += 1
			else:
				st.pop()
				self.level[v] = self.N
		return 0

	def flow(self, s, t, flow_limit=18446744073709551615):
		flow = 0
		while flow < flow_limit and self.bfs(s, t):
			self.it = [0] * self.N
			while flow < flow_limit:
				f = self.dfs(s, t, flow_limit - flow)
				if not f:
					break
				flow += f
		return flow

	def min_cut(self, s):
		visited = [False] * self.N
		q = [s]
		while q:
			v = q.pop()
			visited[v] = True
			for (w, cap) in self.capacities[v].items():
				if cap and (not visited[w]):
					q.append(w)
(N, M) = map(int, input().split())
S = [list(input()) for i in range(N)]
dc = mf_graph(N * M + 2)
s = N * M
t = N * M + 1
for i in range(N):
	for j in range(M):
		if (i + j) % 2 == 0:
			dc.add_edge(s, M * i + j, 1)
		else:
			dc.add_edge(M * i + j, t, 1)
for i in range(N):
	for j in range(M):
		if j + 1 < M and S[i][j] == '.' and (S[i][j + 1] == '.'):
			(u, v) = (M * i + j, M * i + j + 1)
			if (i + j) % 2 == 1:
				(u, v) = (v, u)
			dc.add_edge(u, v, 1)
		if i + 1 < N and S[i][j] == '.' and (S[i + 1][j] == '.'):
			(u, v) = (M * i + j, M * (i + 1) + j)
			if (i + j) % 2 == 1:
				(u, v) = (v, u)
			dc.add_edge(u, v, 1)
print(dc.flow(s, t))
for u in range(N * M + 2):
	(ui, uj) = divmod(u, M)
	if (ui + uj) % 2 == 1:
		continue
	for (v, cap) in dc.capacities[u].items():
		if cap != 0:
			continue
		(vi, vj) = divmod(v, M)
		if u != s and u != t and (v != s) and (v != t):
			if ui + 1 == vi:
				S[ui][uj] = 'v'
				S[vi][vj] = '^'
			elif ui == vi + 1:
				S[ui][uj] = '^'
				S[vi][vj] = 'v'
			elif uj + 1 == vj:
				S[ui][uj] = '>'
				S[vi][vj] = '<'
			elif uj == vj + 1:
				S[ui][uj] = '<'
				S[vi][vj] = '>'
for res in S:
	print(''.join(res))


def getN():
	return int(input())

def getNM():
	return map(int, input().split())

def getList():
	return list(map(int, input().split()))

def getArray(intn):
	return [int(input()) for i in range(intn)]

def input():
	return sys.stdin.readline().rstrip()

def rand_N(ran1, ran2):
	return random.randint(ran1, ran2)

def rand_List(ran1, ran2, rantime):
	return [random.randint(ran1, ran2) for i in range(rantime)]

def rand_ints_nodup(ran1, ran2, rantime):
	ns = []
	while len(ns) < rantime:
		n = random.randint(ran1, ran2)
		if not n in ns:
			ns.append(n)
	return sorted(ns)

def rand_query(ran1, ran2, rantime):
	r_query = []
	while len(r_query) < rantime:
		n_q = rand_ints_nodup(ran1, ran2, 2)
		if not n_q in r_query:
			r_query.append(n_q)
	return sorted(r_query)
from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
from heapq import heapify, heappop, heappush
import math
import random
import string
from copy import deepcopy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right
import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7
(N, M) = getNM()
n = N
m = M
S = [list(input()) for i in range(N)]

def change(y, x):
	return y * M + (x + 1)

def change_rev(z):
	sz = z - 1
	y_opt = sz // m
	return (y_opt, sz - m * y_opt)

def change2(y, x):
	return N * M + y * M + (x + 1)

def change2_rev(z):
	sz = z - n * m - 1
	y_opt = sz // m
	return (y_opt, sz - m * y_opt)
query = []
for i in range(N):
	for j in range(M):
		if S[i][j] == '.':
			query.append([0, change(i, j), 1])
			query.append([change2(i, j), 2 * N * M + 1, 1])
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
for i in range(N):
	for j in range(M):
		if (i + j) % 2 == 0:
			continue
		for k in range(4):
			ny = i + dy[k]
			nx = j + dx[k]
			if 0 <= ny < N and 0 <= nx < M and (S[i][j] == '.') and (S[ny][nx] == '.'):
				query.append([change(i, j), change2(ny, nx), 1])
query.sort()
N = 2 * N * M + 2
ans = 0
lines = defaultdict(set)
cost = defaultdict(lambda : defaultdict(int))
for i in range(len(query)):
	(a, b, c) = query[i]
	if c != 0:
		lines[a].add(b)
		cost[a][b] += c

def Ford_Fulkerson(sta, end):
	global ans
	queue = deque()
	queue.append([sta, float('inf')])
	ignore = [1] * N
	ignore[sta] = 0
	route = [0] * N
	route[sta] = -1
	while queue:
		(s, flow) = queue.pop()
		for t in lines[s]:
			if ignore[t]:
				flow = min(cost[s][t], flow)
				route[t] = s
				queue.append([t, flow])
				ignore[t] = 0
				if t == end:
					ans += flow
					break
		else:
			continue
		break
	else:
		return False
	t = end
	s = route[t]
	while s != -1:
		cost[s][t] -= flow
		if cost[s][t] == 0:
			lines[s].remove(t)
		if cost[t][s] == 0:
			lines[t].add(s)
		cost[t][s] += flow
		t = s
		s = route[t]
	return True
while True:
	if Ford_Fulkerson(0, N - 1):
		continue
	else:
		break
cost_aft = deepcopy(cost)
print(ans)
alta = deepcopy(S)
for (key, value) in cost_aft.items():
	if key == 0 or n * m < key:
		continue
	for (k, v) in value.items():
		if v == 0:
			(sy, sx) = change_rev(key)
			(ey, ex) = change2_rev(k)
			s1y = min(sy, ey)
			e1y = max(sy, ey)
			s1x = min(sx, ex)
			e1x = max(sx, ex)
			if sy == ey:
				alta[s1y][s1x] = '>'
				alta[e1y][e1x] = '<'
			else:
				alta[s1y][s1x] = 'v'
				alta[e1y][e1x] = '^'
for i in alta:
	print(''.join(i))


def FF(E, s, t, nn):
	G = [[] for _ in range(nn)]
	for (a, b, f) in E:
		G[a].append([b, f, len(G[b])])
		G[b].append([a, 0, len(G[a]) - 1])

	def dfs(s, t, f):
		if s == t:
			return f
		used[s] = 1
		for (i, (b, _f, r)) in enumerate(G[s]):
			if used[b] or _f == 0:
				continue
			d = dfs(b, t, min(f, _f))
			if d > 0:
				G[s][i][1] -= d
				G[b][r][1] += d
				return d
		return 0
	flow = 0
	while 1:
		used = [0] * nn
		f = dfs(s, t, 10 ** 100)
		if f == 0:
			return (flow, G)
		flow += f
E = []
(N, M) = map(int, input().split())
A = [[a for a in input()] for _ in range(N)]
X = [[1 if a == '.' else 0 for a in aa] for aa in A]
s = N * M
t = s + 1
for i in range(N):
	for j in range(M):
		if X[i][j]:
			if (i ^ j) & 1 == 0:
				E.append((s, i * M + j, 1))
			else:
				E.append((i * M + j, t, 1))
for i in range(N - 1):
	for j in range(M):
		if X[i][j] and X[i + 1][j]:
			a = i * M + j
			b = a + M
			if (i ^ j) & 1 == 0:
				E.append((a, b, 1))
			else:
				E.append((b, a, 1))
for i in range(N):
	for j in range(M - 1):
		if X[i][j] and X[i][j + 1]:
			a = i * M + j
			b = a + 1
			if (i ^ j) & 1 == 0:
				E.append((a, b, 1))
			else:
				E.append((b, a, 1))
D = {}
for (a, b, v) in E:
	D[(a << 16) + b] = v
(ans, mf) = FF(E, s, t, t + 1)
for a in range(t + 1):
	for (b, w, _) in mf[a]:
		ab = (a << 16) + b
		if ab not in D:
			continue
		if w == 0:
			if a >= N * M or b >= N * M:
				continue
			(aa, bb) = (a, b)
			(i, j) = (aa // M, aa % M)
			(ii, jj) = (bb // M, bb % M)
			v = D[ab] - w
			(aa, bb) = (a, b) if a < b else (b, a)
			(i, j) = (aa // M, aa % M)
			(ii, jj) = (bb // M, bb % M)
			if i == ii:
				A[i][j] = '>'
				A[ii][jj] = '<'
			else:
				A[i][j] = 'v'
				A[ii][jj] = '^'
print(ans)
for x in A:
	print(''.join(map(str, x)))


from collections import defaultdict, deque, Counter, OrderedDict
from bisect import bisect_left, bisect_right
from functools import reduce, lru_cache
from heapq import heappush, heappop, heapify
import itertools
import math, fractions
import sys, copy

def L():
	return sys.stdin.readline().split()

def I():
	return int(sys.stdin.readline().rstrip())

def SL():
	return list(sys.stdin.readline().rstrip())

def LI():
	return [int(x) for x in sys.stdin.readline().split()]

def LI1():
	return [int(x) - 1 for x in sys.stdin.readline().split()]

def LS():
	return [list(x) for x in sys.stdin.readline().split()]

def R(n):
	return [sys.stdin.readline().strip() for _ in range(n)]

def LR(n):
	return [L() for _ in range(n)]

def IR(n):
	return [I() for _ in range(n)]

def LIR(n):
	return [LI() for _ in range(n)]

def LIR1(n):
	return [LI1() for _ in range(n)]

def SLR(n):
	return [SL() for _ in range(n)]

def LSR(n):
	return [LS() for _ in range(n)]

def perm(n, r):
	return math.factorial(n) // math.factorial(r)

def comb(n, r):
	return math.factorial(n) // (math.factorial(r) * math.factorial(n - r))

def make_list(n, *args, default=0):
	return [make_list(*args, default=default) for _ in range(n)] if args else [default for _ in range(n)]
dire = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dire8 = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
alphabets = 'abcdefghijklmnopqrstuvwxyz'
ALPHABETS = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
MOD = 1000000007
INF = float('inf')
sys.setrecursionlimit(1000000)

class MaxFlowGraph:

	def __init__(self, N):
		self.N = N
		self.graph = [[] for _ in range(N)]
		self.capacities = [defaultdict(int) for _ in range(N)]

	def add_edge(self, v, w, cap=1):
		self.graph[v].append(w)
		self.graph[w].append(v)
		self.capacities[v][w] = cap

	def bfs(self, s, t):
		self.level = [-1] * self.N
		q = [s]
		self.level[s] = 0
		while q:
			nq = []
			for v in q:
				for (w, cap) in self.capacities[v].items():
					if cap and self.level[w] == -1:
						self.level[w] = self.level[v] + 1
						if w == t:
							return True
						nq.append(w)
			q = nq
		return False

	def dfs(self, s, t, up):
		st = [t]
		while st:
			v = st[-1]
			if v == s:
				flow = min(up, min((self.capacities[st[i + 1]][st[i]] for i in range(len(st) - 2))))
				for i in range(len(st) - 1):
					self.capacities[st[i]][st[i + 1]] += flow
					self.capacities[st[i + 1]][st[i]] -= flow
				return flow
			while self.it[v] < len(self.graph[v]):
				w = self.graph[v][self.it[v]]
				cap = self.capacities[w][v]
				if cap and self.level[w] != -1:
					if self.level[v] > self.level[w]:
						st.append(w)
						break
				self.it[v] += 1
			else:
				st.pop()
				self.level[v] = self.N
		return 0

	def flow(self, s, t, flow_limit=18446744073709551615):
		flow = 0
		while flow < flow_limit and self.bfs(s, t):
			self.it = [0] * self.N
			while flow < flow_limit:
				f = self.dfs(s, t, flow_limit - flow)
				if not f:
					break
				flow += f
		return flow

	def min_cut(self, s):
		visited = [False] * self.N
		q = [s]
		while q:
			v = q.pop()
			visited[v] = True
			for (w, cap) in self.capacities[v].items():
				if cap and (not visited[w]):
					q.append(w)

def main():
	(N, M) = LI()
	S = SLR(N)
	g = MaxFlowGraph(N * M + 2)
	s = N * M
	t = N * M + 1
	for y in range(N):
		for x in range(M):
			if (y + x) % 2 == 0:
				g.add_edge(s, M * y + x)
				for (dy, dx) in [[1, 0], [0, 1]]:
					(ny, nx) = (y + dy, x + dx)
					if 0 <= ny < N and 0 <= nx < M and (S[y][x] == '.') and (S[ny][nx] == '.'):
						g.add_edge(M * y + x, M * ny + nx)
			else:
				g.add_edge(M * y + x, t)
				for (dy, dx) in [[1, 0], [0, 1]]:
					(ny, nx) = (y + dy, x + dx)
					if 0 <= ny < N and 0 <= nx < M and (S[y][x] == '.') and (S[ny][nx] == '.'):
						g.add_edge(M * ny + nx, M * y + x)
	print(g.flow(s, t))
	for u in range(N * M + 2):
		(uy, ux) = divmod(u, M)
		if (uy + ux) % 2 == 1:
			continue
		for (v, cap) in g.capacities[u].items():
			if cap != 0:
				continue
			(vy, vx) = divmod(v, M)
			if u != s and u != t and (v != s) and (v != t):
				if uy - 1 == vy:
					(S[uy][ux], S[vy][vx]) = ('^', 'v')
				elif uy + 1 == vy:
					(S[uy][ux], S[vy][vx]) = ('v', '^')
				elif ux + 1 == vx:
					(S[uy][ux], S[vy][vx]) = ('>', '<')
				elif ux - 1 == vx:
					(S[uy][ux], S[vy][vx]) = ('<', '>')
	for p in S:
		print(''.join(p))
main()


import sys

def input():
	return sys.stdin.readline().strip()

def list2d(a, b, c):
	return [[c] * b for i in range(a)]

def list3d(a, b, c, d):
	return [[[d] * c for j in range(b)] for i in range(a)]

def list4d(a, b, c, d, e):
	return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]

def ceil(x, y=1):
	return int(-(-x // y))

def INT():
	return int(input())

def MAP():
	return map(int, input().split())

def LIST(N=None):
	return list(MAP()) if N is None else [INT() for i in range(N)]

def Yes():
	print('Yes')

def No():
	print('No')

def YES():
	print('YES')

def NO():
	print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 19
MOD = 10 ** 9 + 7
EPS = 10 ** (-10)

def build_grid(H, W, intv, _type, space=False, padding=True):
	if space:
		_input = lambda : input().split()
	else:
		_input = lambda : input()
	_list = lambda : list(map(_type, _input()))
	if padding:
		offset = 1
	else:
		offset = 0
	grid = list2d(H + offset * 2, W + offset * 2, intv)
	for i in range(offset, H + offset):
		row = _list()
		for j in range(offset, W + offset):
			grid[i][j] = row[j - offset]
	return grid

class Dinic:
	INF = 10 ** 18

	def __init__(self, n):
		self.n = n
		self.links = [[] for _ in range(n)]
		self.depth = None
		self.progress = None
		self.pos = []

	def copy(self):
		res = Dinic(self.n)
		res.links = [[a[:] for a in b] for b in self.links]
		res.pos = [a[:] for a in self.pos]
		return res

	def add_edge(self, _from, to, cap):
		self.pos.append((_from, len(self.links[_from])))
		self.links[_from].append([cap, to, len(self.links[to])])
		self.links[to].append([0, _from, len(self.links[_from]) - 1])

	def bfs(self, s):
		from collections import deque
		depth = [-1] * self.n
		depth[s] = 0
		q = deque([s])
		while q:
			v = q.popleft()
			for (cap, to, _) in self.links[v]:
				if cap > 0 and depth[to] < 0:
					depth[to] = depth[v] + 1
					q.append(to)
		self.depth = depth

	def dfs(self, v, t, flow):
		if v == t:
			return flow
		links_v = self.links[v]
		for i in range(self.progress[v], len(links_v)):
			self.progress[v] = i
			(cap, to, rev) = link = links_v[i]
			if cap == 0 or self.depth[v] >= self.depth[to]:
				continue
			d = self.dfs(to, t, min(flow, cap))
			if d == 0:
				continue
			link[0] -= d
			self.links[to][rev][0] += d
			return d
		return 0

	def flow(self, s, t):
		INF = Dinic.INF
		flow = 0
		while True:
			self.bfs(s)
			if self.depth[t] < 0:
				return flow
			self.progress = [0] * self.n
			current_flow = self.dfs(s, t, INF)
			while current_flow > 0:
				flow += current_flow
				current_flow = self.dfs(s, t, INF)

	def get_edge(self, i):
		e = self.links[self.pos[i][0]][self.pos[i][1]]
		re = self.links[e[1]][e[2]]
		return (self.pos[i][0], e[1], e[0] + re[0], re[0])

	def get_edges(self):
		M = len(self.pos)
		res = []
		for i in range(M):
			res.append(self.get_edge(i))
		return res
(N, M) = MAP()
grid = build_grid(N, M, '#', str)
N += 2
M += 2
dinic = Dinic(N * M + 2)
s = N * M
t = N * M + 1
directions = ((1, 0), (-1, 0), (0, 1), (0, -1))
for i in range(1, N - 1):
	for j in range(1, M - 1):
		if grid[i][j] == '#':
			continue
		u = M * i + j
		if (i + j) % 2 == 1:
			dinic.add_edge(s, u, 1)
			for (di, dj) in directions:
				(ni, nj) = (i + di, j + dj)
				v = M * ni + nj
				if grid[ni][nj] == '.':
					dinic.add_edge(u, v, 1)
		else:
			dinic.add_edge(u, t, 1)
res = dinic.flow(s, t)
edges = dinic.get_edges()
for (u, v, cap, f) in edges:
	if u not in [s, t] and v not in [s, t] and f:
		(ci, cj) = divmod(u, M)
		(ni, nj) = divmod(v, M)
		if ci + 1 == ni:
			grid[ci][cj] = 'v'
			grid[ni][nj] = '^'
		elif ci == ni + 1:
			grid[ci][cj] = '^'
			grid[ni][nj] = 'v'
		elif cj + 1 == nj:
			grid[ci][cj] = '>'
			grid[ni][nj] = '<'
		elif cj == nj + 1:
			grid[ci][cj] = '<'
			grid[ni][nj] = '>'
print(res)
for i in range(1, N - 1):
	print(''.join(grid[i][1:M - 1]))


NUMERIC_LIMITS = 10 ** 18
import queue

class maxFlow:

	class edge:

		def __init__(s, frm, to, cap, flow):
			(s.frm, s.to) = (frm, to)
			(s.cap, s.flow) = (cap, flow)

	def __init__(s, n):
		s._n = n
		s.g = [[] for _ in range(n)]
		s.pos = []

	def add_edge(s, frm, to, cap):
		m = len(s.pos)
		s.pos.append([frm, len(s.g[frm])])
		s.g[frm].append(s._edge(to, len(s.g[to]), cap))
		s.g[to].append(s._edge(frm, len(s.g[frm]) - 1, 0))
		return m

	def get_edge(s, i):
		m = len(s.pos)
		_e = s.g[s.pos[i][0]][s.pos[i][1]]
		_re = s.g[_e.to][_e.rev]
		return s.edge(s.pos[i][0], _e.to, _e.cap + _re.cap, _re.cap)

	def edges(s):
		m = len(s.pos)
		result = []
		for i in range(m):
			result.append(s.get_edge(i))
		return result

	def change_edge(s, i, new_cap, new_flow):
		m = len(s.pos)
		_e = s.g[s.pos[i].to][s.pos[i].rev]
		_re = s.g[_e.to][_e.rev]
		_e.cap = new_cap - new_flow
		_re.cap = new_flow

	def flow(self, s, t, flow_limit=NUMERIC_LIMITS):
		level = [0] * self._n
		iter = [0] * self._n

		def bfs():
			for i in range(self._n):
				level[i] = -1
			level[s] = 0
			que = queue.Queue()
			que.put(s)
			while not que.empty():
				v = que.get()
				for e in self.g[v]:
					if e.cap == 0 or level[e.to] >= 0:
						continue
					level[e.to] = level[v] + 1
					if e.to == t:
						return
					que.put(e.to)

		def dfs(this, v, up):
			if v == s:
				return up
			res = 0
			level_v = level[v]
			for i in range(iter[v], len(self.g[v])):
				e = self.g[v][i]
				if level_v <= level[e.to] or self.g[e.to][e.rev].cap == 0:
					continue
				d = this(this, e.to, min(up - res, self.g[e.to][e.rev].cap))
				if d <= 0:
					continue
				self.g[v][i].cap += d
				self.g[e.to][e.rev].cap -= d
				res += d
				if res == up:
					break
			return res
		flow = 0
		while flow < flow_limit:
			bfs()
			if level[t] == -1:
				break
			for i in range(self._n):
				iter[i]
			while flow < flow_limit:
				f = dfs(dfs, t, flow_limit - flow)
				if not f:
					break
				flow += f
		return flow

	def min_cut(self, s):
		visited = [False] * self._n
		que = queue.Queue()
		que.put(s)
		while not que.empty():
			p = que.get()
			visited[p] = True
			for e in self.g[p]:
				if e.cap and (not visited[e.to]):
					visited[e.to] = True
					que.put(e.to)
		return visited

	class _edge:

		def __init__(s, to, rev, cap):
			(s.to, s.rev) = (to, rev)
			s.cap = cap
(N, M) = list(map(int, input().split()))
S = [list(input()) for _ in range(N)]
stop = '#'
flow = maxFlow(N * M + 2)
s = N * M
t = N * M + 1
for x in range(N):
	for y in range(M):
		if S[x][y] == stop:
			continue
		p = (x + y) % 2
		n = x * M + y
		if p:
			flow.add_edge(s, n, 1)
			for (h, w) in [[x - 1, y], [x + 1, y], [x, y - 1], [x, y + 1]]:
				if h < 0:
					continue
				if h >= N:
					continue
				if w < 0:
					continue
				if w >= M:
					continue
				if S[h][w] == stop:
					continue
				m = h * M + w
				flow.add_edge(n, m, 1)
		else:
			flow.add_edge(n, t, 1)
ans = flow.flow(s, t)
edges = flow.edges()
for edge in edges:
	if edge.flow == 0:
		continue
	if edge.frm == s:
		continue
	if edge.to == t:
		continue
	(frm, to) = (edge.frm, edge.to)
	(fy, ty) = (frm % M, to % M)
	(fx, tx) = ((frm - fy) // M, (to - ty) // M)
	if fx == tx:
		if fy > ty:
			(fy, ty) = (ty, fy)
		S[fx][fy] = '>'
		S[tx][ty] = '<'
	else:
		if fx > tx:
			(fx, tx) = (tx, fx)
		S[fx][fy] = 'v'
		S[tx][ty] = '^'
print(ans)
for s in S:
	print(''.join(s))


class mf_graph:

	def __init__(self, n=0):
		self._n = n
		self.g = [[] for _ in range(n)]
		self.pos = []

	def add_edge(self, frm, to, cap):
		m = len(self.pos)
		e1 = mf_graph._edge(to, cap)
		e2 = mf_graph._edge(frm, 0)
		e1.rev = e2
		e2.rev = e1
		self.pos.append(e1)
		self.g[frm].append(e1)
		self.g[to].append(e2)
		return m

	class edge:

		def __init__(self, frm, to, cap, flow):
			self.frm = frm
			self.to = to
			self.cap = cap
			self.flow = flow

		def __iter__(self):
			yield self.frm
			yield self.to
			yield self.cap
			yield self.flow

	def get_edge(self, i):
		e1 = self.pos[i]
		e2 = e1.rev
		return mf_graph.edge(e2.to, e1.to, e1.cap + e2.cap, e2.cap)

	def edges(self):
		return [self.get_edge(i) for i in range(len(self.pos))]

	def change_edge(self, i, new_cap, new_flow):
		e = self.pos[i]
		e.cap = new_cap - new_flow
		e.rev.cap = new_flow

	def flow(self, s, t, flow_limit=1152921504606846975):
		g = self.g
		flow = 0
		que = [None] * self._n
		while flow < flow_limit:
			level = [-1] * self._n
			level[s] = 0
			ql = 0
			qr = 1
			que[0] = s
			unreached = s != t
			while unreached and ql < qr:
				v = que[ql]
				ql += 1
				for e in g[v]:
					to = e.to
					if e.cap and level[to] < 0:
						level[to] = level[v] + 1
						if to == t:
							unreached = False
							break
						que[qr] = to
						qr += 1
			if unreached:
				return flow
			ptr = [len(es) for es in g]
			stack = []
			v = t
			up = flow_limit - flow
			res = 0
			while True:
				if v == s or not ptr[v]:
					if v == s:
						res = up
					while stack:
						tmp = res
						(e, up, res) = stack.pop()
						e.cap -= tmp
						e.rev.cap += tmp
						res += tmp
						if res < up:
							v = e.to
							break
					else:
						flow += res
						break
				i = ptr[v]
				while i:
					i -= 1
					e = g[v][i]
					if level[e.to] == level[v] - 1 and e.rev.cap:
						ptr[v] = i
						stack.append((e.rev, up, res))
						v = e.to
						up = min(up, e.rev.cap)
						res = 0
						break
				else:
					ptr[v] = i
		return flow

	def min_cut(self, s):
		visited = [False] * self._n
		que = [None] * self._n
		ql = 0
		qr = 1
		que[0] = s
		visited[s] = True
		while ql < qr:
			p = que[ql]
			ql += 1
			for e in self.g[p]:
				if e.cap and (not visited[e.to]):
					visited[e.to] = True
					que[qr] = e.to
					qr += 1
		return visited

	class _edge:

		def __init__(self, to, cap):
			self.to = to
			self.cap = cap
(n, m) = map(int, input().split())
s = [input() for _ in range(n)]
g = mf_graph(n * m + 2)
for i in range(n):
	for j in range(i % 2, m, 2):
		if s[i][j] == '#':
			continue
		for (di, dj) in ((1, 0), (0, 1), (-1, 0), (0, -1)):
			(x, y) = (i + di, j + dj)
			if 0 <= x < n and 0 <= y < m and (s[x][y] == '.'):
				g.add_edge(i * m + j, x * m + y, 1)
for i in range(n):
	for j in range(m):
		if s[i][j] == '#':
			continue
		if (i + j) % 2 == 0:
			g.add_edge(n * m, i * m + j, 1)
		else:
			g.add_edge(i * m + j, n * m + 1, 1)
print(g.flow(n * m, n * m + 1))
ans = [list(si) for si in s]
for (frm, to, cap, flow) in g.edges():
	if flow and frm < n * m and (to < n * m):
		(i, j) = (frm // m, frm % m)
		(x, y) = (to // m, to % m)
		if j == y:
			if i > x:
				(i, j, x, y) = (x, y, i, j)
			(ans[i][j], ans[x][y]) = 'v^'
		else:
			if j > y:
				(i, j, x, y) = (x, y, i, j)
			(ans[i][j], ans[x][y]) = '><'
for a in ans:
	print(''.join(a))


from collections import deque
(N, M) = map(int, input().split())
S = [list(input()) for i in range(N)]
V = N * M + 2
G = [[] for i in range(V)]
L = [0] * V
I = [0] * V
INF = 10 ** 15

def ae(fr, to, ca):
	global G
	G[fr].append([to, ca, len(G[to]), 0])
	G[to].append([fr, 0, len(G[fr]) - 1, 0])

def bfs(s):
	global INF, L, V, G
	L = [-1] * V
	Q = deque()
	L[s] = 0
	Q.append(s)
	while len(Q):
		x = Q.popleft()
		for i in range(len(G[x])):
			if G[x][i][1] > 0 and L[G[x][i][0]] < 0:
				L[G[x][i][0]] = L[x] + 1
				Q.append(G[x][i][0])

def dfs(v, t, f):
	global I, G, V
	if v == t:
		return f
	for i in range(I[v], len(G[v])):
		if G[v][i][1] > 0 and L[v] < L[G[v][i][0]]:
			d = dfs(G[v][i][0], t, min(f, G[v][i][1]))
			if d > 0:
				G[v][i][1] -= d
				G[v][i][3] += d
				G[G[v][i][0]][G[v][i][2]][1] += d
				G[G[v][i][0]][G[v][i][2]][3] -= d
				return d
		I[v] += 1
	return 0

def mf(s, t):
	global L, I, INF, V
	fl = 0
	while True:
		bfs(s)
		if L[t] < 0:
			break
		I = [0] * V
		f = 0
		while True:
			f = dfs(s, t, INF)
			if f <= 0:
				break
			fl += f
	return fl
w4x = [0, 1, 0, -1]
w4y = [1, 0, -1, 0]
v = 0
for i in range(N):
	for j in range(M):
		if i + j & 1:
			ae(i * M + j, V - 1, 1)
			continue
		ae(V - 2, i * M + j, 1)
		if S[i][j] == '#':
			continue
		for k in range(4):
			v = [i + w4y[k], j + w4x[k]]
			if min(v) < 0 or v[0] == N or v[1] == M:
				continue
			if S[v[0]][v[1]] == '.':
				ae(i * M + j, v[0] * M + v[1], 1)
print(mf(V - 2, V - 1))
for i in range(N * M):
	for j in range(len(G[i])):
		if G[i][j][3] > 0:
			v = G[i][j][0]
			if v >= N * M:
				continue
			if i + M == v:
				S[i // M][i % M] = 'v'
				S[i // M + 1][i % M] = '^'
			elif i - M == v:
				S[i // M - 1][i % M] = 'v'
				S[i // M][i % M] = '^'
			elif i + 1 == v:
				S[i // M][i % M] = '>'
				S[i // M][i % M + 1] = '<'
			elif i - 1 == v:
				S[i // M][i % M - 1] = '>'
				S[i // M][i % M] = '<'
for i in range(N):
	print(''.join(S[i]))


import queue
import sys
readline = sys.stdin.readline
INF = 2 ** 62 - 1

def read_int():
	return int(readline())

def read_int_n():
	return list(map(int, readline().split()))

def read_float():
	return float(readline())

def read_float_n():
	return list(map(float, readline().split()))

def read_str():
	return readline().strip()

def read_str_n():
	return readline().strip().split()

def ep(*args):
	print(*args, file=sys.stderr)

def mt(f):
	import time

	def wrap(*args, **kwargs):
		s = time.perf_counter()
		ret = f(*args, **kwargs)
		e = time.perf_counter()
		ep(e - s, 'sec')
		return ret
	return wrap

class Dinic:
	INF = 10 ** 18

	def __init__(self, n):
		self.n = n
		self.links = [[] for _ in range(n)]
		self.depth = None
		self.progress = None
		self.pos = []

	def copy(self):
		res = Dinic(self.n)
		res.links = [[a[:] for a in b] for b in self.links]
		res.pos = [a[:] for a in self.pos]
		return res

	def add_edge(self, _from, to, cap):
		self.pos.append((_from, len(self.links[_from])))
		self.links[_from].append([cap, to, len(self.links[to])])
		self.links[to].append([0, _from, len(self.links[_from]) - 1])

	def bfs(self, s):
		from collections import deque
		depth = [-1] * self.n
		depth[s] = 0
		q = deque([s])
		while q:
			v = q.popleft()
			for (cap, to, _) in self.links[v]:
				if cap > 0 and depth[to] < 0:
					depth[to] = depth[v] + 1
					q.append(to)
		self.depth = depth

	def dfs(self, v, t, flow):
		if v == t:
			return flow
		links_v = self.links[v]
		for i in range(self.progress[v], len(links_v)):
			self.progress[v] = i
			(cap, to, rev) = link = links_v[i]
			if cap == 0 or self.depth[v] >= self.depth[to]:
				continue
			d = self.dfs(to, t, min(flow, cap))
			if d == 0:
				continue
			link[0] -= d
			self.links[to][rev][0] += d
			return d
		return 0

	def flow(self, s, t):
		INF = Dinic.INF
		flow = 0
		while True:
			self.bfs(s)
			if self.depth[t] < 0:
				return flow
			self.progress = [0] * self.n
			current_flow = self.dfs(s, t, INF)
			while current_flow > 0:
				flow += current_flow
				current_flow = self.dfs(s, t, INF)

	def get_edge(self, i):
		e = self.links[self.pos[i][0]][self.pos[i][1]]
		re = self.links[e[1]][e[2]]
		return (self.pos[i][0], e[1], e[0] + re[0], re[0])

	def get_edges(self):
		M = len(self.pos)
		res = []
		for i in range(M):
			res.append(self.get_edge(i))
		return res

@mt
def slv(N, M, S):
	S = [list(s) for s in S]
	g = Dinic(N * M + 2)
	s = N * M
	t = s + 1
	for i in range(N):
		for j in range(M):
			if S[i][j] == '#':
				continue
			v = i * M + j
			if (i + j) % 2 == 0:
				g.add_edge(s, v, 1)
			else:
				g.add_edge(v, t, 1)
	for i in range(N):
		for j in range(M):
			if S[i][j] == '#':
				continue
			if (i + j) % 2 == 1:
				continue
			v0 = i * M + j
			for (x, y) in [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]:
				if not (0 <= x < N and 0 <= y < M):
					continue
				v1 = x * M + y
				g.add_edge(v0, v1, 1)
	print(g.flow(s, t))
	for (from_, to, _, flow) in g.get_edges():
		if from_ in {s, t} or to in {s, t} or flow == 0:
			continue
		i0 = from_ // M
		j0 = from_ % M
		i1 = to // M
		j1 = to % M
		if i0 == i1 + 1:
			S[i1][j1] = 'v'
			S[i0][j0] = '^'
		elif j0 == j1 + 1:
			S[i1][j1] = '>'
			S[i0][j0] = '<'
		elif i0 == i1 - 1:
			S[i1][j1] = '^'
			S[i0][j0] = 'v'
		else:
			S[i1][j1] = '<'
			S[i0][j0] = '>'
	for s in S:
		print(''.join(s))

def main():
	(N, M) = read_int_n()
	S = [read_str() for _ in range(N)]
	slv(N, M, S)
main()


import math, string, itertools, fractions, heapq, collections, re, array, bisect, sys, copy, functools
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20
eps = 1.0 / 10 ** 10
mod = 10 ** 9 + 7
mod2 = 998244353
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]

def LI():
	return list(map(int, sys.stdin.readline().split()))

def LLI():
	return [list(map(int, l.split())) for l in sys.stdin.readlines()]

def LI_():
	return [int(x) - 1 for x in sys.stdin.readline().split()]

def LF():
	return [float(x) for x in sys.stdin.readline().split()]

def LS():
	return sys.stdin.readline().split()

def I():
	return int(sys.stdin.readline())

def F():
	return float(sys.stdin.readline())

def S():
	return input()

def pf(s):
	return print(s, flush=True)

def pe(s):
	return print(str(s), file=sys.stderr)

def JA(a, sep):
	return sep.join(map(str, a))

def JAA(a, s, t):
	return s.join((t.join(map(str, b)) for b in a))

def IF(c, t, f):
	return t if c else f

class Flow:

	def __init__(self, e, N):
		self.E = e
		self.N = N
		self.nl = list(range(N))

	def max_flow(self, s, t):
		r = 0
		e = self.E
		v = None

		def f(c):
			v[c] = 1
			if c == t:
				return 1
			for i in e[c]:
				if v[i] is None and f(i):
					e[c].remove(i)
					e[i].add(c)
					return 1
			return
		while True:
			v = [None] * self.N
			if f(s) is None:
				break
			r += 1
		return r

def main():
	(n, m) = LI()
	sa = [S() for _ in range(n)]
	e = collections.defaultdict(set)
	s = n * m
	t = n * m + 1
	for i in range(n):
		for j in range(m):
			if sa[i][j] == '#':
				continue
			ij = i * m + j
			if (i + j) % 2 == 1:
				e[ij].add(t)
				continue
			e[s].add(ij)
			for (di, dj) in dd:
				ni = i + di
				nj = j + dj
				if ni < 0 or ni >= n or nj < 0 or (nj >= m) or (sa[ni][nj] == '#'):
					continue
				e[ij].add(ni * m + nj)
	fl = Flow(e, n * m + 2)
	r = fl.max_flow(s, t)
	ra = [[c for c in s] for s in sa]
	for i in range(n):
		for j in range(m):
			ij = i * m + j
			if sa[i][j] == '#' or (i + j) % 2 == 1 or ij in e[s]:
				continue
			ni = nj = 0
			for (di, dj) in dd:
				ni = i + di
				nj = j + dj
				if ni < 0 or ni >= n or nj < 0 or (nj >= m) or (sa[ni][nj] == '#'):
					continue
				if ni * m + nj not in e[ij]:
					break
			if ni < i:
				ra[ni][j] = 'v'
				ra[i][j] = '^'
			elif ni > i:
				ra[i][j] = 'v'
				ra[ni][j] = '^'
			elif nj < j:
				ra[i][nj] = '>'
				ra[i][j] = '<'
			else:
				ra[i][j] = '>'
				ra[i][nj] = '<'
	return f'{r}\n' + JAA(ra, '\n', '')
print(main())


from collections import deque

class MaxFlow:

	def __init__(self, n):
		self.n = n
		self.graph = [[] for _ in range(n)]
		self.pos = []

	def add_edge(self, fr, to, cap):
		m = len(self.pos)
		self.pos.append((fr, len(self.graph[fr])))
		self.graph[fr].append([to, len(self.graph[to]), cap])
		self.graph[to].append([fr, len(self.graph[fr]) - 1, 0])
		return m

	def get_edge(self, idx):
		(to, rev, cap) = self.graph[self.pos[idx][0]][self.pos[idx][1]]
		(rev_to, rev_rev, rev_cap) = self.graph[to][rev]
		return (rev_to, to, cap + rev_cap, rev_cap)

	def edges(self):
		m = len(self.pos)
		for i in range(m):
			yield self.get_edge(i)

	def change_edge(self, idx, new_cap, new_flow):
		(to, rev, cap) = self.graph[self.pos[idx][0]][self.pos[idx][1]]
		self.graph[self.pos[idx][0]][self.pos[idx][1]][2] = new_cap - new_flow
		self.graph[to][rev][2] = new_flow

	def dfs(self, s, v, up):
		if v == s:
			return up
		res = 0
		lv = self.level[v]
		for i in range(self.iter[v], len(self.graph[v])):
			(to, rev, cap) = self.graph[v][i]
			if lv <= self.level[to] or self.graph[to][rev][2] == 0:
				continue
			d = self.dfs(s, to, min(up - res, self.graph[to][rev][2]))
			if d <= 0:
				continue
			self.graph[v][i][2] += d
			self.graph[to][rev][2] -= d
			res += d
			if res == up:
				break
			self.iter[v] += 1
		return res

	def max_flow(self, s, t):
		return self.max_flow_with_limit(s, t, 2 ** 63 - 1)

	def max_flow_with_limit(self, s, t, limit):
		flow = 0
		while flow < limit:
			self.level = [-1] * self.n
			self.level[s] = 0
			queue = deque()
			queue.append(s)
			while queue:
				v = queue.popleft()
				for (to, rev, cap) in self.graph[v]:
					if cap == 0 or self.level[to] >= 0:
						continue
					self.level[to] = self.level[v] + 1
					if to == t:
						break
					queue.append(to)
			if self.level[t] == -1:
				break
			self.iter = [0] * self.n
			while flow < limit:
				f = self.dfs(s, t, limit - flow)
				if not f:
					break
				flow += f
		return flow

	def min_cut(self, s):
		visited = [0] * self.n
		queue = deque()
		queue.append(s)
		while queue:
			p = queue.popleft()
			visited[p] = True
			for (to, rev, cap) in self.graph[p]:
				if cap and (not visited[to]):
					visited[to] = True
					queue.append(to)
		return visited
(N, M) = map(int, input().split())
S = [list(input().rstrip()) for _ in range(N)]
mf = MaxFlow(N * M + 2)
start = N * M
end = N * M + 1
for i in range(N):
	for j in range(M):
		if S[i][j] == '#':
			continue
		if (i + j) % 2 == 0:
			mf.add_edge(start, i * M + j, 1)
			for (i2, j2) in [(i, j + 1), (i, j - 1), (i + 1, j), (i - 1, j)]:
				if 0 <= i2 < N and 0 <= j2 < M and (S[i2][j2] != '#'):
					mf.add_edge(i * M + j, i2 * M + j2, 1)
		else:
			mf.add_edge(i * M + j, end, 1)
print(mf.max_flow(start, end))
for (fr, to, cap, flow) in mf.edges():
	if flow == 0 or fr == start or to == end:
		continue
	(fi, fj) = divmod(fr, M)
	(ti, tj) = divmod(to, M)
	if fi < ti:
		S[fi][fj] = 'v'
		S[ti][tj] = '^'
	elif fi > ti:
		S[fi][fj] = '^'
		S[ti][tj] = 'v'
	elif fj < tj:
		S[fi][fj] = '>'
		S[ti][tj] = '<'
	else:
		S[fi][fj] = '<'
		S[ti][tj] = '>'
for s in S:
	print(''.join(s))


class convolution:

	def __init__(self, a: list, b: list, mod: int):
		(self.a, self.b) = (a, b)
		(self.n, self.m) = (len(a), len(b))
		self.MOD = mod
		self.g = primitive_root_constexpr(self.MOD)

	def convolution(self) -> list:
		(n, m) = (self.n, self.m)
		(a, b) = (self.a, self.b)
		if not n or not m:
			return []
		if min(n, m) <= 60:
			if n < m:
				(n, m) = (m, n)
				(a, b) = (b, a)
			ans = [0] * (n + m - 1)
			for i in range(n):
				for j in range(m):
					ans[i + j] += a[i] * b[j] % self.MOD
					ans[i + j] %= self.MOD
			return ans
		z = 1 << ceil_pow2(n + m - 1)
		a = self.resize(a, z)
		a = self.butterfly(a)
		b = self.resize(b, z)
		b = self.butterfly(b)
		for i in range(z):
			a[i] = a[i] * b[i] % self.MOD
		a = self.butterfly_inv(a)
		a = a[:n + m - 1]
		iz = self.inv(z)
		a = [x * iz % self.MOD for x in a]
		return a

	def butterfly(self, a: list) -> list:
		n = len(a)
		h = ceil_pow2(n)
		first = True
		sum_e = [0] * 30
		m = self.MOD
		if first:
			first = False
			(es, ies) = ([0] * 30, [0] * 30)
			cnt2 = bsf(m - 1)
			e = self.mypow(self.g, m - 1 >> cnt2)
			ie = self.inv(e)
			for i in range(cnt2, 1, -1):
				es[i - 2] = e
				ies[i - 2] = ie
				e = e * e % m
				ie = ie * ie % m
			now = 1
			for i in range(cnt2 - 2):
				sum_e[i] = es[i] * now % m
				now = now * ies[i] % m
		for ph in range(1, h + 1):
			w = 1 << ph - 1
			p = 1 << h - ph
			now = 1
			for s in range(w):
				offset = s << h - ph + 1
				for i in range(p):
					l = a[i + offset] % m
					r = a[i + offset + p] * now % m
					a[i + offset] = (l + r) % m
					a[i + offset + p] = (l - r) % m
				now = now * sum_e[bsf(~s)] % m
		return a

	def butterfly_inv(self, a: list) -> list:
		n = len(a)
		h = ceil_pow2(n)
		first = True
		sum_ie = [0] * 30
		m = self.MOD
		if first:
			first = False
			(es, ies) = ([0] * 30, [0] * 30)
			cnt2 = bsf(m - 1)
			e = self.mypow(self.g, m - 1 >> cnt2)
			ie = self.inv(e)
			for i in range(cnt2, 1, -1):
				es[i - 2] = e
				ies[i - 2] = ie
				e = e * e % m
				ie = ie * ie % m
			now = 1
			for i in range(cnt2 - 2):
				sum_ie[i] = ies[i] * now % m
				now = es[i] * now % m
		for ph in range(h, 0, -1):
			w = 1 << ph - 1
			p = 1 << h - ph
			inow = 1
			for s in range(w):
				offset = s << h - ph + 1
				for i in range(p):
					l = a[i + offset] % m
					r = a[i + offset + p] % m
					a[i + offset] = (l + r) % m
					a[i + offset + p] = (m + l - r) * inow % m
				inow = sum_ie[bsf(~s)] * inow % m
		return a

	@staticmethod
	def resize(array: list, sz: int) -> list:
		new_array = array + [0] * (sz - len(array))
		return new_array

	def inv(self, x: int):
		if is_prime_constexpr(self.MOD):
			assert x
			return self.mypow(x, self.MOD - 2)
		else:
			eg = inv_gcd(x)
			assert eg[0] == 1
			return eg[1]

	def mypow(self, x: int, n: int) -> int:
		assert 0 <= n
		r = 1
		m = self.MOD
		while n:
			if n & 1:
				r = r * x % m
			x = x * x % m
			n >>= 1
		return r

class dsu:

	def __init__(self, n: int):
		self._n = n
		self.parent_or_size = [-1] * self._n

	def merge(self, a: int, b: int) -> int:
		assert 0 <= a and a < self._n
		assert 0 <= b and a < self._n
		x = self.leader(a)
		y = self.leader(b)
		if x == y:
			return x
		if -self.parent_or_size[x] < -self.parent_or_size[y]:
			(x, y) = (y, x)
		self.parent_or_size[x] += self.parent_or_size[y]
		self.parent_or_size[y] = x
		return x

	def same(self, a: int, b: int) -> bool:
		assert 0 <= a and a < self._n
		assert 0 <= b and a < self._n
		return self.leader(a) == self.leader(b)

	def leader(self, a: int) -> int:
		assert 0 <= a and a < self._n
		if self.parent_or_size[a] < 0:
			return a
		self.parent_or_size[a] = self.leader(self.parent_or_size[a])
		return self.parent_or_size[a]

	def size(self, a: int) -> int:
		assert 0 <= a and a < self._n
		return -self.parent_or_size[self.leader(a)]

	def groups(self):
		leader_buf = [0] * self._n
		group_size = [0] * self._n
		for i in range(self._n):
			leader_buf[i] = self.leader(i)
			group_size[leader_buf[i]] += 1
		result = [[] for _ in range(self._n)]
		for i in range(self._n):
			result[leader_buf[i]].append(i)
		result = [v for v in result if v]
		return result

class fenwick_tree:

	def __init__(self, n):
		self._n = n
		self.data = [0] * n

	def add(self, p: int, x: int):
		assert 0 <= p and p <= self._n
		p += 1
		while p <= self._n:
			self.data[p - 1] += x
			p += p & -p

	def sum(self, l: int, r: int) -> int:
		assert 0 <= l and l <= r and (r <= self._n)
		return self.__sum(r) - self.__sum(l)

	def __sum(self, r: int) -> int:
		s = 0
		while r > 0:
			s += self.data[r - 1]
			r -= r & -r
		return s

def ceil_pow2(n: int) -> int:
	x = 0
	while 1 << x < n:
		x += 1
	return x

def bsf(n: int) -> int:
	return (n & -n).bit_length() - 1

def safe_mod(x: int, m: int) -> int:
	x %= m
	if x < 0:
		x += m
	return x

class barrett:

	def __init__(self, m: int):
		self._m = m
		self.im = -1 // (m + 1)

	def umod(self):
		return self._m

	def mul(self, a: int, b: int) -> int:
		z = a
		z *= b
		x = z * im >> 64
		v = z - x * self._m
		if self._m <= v:
			v += self._m
		return v

def pow_mod_constexpr(x: int, n: int, m: int) -> int:
	if m == 1:
		return 0
	_m = m
	r = 1
	y = safe_mod(x, m)
	while n:
		if n & 1:
			r = r * y % _m
		y = y * y % _m
		n >>= 1
	return r

def is_prime_constexpr(n: int) -> bool:
	if n <= 1:
		return False
	if n == 2 or n == 7 or n == 61:
		return True
	if n % 2 == 0:
		return False
	d = n - 1
	while d % 2 == 0:
		d //= 2
	for a in [2, 7, 61]:
		t = d
		y = pow_mod_constexpr(a, t, n)
		while t != n - 1 and y != 1 and (y != n - 1):
			y = y * y % n
			t <<= 1
		if y != n - 1 and t % 2 == 0:
			return False
	return True

def inv_gcd(self, a: int, b: int) -> tuple:
	a = safe_mod(a, b)
	if a == 0:
		return (b, 0)
	s = b
	t = a
	m0 = 0
	m1 = 1
	while t:
		u = s // t
		s -= t * u
		m0 -= m1 * u
		tmp = s
		s = t
		t = tmp
		tmp = m0
		m0 = m1
		m1 = tmp
	if m0 < 0:
		m0 += b // s
	return (s, m0)

def primitive_root_constexpr(m: int) -> int:
	if m == 2:
		return 1
	if m == 167772161:
		return 3
	if m == 469762049:
		return 3
	if m == 754974721:
		return 11
	if m == 998244353:
		return 3
	divs = [0] * 20
	divs[0] = 2
	cnt = 1
	x = (m - 1) // 2
	while x % 2 == 0:
		x //= 2
	i = 3
	while i * i <= x:
		if x % i == 0:
			divs[cnt] = i
			cnt += 1
			while x % i == 0:
				x //= i
		i += 2
	if x > 1:
		divs[cnt] = x
		cnt += 1
	g = 2
	while True:
		ok = True
		for i in range(cnt):
			if pow_mod_constexpr(g, (m - 1) // div[i], m) == 1:
				ok = False
				break
		if ok:
			return g
		g += 1

class simple_queue:

	def __init__(self):
		self.payload = []
		self.pos = 0

	def size(self):
		return len(self.payload) - self.pos

	def empty(self):
		return self.pos == len(self.payload)

	def push(self, t: int):
		self.payload.append(t)

	def front(self):
		return self.payload[self.pos]

	def clear(self):
		self.payload.clear()
		pos = 0

	def pop(self):
		self.pos += 1

	def pop_front(self):
		self.pos += 1
		return self.payload[~-self.pos]

class csr:

	def __init__(self, n: int, edges: list):
		from copy import deepcopy
		self.start = [0] * (n + 1)
		self.elist = [[] for _ in range(len(edges))]
		for e in edges:
			self.start[e[0] + 1] += 1
		for i in range(1, n + 1):
			self.start[i] += self.start[i - 1]
		counter = deepcopy(self.start)
		for e in edges:
			self.elist[counter[e[0]]] = e[1]
			counter[e[0]] += 1

class scc_graph:
	edges = []

	def __init__(self, n: int):
		self._n = n
		self.now_ord = 0
		self.group_num = 0

	def num_vertices(self):
		return self._n

	def add_edge(self, _from: int, _to: int):
		self.edges.append((_from, [_to]))

	def scc_ids(self):
		g = csr(self._n, self.edges)
		visited = []
		low = [0] * self._n
		ord = [-1] * self._n
		ids = [0] * self._n

		def dfs(s, v: int):
			low[v] = ord[v] = self.now_ord
			self.now_ord += 1
			visited.append(v)
			for i in range(g.start[v], g.start[v + 1]):
				to = g.elist[i][0]
				if ord[to] == -1:
					s(s, to)
					low[v] = min(low[v], low[to])
				else:
					low[v] = min(low[v], ord[to])
			if low[v] == ord[v]:
				while True:
					u = visited.pop()
					ord[u] = self._n
					ids[u] = self.group_num
					if u == v:
						break
				self.group_num += 1
		for i in range(self._n):
			if ord[i] == -1:
				dfs(dfs, i)
		for i in range(self._n):
			ids[i] = self.group_num - 1 - ids[i]
		return (self.group_num, ids)

	def scc(self):
		ids = self.scc_ids()
		group_num = ids[0]
		counts = [0] * group_num
		for x in ids[1]:
			counts[x] += 1
		groups = [[] for _ in range(group_num)]
		for i in range(self._n):
			groups[ids[1][i]].append(i)
		return groups

class lazy_segtree:

	def __init__(self, op, e, mapping, composition, id, v: list):
		self.op = op
		self.e = e
		self.mapping = mapping
		self.composition = composition
		self.id = id
		self._n = len(v)
		self.log = ceil_pow2(self._n)
		self.size = 1 << self.log
		self.lz = [self.id()] * self.size
		self.d = [self.e()] * (2 * self.size)
		for i in range(self._n):
			self.d[self.size + i] = v[i]
		for i in range(self.size - 1, 0, -1):
			self.__update(i)

	def set_(self, p: int, x: int):
		assert 0 <= p and p < self._n
		p += self.size
		for i in range(self.log, 0, -1):
			self.__push(p >> i)
		self.d[p] = x
		for i in range(1, self.log + 1):
			self.__update(p >> 1)

	def get(self, p: int):
		assert 0 <= p and p < self._n
		p += self.size
		for i in range(self.log, 0, -1):
			self.__push(p >> i)
		return self.d[p]

	def prod(self, l: int, r: int):
		assert 0 <= l and l <= r and (r <= self._n)
		if l == r:
			return self.e()
		l += self.size
		r += self.size
		for i in range(self.log, 0, -1):
			if l >> i << i != l:
				self.__push(l >> i)
			if r >> i << i != r:
				self.__push(r >> i)
		(sml, smr) = (self.e(), self.e())
		while l < r:
			if l & 1:
				sml = self.op(sml, self.d[l])
				l += 1
			if r & 1:
				r -= 1
				smr = self.op(self.d[r], smr)
			l >>= 1
			r >>= 1
		return self.op(sml, smr)

	def all_prod(self):
		return self.d[1]

	def apply(self, p: int, f):
		assert 0 <= p and p < self._n
		p += self.size
		for i in range(self.log, 0, -1):
			self.__push(p >> i)
		self.d[p] = self.mapping(f, self.d[p])
		for i in range(1, self.log + 1):
			self.__update(p >> 1)

	def apply(self, l: int, r: int, f):
		assert 0 <= l and l <= r and (r <= self._n)
		if l == r:
			return
		l += self.size
		r += self.size
		for i in range(self.log, 0, -1):
			if l >> i << i != l:
				self.__push(l >> i)
			if r >> i << i != r:
				self.__push(r - 1 >> i)
		(l2, r2) = (l, r)
		while l < r:
			if l & 1:
				self.__all_apply(l, f)
				l += 1
			if r & 1:
				r -= 1
				self.__all_apply(r, f)
			l >>= 1
			r >>= 1
		(l, r) = (l2, r2)
		for i in range(1, self.log + 1):
			if l >> i << i != l:
				self.__update(l >> i)
			if r >> i << i != r:
				self.__update(r >> i)

	def max_right(self, l: int, g):
		assert 0 <= l and l <= self._n
		if l == self._n:
			return self._n
		l += self.size
		for i in range(self.log, 0, -1):
			self.__push(l >> i)
		sm = self.e()
		while True:
			while l % 2 == 0:
				l >>= 1
			if not g(self.op(sm, self.d[l])):
				while l < self.size:
					self.__push(l)
					l = 2 * l
					if g(self.op(sm, self.d[l])):
						sm = self.op(sm, self.d[l])
						l += 1
				return l - self.size
			sm = self.op(sm, self.d[l])
			l += 1
			if l & -l == l:
				break
		return self._n

	def min_left(self, r: int, g):
		assert 0 <= r and r <= self._n
		if r == 0:
			return 0
		r += self.size
		for i in range(self.log, 0, -1):
			self.__push(r >> i)
		sm = self.e()
		while True:
			r -= 1
			while r > 1 and r % 2:
				r >>= 1
			if not g(self.op(self.d[r], sm)):
				while r < self.size:
					self.__push(r)
					r = 2 * r + 1
					if g(self.op(self.d[r], sm)):
						sm = self.op(self.d[r], sm)
						r -= 1
				return r + 1 - self.size
			sm = self.op(self.d[r], sm)
			if r & -r == r:
				break
		return 0

	def __update(self, k: int):
		self.d[k] = self.op(self.d[k * 2], self.d[k * 2 + 1])

	def __all_apply(self, k: int, f):
		self.d[k] = self.mapping(f, self.d[k])
		if k < self.size:
			self.lz[k] = self.composition(f, self.lz[k])

	def __push(self, k: int):
		self.__all_apply(2 * k, self.lz[k])
		self.__all_apply(2 * k + 1, self.lz[k])
		self.lz[k] = self.id()

def pow_mod(x: int, n: int, m: int) -> int:
	assert 0 <= n and 1 <= m
	if m == 1:
		return 0
	bt = barrett(m)
	r = 1
	y = safe_mod(x, m)
	while n:
		if n & 1:
			r = bt.mul(r, y)
		y = bt.mul(y, y)
		n >>= 1
	return n

def inv_mod(x: int, m: int) -> int:
	assert 1 <= m
	z = inv_gcd(x, m)
	assert z[0] == 1
	return z[1]

def crt(r: list, m: list) -> tuple:
	assert len(r) == len(m)
	n = len(r)
	r0 = 0
	m0 = 1
	for i in range(n):
		assert 1 <= m[i]
		r1 = safe_mod(r[i], m[i])
		m1 = m[i]
		if m0 < m1:
			(r0, r1) = (r1, r0)
			(m0, m1) = (m1, m0)
		if m0 % m1 == 0:
			if r0 % m1 != r1:
				return (0, 0)
			continue
		(g, im) = inv_gcd(m0, m1)
		u1 = m1 // g
		if (r1 - r0) % g:
			return (0, 0)
		x = (r1 - r0) // g % u1 * im % u1
		r0 += x * m0
		m0 *= u1
		if r0 < 0:
			r0 += m0
	return (r0, m0)

def floor_sum(n: int, m: int, a: int, b: int) -> int:
	ans = 0
	if a >= m:
		ans += (n - 1) * n * (a // m) // 2
		a %= m
	if b >= m:
		ans += n * (b // m)
		bb %= m
	y_max = (a * n + b) // m
	x_max = y_max * m - b
	if y_max == 0:
		return ans
	ans += (n - (x_max + a - 1) // a) * y_max
	ans += floor_sum(y_max, a, m, (a - x_max % a) % a)
	return ans

class mf_graph:
	numeric_limits_max = 10 ** 18

	def __init__(self, n: int):
		self._n = n
		self.g = [[] for _ in range(self._n)]
		self.pos = []

	def add_edge(self, _from: int, _to: int, cap: int) -> int:
		assert 0 <= _from and _from < self._n
		assert 0 <= _to and _to < self._n
		assert 0 <= cap
		m = len(self.pos)
		self.pos.append((_from, len(self.g[_from])))
		self.g[_from].append(self._edge(_to, len(self.g[_to]), cap))
		self.g[_to].append(self._edge(_from, len(self.g[_from]) - 1, 0))
		return m

	class edge:

		def __init__(s, _from: int, _to: int, cap: int, flow: int):
			s._from = _from
			s._to = _to
			s.cap = cap
			s.flow = flow

	def get_edge(self, i: int) -> edge:
		m = len(self.pos)
		assert 0 <= i and i < m
		_e = self.g[self.pos[i][0]][self.pos[i][1]]
		_re = self.g[_e.to][_e.rev]
		return self.edge(self.pos[i][0], _e.to, _e.cap + _re.cap, _re.cap)

	def edges(self) -> list:
		m = len(self.pos)
		result = [self.get_edge(i) for i in range(m)]
		return result

	def change_edge(self, i: int, new_cap: int, new_flow: int):
		m = len(self.pos)
		assert 0 <= i and i < m
		assert 0 <= new_flow and new_flow <= new_cap
		_e = self.g[self.pos[i][0]][self.pos[i][1]]
		_re = self.g[_e.to][_e.rev]
		_e.cap = new_cap - new_flow
		_re.cap = new_flow

	def flow(self, s: int, t: int):
		return self.flow_(s, t, self.numeric_limits_max)

	def flow_(self, s: int, t: int, flow_limit: int) -> int:
		assert 0 <= s and s < self._n
		assert 0 <= t and t < self._n
		level = [0] * self._n
		it = [0] * self._n

		def bfs():
			for i in range(self._n):
				level[i] = -1
			level[s] = 0
			que = deque([s])
			while que:
				v = que.popleft()
				for e in self.g[v]:
					if e.cap == 0 or level[e.to] >= 0:
						continue
					level[e.to] = level[v] + 1
					if e.to == t:
						return
					que.append(e.to)

		def dfs(self_, v: int, up: int) -> int:
			if v == s:
				return up
			res = 0
			level_v = level[v]
			for i in range(it[v], len(self.g[v])):
				it[v] = i
				e = self.g[v][i]
				if level_v <= level[e.to] or self.g[e.to][e.rev].cap == 0:
					continue
				d = self_(self_, e.to, min(up - res, self.g[e.to][e.rev].cap))
				if d <= 0:
					continue
				self.g[v][i].cap += d
				self.g[e.to][e.rev].cap -= d
				res += d
				if res == up:
					break
			return res
		flow = 0
		while flow < flow_limit:
			bfs()
			if level[t] == -1:
				break
			for i in range(self._n):
				it[i] = 0
			while flow < flow_limit:
				f = dfs(dfs, t, flow_limit - flow)
				if not f:
					break
				flow += f
		return flow

	def min_cut(self, s: int) -> list:
		visited = [False] * self._n
		que = deque([s])
		while que:
			p = que.popleft()
			visited[p] = True
			for e in self.g[p]:
				if e.cap and (not visited[e.to]):
					visited[e.to] = True
					que.append(e.to)
		return visited

	class _edge:

		def __init__(s, to: int, rev: int, cap: int):
			s.to = to
			s.rev = rev
			s.cap = cap

class mcf_graph:
	numeric_limits_max = 10 ** 18

	def __init__(self, n: int):
		self._n = n
		self.g = [[] for _ in range(n)]
		self.pos = []

	def add_edge(self, _from: int, _to: int, cap: int, cost: int) -> int:
		assert 0 <= _from and _from < self._n
		assert 0 <= _to and _to < self._n
		m = len(self.pos)
		self.pos.append((_from, len(self.g[_from])))
		self.g[_from].append(self._edge(_to, len(self.g[_to]), cap, cost))
		self.g[_to].append(self._edge(_from, len(self.g[_from]) - 1, 0, -cost))
		return m

	class edge:

		def __init__(s, _from: int, _to: int, cap: int, flow: int, cost: int):
			s._from = _from
			s._to = _to
			s.cap = cap
			s.flow = flow
			s.cost = cost

	def get_edge(self, i: int) -> edge:
		m = len(self.pos)
		assert 0 <= i and i < m
		_e = self.g[self.pos[i][0]][self.pos[i][1]]
		_re = self.g[_e.to][_e.rev]
		return self.edge(self.pos[i][0], _e.to, _e.cap + _re.cap, _re.cap, _e.cost)

	def edges(self) -> list:
		m = len(self.pos)
		result = [self.get_edge(i) for i in range(m)]
		return result

	def flow(self, s: int, t: int) -> edge:
		return self.flow_(s, t, self.numeric_limits_max)

	def flow_(self, s: int, t: int, flow_limit: int) -> edge:
		return self.__slope(s, t, flow_limit)[-1]

	def slope(self, s: int, t: int) -> list:
		return self.slope_(s, t, self.numeric_limits_max)

	def slope_(self, s: int, t: int, flow_limit: int) -> list:
		return self.__slope(s, t, flow_limit)

	def __slope(self, s: int, t: int, flow_limit: int) -> list:
		assert 0 <= s and s < self._n
		assert 0 <= t and t < self._n
		assert s != t
		dual = [0] * self._n
		dist = [0] * self._n
		(pv, pe) = ([-1] * self._n, [-1] * self._n)
		vis = [False] * self._n

		def dual_ref():
			for i in range(self._n):
				dist[i] = self.numeric_limits_max
				pv[i] = -1
				pe[i] = -1
				vis[i] = False

			class Q:

				def __init__(s, key: int, to: int):
					s.key = key
					s.to = to

				def __lt__(s, r):
					return s.key < r.key
			que = []
			dist[s] = 0
			heappush(que, Q(0, s))
			while que:
				v = heappop(que).to
				if vis[v]:
					continue
				vis[v] = True
				if v == t:
					break
				for i in range(len(self.g[v])):
					e = self.g[v][i]
					if vis[e.to] or not e.cap:
						continue
					cost = e.cost - dual[e.to] + dual[v]
					if dist[e.to] - dist[v] > cost:
						dist[e.to] = dist[v] + cost
						pv[e.to] = v
						pe[e.to] = i
						heappush(que, Q(dist[e.to], e.to))
			if not vis[t]:
				return False
			for v in range(self._n):
				if not vis[v]:
					continue
				dual[v] -= dist[t] - dist[v]
			return True
		flow = 0
		cost = 0
		prev_cost = -1
		result = []
		result.append((flow, cost))
		while flow < flow_limit:
			if not dual_ref():
				break
			c = flow_limit - flow
			v = t
			while v != s:
				c = min(c, self.g[pv[v]][pe[v]].cap)
				v = pv[v]
			v = t
			while v != s:
				e = self.g[pv[v]][pe[v]]
				e.cap -= c
				self.g[v][e.rev].cap += c
				v = pv[v]
			d = -dual[s]
			flow += c
			cost += c * d
			if prev_cost == d:
				result.pop()
			result.append((flow, cost))
			prev_cost = cost
		return result

	class _edge:

		def __init__(s, to: int, rev: int, cap: int, cost: int):
			s.to = to
			s.rev = rev
			s.cap = cap
			s.cost = cost

class Mint:
	modint1000000007 = 1000000007
	modint998244353 = 998244353

	def __init__(self, v: int=0):
		self.m = self.modint1000000007
		self.x = v % self.__umod()

	def inv(self):
		if is_prime_constexpr(self.__umod()):
			assert self.x
			return self.pow_(self.__umod() - 2)
		else:
			eg = inv_gcd(self.x, self.m)
			assert eg[0] == 1
			return eg[2]

	def __str__(self):
		return str(self.x)

	def __le__(self, other):
		return self.x <= Mint.__get_val(other)

	def __lt__(self, other):
		return self.x < Mint.__get_val(other)

	def __ge__(self, other):
		return self.x >= Mint.__get_val(other)

	def __gt(self, other):
		return self.x > Mint.__get_val(other)

	def __eq__(self, other):
		return self.x == Mint.__get_val(other)

	def __iadd__(self, other):
		self.x += Mint.__get_val(other)
		if self.x >= self.__umod():
			self.x -= self.__umod()
		return self

	def __add__(self, other):
		_v = Mint(self.x)
		_v += other
		return _v

	def __isub__(self, other):
		self.x -= Mint.__get_val(other)
		if self.x >= self.__umod():
			self.x += self.__umod()
		return self

	def __sub__(self, other):
		_v = Mint(self.x)
		_v -= other
		return _v

	def __rsub__(self, other):
		_v = Mint(Mint.__get_val(other))
		_v -= self
		return _v

	def __imul__(self, other):
		self.x = self.x * Mint.__get_val(other) % self.__umod()
		return self

	def __mul__(self, other):
		_v = Mint(self.x)
		_v *= other
		return _v

	def __itruediv__(self, other):
		self.x = self.x / Mint.__get_val(other) % self.__umod()
		return self

	def __truediv__(self, other):
		_v = Mint(self.x)
		_v /= other
		return _v

	def __rtruediv__(self, other):
		_v = Mint(Mint.__get_val(other))
		_v /= self
		return _v

	def __ifloordiv__(self, other):
		other = other if isinstance(other, Mint) else Mint(other)
		self *= other.inv()
		return self

	def __floordiv__(self, other):
		_v = Mint(self.x)
		_v //= other
		return _v

	def __rfloordiv__(self, other):
		_v = Mint(Mint.__get_val(other))
		_v //= self
		return _v

	def __pow__(self, other):
		_v = Mint(pow(self.x, Mint.__get_val(other), self.__umod()))
		return _v

	def __rpow__(self, other):
		_v = Mint(pow(Mint.__get_val(other), self.x, self.__umod()))
		return _v

	def __imod__(self, other):
		self.x %= Mint.__get_val(other)
		return self

	def __mod__(self, other):
		_v = Mint(self.x)
		_v %= other
		return _v

	def __rmod__(self, other):
		_v = Mint(Mint.__get_val(other))
		_v %= self
		return _v

	def __ilshift__(self, other):
		self.x <<= Mint.__get_val(other)
		return self

	def __irshift__(self, other):
		self.x >>= Mint.__get_val(other)
		return self

	def __lshift__(self, other):
		_v = Mint(self.x)
		_v <<= other
		return _v

	def __rshift__(self, other):
		_v = Mint(self.x)
		_v >>= other
		return _v

	def __rlshift__(self, other):
		_v = Mint(Mint.__get_val(other))
		_v <<= self
		return _v

	def __rrshift__(self, other):
		_v = Mint(Mint.__get_val(other))
		_v >>= self
		return _v
	__repr__ = __str__
	__radd__ = __add__
	__rmul__ = __mul__

	def __umod(self):
		return self.m

	@staticmethod
	def __get_val(val):
		return val.x if isinstance(val, Mint) else val

	def pow_(self, n: int):
		assert 0 <= n
		x = Mint(self.x)
		r = 1
		while n:
			if n & 1:
				r *= x
			x *= x
			n >>= 1
		return r

	def val(self):
		return self.x

	def mod(self):
		return self.m

	def raw(self, v):
		x = Mint()
		x.x = v
		return x

class scc_graph_sub:

	def __init__(self, n):
		self.internal = scc_graph(n)

	def add_edge(self, _from, _to):
		n = self.internal.num_vertices()
		assert 0 <= _from and _from < n
		assert 0 <= _to and _to < n
		self.internal.add_edge(_from, _to)

	def scc(self):
		return self.internal.scc()

class segtree:

	def __init__(self, op, e, v: list):
		self._n = len(v)
		self.log = ceil_pow2(self._n)
		self.size = 1 << self.log
		self.op = op
		self.e = e
		self.d = [self.e()] * (self.size * 2)
		for i in range(self._n):
			self.d[self.size + i] = v[i]
		for i in range(self.size - 1, 0, -1):
			self.__update(i)

	def set_(self, p: int, x: int):
		assert 0 <= p and p < self._n
		p += self.size
		self.d[p] = x
		for i in range(1, self.log + 1):
			self.__update(p >> i)

	def get(self, p: int):
		assert 0 <= p and p < self._n
		return self.d[p + self.size]

	def prod(self, l: int, r: int):
		assert 0 <= l and l <= r and (r <= self._n)
		l += self.size
		r += self.size
		(sml, smr) = (self.e(), self.e())
		while l < r:
			if l & 1:
				sml = self.op(sml, self.d[l])
				l += 1
			if r & 1:
				r -= 1
				smr = self.op(self.d[r], smr)
			l >>= 1
			r >>= 1
		return self.op(sml, smr)

	def all_prod(self):
		return self.d[1]

	def max_right(self, l: int, f):
		assert 0 <= l and l <= self._n
		assert f(self.e())
		if l == self._n:
			return self._n
		l += self.size
		sm = self.e()
		while True:
			while l % 2 == 0:
				l >>= 1
			if not f(self.op(sm, self.d[l])):
				while l < self.size:
					l = 2 * l
					if f(self.op(sm, self.d[l])):
						sm = self.op(sm, self.d[l])
						l += 1
				return l - self.size
			sm = self.op(sm, self.d[l])
			l += 1
			if l & -l == l:
				break
		return self._n

	def min_left(self, r: int, f):
		assert 0 <= r and r <= self._n
		assert f(self.e())
		if r == 0:
			return 0
		r += self.size
		sm = self.e()
		while True:
			r -= 1
			while r > 1 and r % 2:
				r >>= 1
			if not f(self.op(self.d[r], sm)):
				while r < self.size:
					r = 2 * r + 1
					if f(self.op(self.d[r], sm)):
						sm = self.op(self.d[r], sm)
						r -= 1
				return r + 1 - self.size
			sm = self.op(self.d[r], sm)
			if r & -r == r:
				break
		return 0

	def __update(self, k: int):
		self.d[k] = self.op(self.d[k * 2], self.d[k * 2 + 1])

def sa_native(s: list):
	from functools import cmp_to_key

	def mycmp(r, l):
		if l == r:
			return -1
		while l < n and r < n:
			if s[l] != s[r]:
				return 1 if s[l] < s[r] else -1
			l += 1
			r += 1
		return 1 if l == n else -1
	n = len(s)
	sa = [i for i in range(n)]
	sa.sort(key=cmp_to_key(mycmp))
	return sa

def sa_doubling(s: list):
	from functools import cmp_to_key

	def mycmp(y, x):
		if rnk[x] != rnk[y]:
			return 1 if rnk[x] < rnk[y] else -1
		rx = rnk[x + k] if x + k < n else -1
		ry = rnk[y + k] if y + k < n else -1
		return 1 if rx < ry else -1
	n = len(s)
	sa = [i for i in range(n)]
	rnk = s
	tmp = [0] * n
	k = 1
	while k < n:
		sa.sort(key=cmp_to_key(mycmp))
		tmp[sa[0]] = 0
		for i in range(1, n):
			tmp[sa[i]] = tmp[sa[i - 1]]
			if mycmp(sa[i], sa[i - 1]):
				tmp[sa[i]] += 1
		(tmp, rnk) = (rnk, tmp)
		k *= 2
	return sa

def sa_is(s: list, upper: int):
	THRESHOLD_NATIVE = 10
	THRESHOLD_DOUBLING = 40
	n = len(s)
	if n == 0:
		return []
	if n == 1:
		return [0]
	if n == 2:
		if s[0] < s[1]:
			return [0, 1]
		else:
			return [1, 0]
	if n < THRESHOLD_NATIVE:
		return sa_native(s)
	if n < THRESHOLD_DOUBLING:
		return sa_doubling(s)
	sa = [0] * n
	ls = [False] * n
	for i in range(n - 2, -1, -1):
		ls[i] = ls[i + 1] if s[i] == s[i + 1] else s[i] < s[i + 1]
	sum_l = [0] * (upper + 1)
	sum_s = [0] * (upper + 1)
	for i in range(n):
		if not ls[i]:
			sum_s[s[i]] += 1
		else:
			sum_l[s[i] + 1] += 1
	for i in range(upper + 1):
		sum_s[i] += sum_l[i]
		if i < upper:
			sum_l[i + 1] += sum_s[i]

	def induce(lms: list):
		from copy import copy
		for i in range(n):
			sa[i] = -1
		buf = copy(sum_s)
		for d in lms:
			if d == n:
				continue
			sa[buf[s[d]]] = d
			buf[s[d]] += 1
		buf = copy(sum_l)
		sa[buf[s[n - 1]]] = n - 1
		buf[s[n - 1]] += 1
		for i in range(n):
			v = sa[i]
			if v >= 1 and (not ls[v - 1]):
				sa[buf[s[v - 1]]] = v - 1
				buf[s[v - 1]] += 1
		buf = copy(sum_l)
		for i in range(n - 1, -1, -1):
			v = sa[i]
			if v >= 1 and ls[v - 1]:
				buf[s[v - 1] + 1] -= 1
				sa[buf[s[v - 1] + 1]] = v - 1
	lms_map = [-1] * (n + 1)
	m = 0
	for i in range(1, n):
		if not ls[i - 1] and ls[i]:
			lms_map[i] = m
			m += 1
	lms = [i for i in range(1, n) if not ls[i - 1] and ls[i]]
	induce(lms)
	if m:
		sorted_lms = [v for v in sa if lms_map[v] != -1]
		rec_s = [0] * m
		rec_upper = 0
		rec_s[lms_map[sorted_lms[0]]] = 0
		for i in range(1, m):
			l = sorted_lms[i - 1]
			r = sorted_lms[i]
			end_l = lms[lms_map[l] + 1] if lms_map[l] + 1 < m else n
			end_r = lms[lms_map[r] + 1] if lms_map[r] + 1 < m else n
			same = True
			if end_l - l != end_r - r:
				same = False
			else:
				while l < end_l:
					if s[l] != s[r]:
						break
					l += 1
					r += 1
				if l == n or s[l] != s[r]:
					same = False
			if not same:
				rec_upper += 1
			rec_s[lms_map[sorted_lms[i]]] = rec_upper
		rec_sa = sa_is(rec_s, rec_upper)
		for i in range(m):
			sorted_lms[i] = lms[rec_sa[i]]
		induce(sorted_lms)
	return sa

def suffix_array(s: list, upper: int):
	assert 0 <= upper
	for d in s:
		assert 0 <= d and d <= upper
	sa = sa_is(s, upper)
	return sa

def suffix_array2(s: list):
	from functools import cmp_to_key
	n = len(s)
	idx = [i for i in range(n)]
	idx.sort(key=cmp_to_key(lambda l, r: s[l] < s[r]))
	s2 = [0] * n
	now = 0
	for i in range(n):
		if i and s[idx[i - 1]] != s[idx[i]]:
			now += 1
		s2[idx[i]] = now
	return sa_is(s2, now)

def suffix_array3(s: str):
	n = len(s)
	s2 = list(map(ord, s))
	return sa_is(s2, 255)

def lcp_array(s: list, sa: list):
	n = len(s)
	assert n >= 1
	rnk = [0] * n
	for i in range(n):
		rnk[sa[i]] = i
	lcp = [0] * (n - 1)
	h = 0
	for i in range(n):
		if h > 0:
			h -= 1
		if rnk[i] == 0:
			continue
		j = sa[rnk[i] - 1]
		while j + h < n and i + h < n:
			if s[j + h] != s[i + h]:
				break
			h += 1
		lcp[rnk[i] - 1] = h
	return lcp

def lcp_array2(s: str, sa: list):
	n = len(s)
	s2 = list(map(ord, s))
	return lcp_array(s2, sa)

def z_algorithm(s: list):
	n = len(s)
	if n == 0:
		return []
	z = [-1] * n
	z[0] = 0
	j = 0
	for i in range(1, n):
		k = z[i] = 0 if j + z[j] <= i else min(j + z[j] - i, z[i - j])
		while i + k < n and s[k] == s[i + k]:
			k += 1
		z[i] = k
		if j + z[j] < i + z[i]:
			j = i
	z[0] = n
	return z

def z_algorithm2(s: str):
	n = len(s)
	s2 = list(map(ord, s))
	return z_algorithm(s2)

class two_sat:

	def __init__(self, n: int):
		self._n = n
		self.scc = scc_graph(2 * n)
		self._answer = [False] * n

	def add_clause(self, i: int, f: bool, j: int, g: bool):
		assert 0 <= i and i < self._n
		assert 0 <= j and j < self._n
		self.scc.add_edge(2 * i + (not f), 2 * j + g)
		self.scc.add_edge(2 * j + (not g), 2 * i + f)

	def satisfiable(self) -> bool:
		_id = self.scc.scc_ids()[1]
		for i in range(self._n):
			if _id[2 * i] == _id[2 * i + 1]:
				return False
			self._answer[i] = _id[2 * i] < _id[2 * i + 1]
		return True

	def answer(self):
		return self._answer
import sys
sys.setrecursionlimit(10 ** 6)
MOD = 10 ** 9 + 7
INF = 10 ** 9
PI = 3.141592653589793

def read_str():
	return sys.stdin.readline().strip()

def read_int():
	return int(sys.stdin.readline().strip())

def read_ints():
	return map(int, sys.stdin.readline().strip().split())

def read_ints2(x):
	return map(lambda num: int(num) - x, sys.stdin.readline().strip().split())

def read_str_list():
	return list(sys.stdin.readline().strip().split())

def read_int_list():
	return list(map(int, sys.stdin.readline().strip().split()))

def GCD(a: int, b: int) -> int:
	return b if a % b == 0 else GCD(b, a % b)

def LCM(a: int, b: int) -> int:
	return a * b // GCD(a, b)

def Main_A():
	(n, q) = read_ints()
	d = dsu(n)
	for _ in range(q):
		(t, u, v) = read_ints()
		if t == 0:
			d.merge(u, v)
		else:
			print(int(d.same(u, v)))

def Main_B():
	(n, q) = read_ints()
	a = read_int_list()
	fw = fenwick_tree(n)
	for (i, x) in enumerate(a):
		fw.add(i, x)
	for _ in range(q):
		query = read_int_list()
		if query[0] == 0:
			fw.add(query[1], query[2])
		else:
			print(fw.sum(query[1], query[2]))

def Main_C():
	for _ in range(read_int()):
		(n, m, a, b) = read_ints()
		print(floor_sum(n, m, a, b))
from collections import deque

def Main_D():
	(n, m) = read_ints()
	grid = [list(read_str()) for _ in range(n)]
	mf = mf_graph(n * m + 2)
	start = n * m
	end = start + 1
	dir = [(1, 0), (0, 1)]
	for y in range(n):
		for x in range(m):
			if (y + x) % 2 == 0:
				mf.add_edge(start, m * y + x, 1)
			else:
				mf.add_edge(m * y + x, end, 1)
			if grid[y][x] == '.':
				for (dy, dx) in dir:
					ny = y + dy
					nx = x + dx
					if ny < n and nx < m and (grid[ny][nx] == '.'):
						(f, t) = (y * m + x, ny * m + nx)
						if (y + x) % 2:
							(f, t) = (t, f)
						mf.add_edge(f, t, 1)
	ans = mf.flow(start, end)
	for y in range(n):
		for x in range(m):
			for e in mf.g[y * m + x]:
				(to, rev, cap) = (e.to, e.rev, e.cap)
				(ny, nx) = divmod(to, m)
				if (y + x) % 2 == 0 and cap == 0 and (to != start) and (to != end) and (y * m + x != start) and (y * m + x != end):
					if y + 1 == ny:
						grid[y][x] = 'v'
						grid[ny][nx] = '^'
					elif y == ny + 1:
						grid[y][x] = '^'
						grid[ny][nx] = 'v'
					elif x + 1 == nx:
						grid[y][x] = '>'
						grid[ny][nx] = '<'
					elif x == nx + 1:
						grid[y][x] = '<'
						grid[ny][nx] = '>'
	print(ans)
	print(*[''.join(ret) for ret in grid], sep='\n')

def Main_E():
	(n, k) = read_ints()
	a = [read_int_list() for _ in range(n)]
	mcf = mcf_graph(n * 2 + 2)
	s = n * 2
	t = n * 2 + 1
	for i in range(n):
		mcf.add_edge(s, i, k, 0)
		mcf.add_edge(i + n, t, k, 0)
	mcf.add_edge(s, t, n * k, INF)
	for i in range(n):
		for j in range(n):
			mcf.add_edge(i, n + j, 1, INF - a[i][j])
	result = mcf.flow_(s, t, n * k)
	print(n * k * INF - result[1])
	grid = [['.'] * n for _ in range(n)]
	edges = mcf.edges()
	for e in edges:
		if e._from == s or e._to == t or e.flow == 0:
			continue
		grid[e._from][e._to - n] = 'X'
	print(*[''.join(g) for g in grid], sep='\n')

def Main_F():
	MOD = 998244353
	(n, m) = read_ints()
	a = read_int_list()
	b = read_int_list()
	a = [x % MOD for x in a]
	b = [x % MOD for x in b]
	cnv = convolution(a, b, MOD)
	ans = cnv.convolution()
	print(*ans)

def Main_G():
	sys.setrecursionlimit(10 ** 6)
	(n, m) = read_ints()
	scc = scc_graph(n)
	for _ in range(m):
		(a, b) = read_ints()
		scc.add_edge(a, b)
	ans = scc.scc()
	print(len(ans))
	for v in ans:
		print(len(v), ' '.join(map(str, v[::-1])))

def Main_H():
	(n, d) = read_ints()
	xy = [read_int_list() for _ in range(n)]
	tw = two_sat(n)
	for i in range(n):
		for j in range(i + 1, n):
			for x in range(2):
				if abs(xy[i][0] - xy[j][0]) < d:
					tw.add_clause(i, False, j, False)
				if abs(xy[i][0] - xy[j][1]) < d:
					tw.add_clause(i, False, j, True)
				if abs(xy[i][1] - xy[j][0]) < d:
					tw.add_clause(i, True, j, False)
				if abs(xy[i][1] - xy[j][1]) < d:
					tw.add_clause(i, True, j, True)
	if not tw.satisfiable():
		print('No')
		exit()
	print('Yes')
	ans = tw.answer()
	for (i, flag) in enumerate(ans):
		print(xy[i][0] if flag else xy[i][1])

def Main_I():
	s = read_str()
	sa = suffix_array3(s)
	ans = len(s) * (len(s) + 1) // 2
	for x in lcp_array2(s, sa):
		ans -= x
	print(ans)

def Main_J():

	def op(l, r):
		return max(l, r)

	def e():
		return -1

	def f(n):
		return n < r
	(n, q) = read_ints()
	a = read_int_list()
	seg = segtree(op, e, a)
	query = [read_ints() for _ in range(q)]
	for i in range(q):
		(t, l, r) = query[i]
		if t == 1:
			seg.set_(~-l, r)
		elif t == 2:
			print(seg.prod(~-l, r))
		else:
			print(seg.max_right(~-l, f) + 1)

def Main_K():
	p = 998244353

	def op(l, r):
		(l1, l2) = (l >> 32, l % (1 << 32))
		(r1, r2) = (r >> 32, r % (1 << 32))
		return ((l1 + r1) % p << 32) + l2 + r2

	def e():
		return 0

	def mapping(l, r):
		(l1, l2) = (l >> 32, l % (1 << 32))
		(r1, r2) = (r >> 32, r % (1 << 32))
		return ((l1 * r1 + l2 * r2) % p << 32) + r2

	def composition(l, r):
		(l1, l2) = (l >> 32, l % (1 << 32))
		(r1, r2) = (r >> 32, r % (1 << 32))
		return (l1 * r1 % p << 32) + (l1 * r2 + l2) % p

	def id():
		return 1 << 32
	(n, q) = read_ints()
	A = read_int_list()
	A = [(x << 32) + 1 for x in A]
	seg = lazy_segtree(op, e, mapping, composition, id, A)
	ans = []
	for _ in range(q):
		query = read_int_list()
		if query[0] == 0:
			(l, r, b, c) = query[1:]
			seg.apply(l, r, (b << 32) + c)
		else:
			(l, r) = query[1:]
			print(seg.prod(l, r) >> 32)

def Main_L():

	def op(l: tuple, r: tuple):
		return (l[0] + r[0], l[1] + r[1], l[2] + r[2] + l[1] * r[0])

	def e():
		return (0, 0, 0)

	def mapping(l: bool, r: tuple):
		if not l:
			return r
		return (r[1], r[0], r[1] * r[0] - r[2])

	def composition(l: bool, r: bool):
		return l ^ r

	def id():
		return False
	(n, q) = read_ints()
	A = read_int_list()
	query = [read_ints() for _ in range(q)]
	a = [(1, 0, 0) if i == 0 else (0, 1, 0) for i in A]
	seg = lazy_segtree(op, e, mapping, composition, id, a)
	for (t, l, r) in query:
		if t == 1:
			seg.apply(~-l, r, True)
		else:
			print(seg.prod(~-l, r)[2])
Main_D()


from collections import deque

class Dinic:

	def __init__(self, N):
		self.N = N
		self.G = [[] for i in range(N)]

	def add_edge(self, fr, to, cap):
		forward = [to, cap, None]
		forward[2] = backward = [fr, 0, forward]
		self.G[fr].append(forward)
		self.G[to].append(backward)

	def add_multi_edge(self, v1, v2, cap1, cap2):
		edge1 = [v2, cap1, None]
		edge1[2] = edge2 = [v1, cap2, edge1]
		self.G[v1].append(edge1)
		self.G[v2].append(edge2)

	def bfs(self, s, t):
		self.level = level = [None] * self.N
		deq = deque([s])
		level[s] = 0
		G = self.G
		while deq:
			v = deq.popleft()
			lv = level[v] + 1
			for (w, cap, _) in G[v]:
				if cap and level[w] is None:
					level[w] = lv
					deq.append(w)
		return level[t] is not None

	def dfs(self, v, t, f):
		if v == t:
			return f
		level = self.level
		for e in self.it[v]:
			(w, cap, rev) = e
			if cap and level[v] < level[w]:
				d = self.dfs(w, t, min(f, cap))
				if d:
					e[1] -= d
					rev[1] += d
					return d
		return 0

	def flow(self, s, t):
		flow = 0
		INF = 10 ** 9 + 7
		G = self.G
		while self.bfs(s, t):
			(*self.it,) = map(iter, self.G)
			f = INF
			while f:
				f = self.dfs(s, t, INF)
				flow += f
		return flow
(N, M) = map(int, input().split())
S = [list(input()) for i in range(N)]
dc = Dinic(N * M + 2)
s = N * M
t = N * M + 1
for i in range(N):
	for j in range(M):
		if (i + j) % 2 == 0:
			dc.add_edge(s, M * i + j, 1)
		else:
			dc.add_edge(M * i + j, t, 1)
for i in range(N):
	for j in range(M):
		if j + 1 < M and S[i][j] == '.' and (S[i][j + 1] == '.'):
			(u, v) = (M * i + j, M * i + j + 1)
			if (i + j) % 2 == 1:
				(u, v) = (v, u)
			dc.add_edge(u, v, 1)
		if i + 1 < N and S[i][j] == '.' and (S[i + 1][j] == '.'):
			(u, v) = (M * i + j, M * (i + 1) + j)
			if (i + j) % 2 == 1:
				(u, v) = (v, u)
			dc.add_edge(u, v, 1)
print(dc.flow(s, t))
for u in range(N * M + 2):
	for (v, cap, _) in dc.G[u]:
		(ui, uj) = divmod(u, M)
		(vi, vj) = divmod(v, M)
		if (ui + uj) % 2 == 0 and cap == 0 and (u != s) and (u != t) and (v != s) and (v != t):
			if ui + 1 == vi:
				S[ui][uj] = 'v'
				S[vi][vj] = '^'
			elif ui == vi + 1:
				S[ui][uj] = '^'
				S[vi][vj] = 'v'
			elif uj + 1 == vj:
				S[ui][uj] = '>'
				S[vi][vj] = '<'
			elif uj == vj + 1:
				S[ui][uj] = '<'
				S[vi][vj] = '>'
for res in S:
	print(''.join(res))


(n, m) = map(int, input().split())
INF = 10 ** 9
import sys
sys.setrecursionlimit(6000)
G = [[] for _ in range(n * m + 2)]

def add_edge(s, t, cap):
	G[s].append([t, cap, len(G[t])])
	G[t].append([s, 0, len(G[s]) - 1])

def get_edges(s):
	pass

def dfs(v, t, f, used):
	if v == t:
		return f
	used[v] = 1
	for (idx, (nn, cap, rev)) in enumerate(G[v]):
		if used[nn] == 0 and cap > 0:
			d = dfs(nn, t, min(f, cap), used)
			if d > 0:
				G[v][idx][1] -= d
				G[nn][rev][1] += d
				return d
	else:
		return 0

def flow(s, t):
	ans = 0
	while True:
		used = [0] * (n * m + 2)
		f = dfs(s, t, INF, used)
		if f == 0:
			return ans
		ans += f
S = [list(input()) for _ in range(n)]
for (i, line) in enumerate(S):
	for (j, s) in enumerate(line):
		cp = i * m + j
		if i % 2 == 0 and j % 2 == 0 or (i % 2 == 1 and j % 2 == 1):
			if s == '.':
				add_edge(n * m, cp, 1)
				for (mi, mj) in [(-1, 0), (1, 0), (0, 1), (0, -1)]:
					(ni, nj) = (i + mi, j + mj)
					if 0 <= ni < n and 0 <= nj < m and (S[ni][nj] == '.'):
						ep = ni * m + nj
						add_edge(cp, ep, 1)
		elif s == '.':
			add_edge(cp, n * m + 1, 1)
f = flow(n * m, n * m + 1)
print(f)
for (a, cap, rev) in G[n * m]:
	if cap == 0:
		for (b, cap, rev) in G[a]:
			if cap == 0:
				(i, j) = divmod(a, m)
				(ii, jj) = divmod(b, m)
				np = (ii - i, jj - j)
				if np == (1, 0):
					S[i][j] = 'v'
					S[ii][jj] = '^'
				elif np == (-1, 0):
					S[i][j] = '^'
					S[ii][jj] = 'v'
				elif np == (0, 1):
					S[i][j] = '>'
					S[ii][jj] = '<'
				elif np == (0, -1):
					S[i][j] = '<'
					S[ii][jj] = '>'
				break
for line in S:
	print(''.join(line))


from typing import NamedTuple, Optional, List

class MaxFlow:

	class Edge(NamedTuple):
		src: int
		dst: int
		cap: int
		flow: int

	class _Edge:
		dst: int
		cap: int
		rev: Optional['MaxFlow._Edge']

		def __init__(self, dst: int, cap: int):
			self.dst = dst
			self.cap = cap
			self.rev = None

	def __init__(self, n: int):
		self._n = n
		self._g: List[List[MaxFlow._Edge]] = [[] for _ in range(n)]
		self._edges: List[MaxFlow._Edge] = []

	def add_edge(self, src: int, dst: int, cap: int) -> int:
		assert 0 <= src < self._n
		assert 0 <= dst < self._n
		assert 0 <= cap
		m = len(self._edges)
		e = MaxFlow._Edge(dst, cap)
		re = MaxFlow._Edge(src, 0)
		e.rev = re
		re.rev = e
		self._g[src].append(e)
		self._g[dst].append(re)
		self._edges.append(e)
		return m

	def get_edge(self, i: int) -> Edge:
		assert 0 <= i < len(self._edges)
		e = self._edges[i]
		re = e.rev
		return MaxFlow.Edge(re.dst, e.dst, e.cap + re.cap, re.cap)

	def edges(self) -> List[Edge]:
		return [self.get_edge(i) for i in range(len(self._edges))]

	def change_edge(self, i: int, new_cap: int, new_flow: int):
		assert 0 <= i < len(self._edges)
		assert 0 <= new_flow <= new_cap
		e = self._edges[i]
		e.cap = new_cap - new_flow
		e.rev.cap = new_flow

	def flow(self, s: int, t: int, flow_limit: Optional[int]=None) -> int:
		assert 0 <= s < self._n
		assert 0 <= t < self._n
		assert s != t
		if flow_limit is None:
			flow_limit = sum((e.cap for e in self._g[s]))
		current_edge = [0] * self._n
		level = [0] * self._n
		buf: List[int] = []
		edge_stack: List[MaxFlow._Edge] = []

		def fill(arr: List[int], value: int):
			for i in range(len(arr)):
				arr[i] = value

		def bfs() -> bool:
			fill(level, self._n)
			queue = buf
			queue.clear()
			q_front = 0
			queue.append(s)
			level[s] = 0
			while q_front < len(queue):
				v = queue[q_front]
				q_front += 1
				next_level = level[v] + 1
				for e in self._g[v]:
					if e.cap == 0 or level[e.dst] <= next_level:
						continue
					level[e.dst] = next_level
					if e.dst == t:
						return True
					queue.append(e.dst)
			return False

		def dfs(lim) -> int:
			stack = buf
			stack.clear()
			stack.append(t)
			edge_stack.clear()
			while stack:
				v = stack[-1]
				if v == s:
					flow = min(lim, min((e.cap for e in edge_stack)))
					for e in edge_stack:
						e.cap -= flow
						e.rev.cap += flow
					return flow
				next_level = level[v] - 1
				while current_edge[v] < len(self._g[v]):
					e = self._g[v][current_edge[v]]
					re = e.rev
					if level[e.dst] != next_level or re.cap == 0:
						current_edge[v] += 1
						continue
					stack.append(e.dst)
					edge_stack.append(re)
					break
				else:
					stack.pop()
					if edge_stack:
						edge_stack.pop()
					level[v] = self._n
			return 0
		flow = 0
		while flow < flow_limit:
			if not bfs():
				break
			fill(current_edge, 0)
			while flow < flow_limit:
				f = dfs(flow_limit - flow)
				flow += f
				if f == 0:
					break
		return flow

def main() -> None:
	import sys
	(n, m) = map(int, sys.stdin.readline().split())
	s = n * m
	t = s + 1
	g = MaxFlow(t + 1)
	grid = [list(sys.stdin.readline().strip()) for _ in range(n)]

	def enc(i: int, j: int) -> int:
		return i * m + j

	def dec(v: int) -> (int, int):
		return (v // m, v % m)
	for i in range(n):
		for j in range(m):
			if grid[i][j] == '#':
				continue
			if (i + j) % 2 == 0:
				g.add_edge(s, enc(i, j), 1)
			else:
				g.add_edge(enc(i, j), t, 1)
	dx = [1, 0, -1, 0]
	dy = [0, 1, 0, -1]
	for i in range(n):
		for j in range(m):
			if (i + j) % 2 == 1 or grid[i][j] == '#':
				continue
			for direction in range(4):
				ii = i + dx[direction]
				jj = j + dy[direction]
				if 0 <= ii < n and 0 <= jj < m and (grid[ii][jj] == '.'):
					g.add_edge(enc(i, j), enc(ii, jj), 1)
	print(g.flow(s, t))
	for e in g.edges():
		if e.src == s or e.dst == t or e.flow == 0:
			continue
		(i, j) = dec(e.src)
		(ii, jj) = dec(e.dst)
		if i == ii + 1:
			grid[ii][jj] = 'v'
			grid[i][j] = '^'
		elif j == jj + 1:
			grid[ii][jj] = '>'
			grid[i][j] = '<'
		elif i == ii - 1:
			grid[i][j] = 'v'
			grid[ii][jj] = '^'
		else:
			grid[i][j] = '>'
			grid[ii][jj] = '<'
	for s in grid:
		print(''.join(s))
main()


(N, M) = map(int, input().split())
S = [list(input()) for i in range(N)]
V = N * M
G = [[] for i in range(V)]
match = [0] * V
used = [0] * V

def ae(u, v):
	G[u].append(v)
	G[v].append(u)

def dfs(v):
	used[v] = 1
	(u, w) = (0, 0)
	for i in range(len(G[v])):
		u = G[v][i]
		w = match[u]
		if w < 0 or (not used[w] and dfs(w)):
			match[v] = u
			match[u] = v
			return 1
	return 0

def matching():
	r = 0
	for i in range(V):
		match[i] = -1
	for v in range(V):
		if match[v] < 0:
			for i in range(V):
				used[i] = 0
			if dfs(v):
				r += 1
	return r
w4y = [1, 0, -1, 0]
w4x = [0, 1, 0, -1]
for i in range(N):
	for j in range(M):
		if i + j + 1 & 1 and S[i][j] == '.':
			for k in range(4):
				k = [i + w4y[k], j + w4x[k]]
				if min(k) < 0 or k[0] >= N or k[1] >= M:
					continue
				if S[k[0]][k[1]] == '.':
					ae(i * M + j, k[0] * M + k[1])
print(matching())
for i in range(N):
	for j in range(M):
		if match[i * M + j] < 0:
			continue
		if match[i * M + j] == i * M + j + M:
			S[i][j] = 'v'
		elif match[i * M + j] == i * M + j - M:
			S[i][j] = '^'
		elif match[i * M + j] == i * M + j + 1:
			S[i][j] = '>'
		elif match[i * M + j] == i * M + j - 1:
			S[i][j] = '<'
	print(''.join(S[i]))


from collections import deque
from typing import List
Edge = List[int]

class Dinic:
	__slots__ = ['_size', 'graph', '_depth', '_progress']

	def __init__(self, size: int) -> None:
		self._size = size
		self.graph: List[List[Edge]] = [[] for _ in range(size)]
		self._depth = [-1] * size
		self._progress = [0] * size

	def add(self, from_: int, to: int, cap: int=1, is_directed: bool=True) -> None:
		self.graph[from_].append([to, cap, len(self.graph[to])])
		self.graph[to].append([from_, 0, len(self.graph[from_]) - 1])
		if not is_directed:
			self.add(to, from_, cap)

	def find_max_flow(self, source: int, target: int, inf: int=1 << 30) -> int:
		flow = 0
		while True:
			self._bfs(source)
			if self._depth[target] < 0:
				break
			self._progress = [0] * self._size
			cur_flow = self._dfs(source, target, inf)
			while cur_flow:
				flow += cur_flow
				cur_flow = self._dfs(source, target, inf)
		return flow

	def _bfs(self, source: int) -> None:
		depth = [-1] * self._size
		depth[source] = 0
		queue = deque([source])
		while queue:
			v = queue.popleft()
			for (to, cap, _) in self.graph[v]:
				if cap > 0 > depth[to]:
					depth[to] = depth[v] + 1
					queue.append(to)
		self._depth = depth

	def _dfs(self, v: int, target: int, flow: int) -> int:
		if v == target:
			return flow
		v_edges = self.graph[v]
		for i in range(self._progress[v], len(v_edges)):
			self._progress[v] = i
			(to, cap, rev) = v_edges[i]
			if not cap or self._depth[v] >= self._depth[to]:
				continue
			d = self._dfs(to, target, min(flow, cap))
			if not d:
				continue
			v_edges[i][1] -= d
			self.graph[to][rev][1] += d
			return d
		return 0

def practice2_d():
	(N, M) = map(int, input().split())
	S = [list(input()) for _ in range(N)]
	dc = Dinic(N * M + 2)
	s = N * M
	t = N * M + 1
	for i in range(N):
		for j in range(M):
			if (i + j) % 2 == 0:
				dc.add(s, M * i + j)
			else:
				dc.add(M * i + j, t)
	for i in range(N):
		for j in range(M):
			if j + 1 < M and S[i][j] == '.' and (S[i][j + 1] == '.'):
				(u, v) = (M * i + j, M * i + j + 1)
				if (i + j) % 2:
					(u, v) = (v, u)
				dc.add(u, v)
			if i + 1 < N and S[i][j] == '.' and (S[i + 1][j] == '.'):
				(u, v) = (M * i + j, M * (i + 1) + j)
				if (i + j) % 2:
					(u, v) = (v, u)
				dc.add(u, v)
	print(dc.find_max_flow(s, t))
	for u in range(N * M + 2):
		for (v, cap, _) in dc.graph[u]:
			(ui, uj) = divmod(u, M)
			(vi, vj) = divmod(v, M)
			if not (ui + uj) % 2 and (not cap) and (u != s) and (u != t) and (v != s) and (v != t):
				if ui + 1 == vi:
					S[ui][uj] = 'v'
					S[vi][vj] = '^'
				elif ui == vi + 1:
					S[ui][uj] = '^'
					S[vi][vj] = 'v'
				elif uj + 1 == vj:
					S[ui][uj] = '>'
					S[vi][vj] = '<'
				elif uj == vj + 1:
					S[ui][uj] = '<'
					S[vi][vj] = '>'
	for res in S:
		print(''.join(res))
practice2_d()


import sys
readline = sys.stdin.readline
import collections

class Dinic:

	def __init__(self, vnum):
		self.edge = [[] for i in range(vnum)]
		self.n = vnum
		self.inf = float('inf')

	def addedge(self, st, en, c):
		self.edge[st].append([en, c, len(self.edge[en])])
		self.edge[en].append([st, 0, len(self.edge[st]) - 1])

	def bfs(self, vst):
		dist = [-1] * self.n
		dist[vst] = 0
		Q = collections.deque([vst])
		while Q:
			nv = Q.popleft()
			for (vt, c, r) in self.edge[nv]:
				if dist[vt] == -1 and c > 0:
					dist[vt] = dist[nv] + 1
					Q.append(vt)
		self.dist = dist

	def dfs(self, nv, en, nf):
		nextv = self.nextv
		if nv == en:
			return nf
		dist = self.dist
		ist = nextv[nv]
		for (i, (vt, c, r)) in enumerate(self.edge[nv][ist:], ist):
			if dist[nv] < dist[vt] and c > 0:
				df = self.dfs(vt, en, min(nf, c))
				if df > 0:
					self.edge[nv][i][1] -= df
					self.edge[vt][r][1] += df
					return df
			nextv[nv] += 1
		return 0

	def getmf(self, st, en):
		mf = 0
		while True:
			self.bfs(st)
			if self.dist[en] == -1:
				break
			self.nextv = [0] * self.n
			while True:
				fl = self.dfs(st, en, self.inf)
				if fl > 0:
					mf += fl
				else:
					break
		return mf
(N, M) = map(int, readline().split())
G = [[1 if s == '#' else 0 for s in readline().strip()] for _ in range(N)]
T = Dinic(2 * N * M + 2)
st = 2 * N * M
en = st + 1
geta = N * M
DIREC = ((1, 0), (-1, 0), (0, 1), (0, -1))
for i in range(N):
	for j in range(M):
		if not G[i][j]:
			if (i + j) % 2:
				T.addedge(st, i * M + j, 1)
				for (di, dj) in DIREC:
					(ni, nj) = (i + di, j + dj)
					if 0 <= ni < N and 0 <= nj < M and (not G[ni][nj]):
						T.addedge(i * M + j, geta + ni * M + nj, 1)
			else:
				T.addedge(geta + i * M + j, en, 1)
print(T.getmf(st, en))
Ans = [g[:] for g in G]
for i in range(N):
	for j in range(M):
		if not (i + j) % 2 and (not G[i][j]):
			for (vf, c, _) in T.edge[geta + M * i + j]:
				if c == 1 and vf != en:
					(ni, nj) = divmod(vf, M)
					if i == ni:
						if j < nj:
							Ans[i][j] = 2
							Ans[ni][nj] = 3
						else:
							Ans[i][j] = 3
							Ans[ni][nj] = 2
					elif i < ni:
						Ans[i][j] = 4
						Ans[ni][nj] = 5
					else:
						Ans[i][j] = 5
						Ans[ni][nj] = 4
D = ['.', '#', '>', '<', 'v', '^']
print('\n'.join((''.join((D[ai] for ai in a)) for a in Ans)))


from collections import deque

class Dinic:

	def __init__(self, N):
		self.N = N
		self.graph = [[] for _ in range(N)]

	def add_edge(self, v, w, cap):
		edge = [w, cap, None]
		edge[2] = rev_edge = [v, 0, edge]
		self.graph[v].append(edge)
		self.graph[w].append(rev_edge)

	def bfs(self, s, t):
		self.level = [None] * self.N
		d = deque([s])
		self.level[s] = 0
		while d:
			v = d.popleft()
			nlevel = self.level[v] + 1
			for (w, cap, _) in self.graph[v]:
				if cap and self.level[w] is None:
					self.level[w] = nlevel
					d.append(w)
		return self.level[t] is not None

	def dfs(self, s, v, f):
		if v == s:
			return f
		for rev in self.it[v]:
			(w, _, e) = rev
			cap = e[1]
			if cap and self.level[w] is not None:
				if self.level[v] > self.level[w]:
					d = self.dfs(s, w, min(f, cap))
					if d:
						e[1] -= d
						rev[1] += d
						return d
		return 0

	def max_flow(self, s, t):
		flow = 0
		INF = 10 ** 9
		while self.bfs(s, t):
			(*self.it,) = map(iter, self.graph)
			f = INF
			while f:
				f = self.dfs(s, t, INF)
				flow += f
		return flow
(N, M) = map(int, input().split())
S = [list(input()) for i in range(N)]
dc = Dinic(N * M + 2)
s = N * M
t = N * M + 1
for i in range(N):
	for j in range(M):
		if (i + j) % 2 == 0:
			dc.add_edge(s, M * i + j, 1)
		else:
			dc.add_edge(M * i + j, t, 1)
for i in range(N):
	for j in range(M):
		if j + 1 < M and S[i][j] == '.' and (S[i][j + 1] == '.'):
			(u, v) = (M * i + j, M * i + j + 1)
			if (i + j) % 2 == 1:
				(u, v) = (v, u)
			dc.add_edge(u, v, 1)
		if i + 1 < N and S[i][j] == '.' and (S[i + 1][j] == '.'):
			(u, v) = (M * i + j, M * (i + 1) + j)
			if (i + j) % 2 == 1:
				(u, v) = (v, u)
			dc.add_edge(u, v, 1)
print(dc.max_flow(s, t))
for u in range(N * M + 2):
	for (v, cap, _) in dc.graph[u]:
		(ui, uj) = divmod(u, M)
		(vi, vj) = divmod(v, M)
		if (ui + uj) % 2 == 0 and cap == 0 and (u != s) and (u != t) and (v != s) and (v != t):
			if ui + 1 == vi:
				S[ui][uj] = 'v'
				S[vi][vj] = '^'
			elif ui == vi + 1:
				S[ui][uj] = '^'
				S[vi][vj] = 'v'
			elif uj + 1 == vj:
				S[ui][uj] = '>'
				S[vi][vj] = '<'
			elif uj == vj + 1:
				S[ui][uj] = '<'
				S[vi][vj] = '>'
for res in S:
	print(''.join(res))


from collections import deque

class Dinic:

	def __init__(self, n: int):
		self.n = n
		self.INF = 10 ** 9 + 7
		self.graph = [[] for _ in range(n)]

	def add_edge(self, _from: int, to: int, capacity: int):
		forward = [to, capacity, None]
		forward[2] = backward = [_from, 0, forward]
		self.graph[_from].append(forward)
		self.graph[to].append(backward)

	def bfs(self, s: int, t: int):
		self.level = [-1] * self.n
		q = deque([s])
		self.level[s] = 0
		while q:
			_from = q.popleft()
			for (to, capacity, _) in self.graph[_from]:
				if capacity > 0 and self.level[to] < 0:
					self.level[to] = self.level[_from] + 1
					q.append(to)

	def dfs(self, _from: int, t: int, f: int) -> int:
		if _from == t:
			return f
		for edge in self.itr[_from]:
			(to, capacity, reverse_edge) = edge
			if capacity > 0 and self.level[_from] < self.level[to]:
				d = self.dfs(to, t, min(f, capacity))
				if d > 0:
					edge[1] -= d
					reverse_edge[1] += d
					return d
		return 0

	def max_flow(self, s: int, t: int) -> int:
		flow = 0
		while True:
			self.bfs(s, t)
			if self.level[t] < 0:
				break
			self.itr = list(map(iter, self.graph))
			f = self.dfs(s, t, self.INF)
			while f > 0:
				flow += f
				f = self.dfs(s, t, self.INF)
		return flow
(n, m) = map(int, input().split())
s = [list(input()) for i in range(n)]
dc = Dinic(n * m + 2)
start = n * m
goal = n * m + 1
for i in range(n):
	for j in range(m):
		if (i + j) % 2 == 0:
			dc.add_edge(start, m * i + j, 1)
		else:
			dc.add_edge(m * i + j, goal, 1)
for i in range(n):
	for j in range(m):
		if j + 1 < m and s[i][j] == '.' and (s[i][j + 1] == '.'):
			(u, v) = (m * i + j, m * i + j + 1)
			if (i + j) % 2 == 1:
				(u, v) = (v, u)
			dc.add_edge(u, v, 1)
		if i + 1 < n and s[i][j] == '.' and (s[i + 1][j] == '.'):
			(u, v) = (m * i + j, m * (i + 1) + j)
			if (i + j) % 2 == 1:
				(u, v) = (v, u)
			dc.add_edge(u, v, 1)
ans = dc.max_flow(start, goal)
for u in range(n * m + 2):
	for (v, cap, _) in dc.graph[u]:
		(ui, uj) = divmod(u, m)
		(vi, vj) = divmod(v, m)
		if (ui + uj) % 2 == 0 and cap == 0 and (u != start) and (u != goal) and (v != start) and (v != goal):
			if ui + 1 == vi:
				s[ui][uj] = 'v'
				s[vi][vj] = '^'
			elif ui == vi + 1:
				s[ui][uj] = '^'
				s[vi][vj] = 'v'
			elif uj + 1 == vj:
				s[ui][uj] = '>'
				s[vi][vj] = '<'
			elif uj == vj + 1:
				s[ui][uj] = '<'
				s[vi][vj] = '>'
print(ans)
for res in s:
	print(''.join(res))


import sys
input = sys.stdin.readline
(N, M) = map(int, input().split())
MAP = [list(input().strip()) for i in range(N)]
start = N * M + 2
goal = N * M + 3
EDGE = [set() for i in range(N * M + 5)]
for i in range(N):
	for j in range(M):
		if (i + j) % 2 == 0 and MAP[i][j] == '.':
			EDGE[start].add(i * M + j)
			for (x, y) in [(i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)]:
				if 0 <= x < N and 0 <= y < M and (MAP[x][y] == '.'):
					EDGE[i * M + j].add(x * M + y)
		if (i + j) % 2 == 1 and MAP[i][j] == '.':
			EDGE[i * M + j].add(goal)
count = 0
while True:
	USED = [0] * (N * M + 5)
	ROUTE = [-1] * (N * M + 5)
	Q = [start]
	while Q:
		NOW = Q.pop()
		if NOW == goal:
			break
		for to in EDGE[NOW]:
			if USED[to] == 0:
				ROUTE[to] = NOW
				USED[to] = 1
				Q.append(to)
	else:
		break
	count += 1
	i = goal
	while i != start:
		j = ROUTE[i]
		EDGE[j].remove(i)
		EDGE[i].add(j)
		i = j
print(count)
for i in range(N):
	for j in range(M):
		if (i + j) % 2 == 1:
			for to in EDGE[i * M + j]:
				if M > 1 and to == i * M + j - 1:
					MAP[i][j] = '<'
					MAP[i][j - 1] = '>'
				elif M > 1 and to == i * M + j + 1:
					MAP[i][j] = '>'
					MAP[i][j + 1] = '<'
				elif to == i * M + j - M:
					MAP[i][j] = '^'
					MAP[i - 1][j] = 'v'
				elif to == i * M + j + M:
					MAP[i][j] = 'v'
					MAP[i + 1][j] = '^'
for m in MAP:
	print(''.join(m))


from collections import deque

class mf_graph:

	def __init__(self, N):
		self.N = N
		self.graph = [[] for _ in range(N)]

	def add_edge(self, v, w, cap):
		edge = [w, cap, None]
		edge[2] = rev_edge = [v, 0, edge]
		self.graph[v].append(edge)
		self.graph[w].append(rev_edge)

	def bfs(self, s, t):
		self.level = [None] * self.N
		dq = deque([s])
		self.level[s] = 0
		while dq:
			v = dq.popleft()
			nlevel = self.level[v] + 1
			for (w, cap, _) in self.graph[v]:
				if cap and self.level[w] is None:
					self.level[w] = nlevel
					dq.append(w)
		return self.level[t] is not None

	def dfs(self, s, v, f):
		if v == s:
			return f
		for rev in self.it[v]:
			(w, _, e) = rev
			cap = e[1]
			if cap and self.level[w] is not None:
				if self.level[v] > self.level[w]:
					d = self.dfs(s, w, min(f, cap))
					if d:
						e[1] -= d
						rev[1] += d
						return d
		return 0

	def flow(self, s, t, flow_limit=float('inf')):
		flow = 0
		while self.bfs(s, t):
			(*self.it,) = map(iter, self.graph)
			f = flow_limit
			while f:
				f = self.dfs(s, t, flow_limit - flow)
				flow += f
		return flow

	def min_cut(self, s):
		visited = [False] * self.N
		dq = deque([s])
		while dq:
			v = dq.pop()
			visited[v] = True
			for (w, cap, _) in self.graph[v]:
				if cap and (not visited[w]):
					dq.append(w)
(N, M) = map(int, input().split())
S = [list(input()) for i in range(N)]
dc = mf_graph(N * M + 2)
s = N * M
t = N * M + 1
for i in range(N):
	for j in range(M):
		if (i + j) % 2 == 0:
			dc.add_edge(s, M * i + j, 1)
		else:
			dc.add_edge(M * i + j, t, 1)
for i in range(N):
	for j in range(M):
		if j + 1 < M and S[i][j] == '.' and (S[i][j + 1] == '.'):
			(u, v) = (M * i + j, M * i + j + 1)
			if (i + j) % 2 == 1:
				(u, v) = (v, u)
			dc.add_edge(u, v, 1)
		if i + 1 < N and S[i][j] == '.' and (S[i + 1][j] == '.'):
			(u, v) = (M * i + j, M * (i + 1) + j)
			if (i + j) % 2 == 1:
				(u, v) = (v, u)
			dc.add_edge(u, v, 1)
print(dc.flow(s, t))
for u in range(N * M + 2):
	for (v, cap, _) in dc.graph[u]:
		(ui, uj) = divmod(u, M)
		(vi, vj) = divmod(v, M)
		if (ui + uj) % 2 == 0 and cap == 0 and (u != s) and (u != t) and (v != s) and (v != t):
			if ui + 1 == vi:
				S[ui][uj] = 'v'
				S[vi][vj] = '^'
			elif ui == vi + 1:
				S[ui][uj] = '^'
				S[vi][vj] = 'v'
			elif uj + 1 == vj:
				S[ui][uj] = '>'
				S[vi][vj] = '<'
			elif uj == vj + 1:
				S[ui][uj] = '<'
				S[vi][vj] = '>'
for res in S:
	print(''.join(res))


from collections import deque

class MF_graph(object):

	def __init__(self, n):
		self.n = n
		self.g = [[] for _ in range(n)]
		self.pos = []

	def add_edge(self, frm, to, cap):
		m = len(self.pos)
		self.pos.append((frm, len(self.g[frm])))
		self.g[frm].append([to, len(self.g[to]), cap])
		self.g[to].append([frm, len(self.g[frm]) - 1, 0])
		return m

	def get_edge(self, i):
		(e_to, e_rev, e_cap) = self.g[self.pos[i][0]][self.pos[i][1]]
		(re_to, _, re_cap) = self.g[e_to][e_rev]
		return (re_to, e_to, e_cap + re_cap, re_cap)

	def edges(self):
		m = len(self.pos)
		for i in range(m):
			yield self.get_edge(i)

	def change_edge(self, i, new_cap, new_flow):
		(f, s) = self.pos[i]
		(rf, rs, _) = self.g[f][s]
		self.g[f][s][2] = new_cap - new_flow
		self.g[rf][rs][2] = new_flow
		return

	def dfs(self, s, v, up):
		if v == s:
			return up
		res = 0
		level_v = self.level[v]
		for i in range(self.iter[v], len(self.g[v])):
			(u_to, u_rev, _) = self.g[v][i]
			if level_v <= self.level[u_to] or self.g[u_to][u_rev][2] == 0:
				continue
			d = self.dfs(s, u_to, min(up - res, self.g[u_to][u_rev][2]))
			if d <= 0:
				continue
			self.g[v][i][2] += d
			self.g[u_to][u_rev][2] -= d
			res += d
			if res == up:
				break
		return res

	def flow(self, s, t, flow_limit=10 ** 18):
		self.iter = [0] * self.n
		flow = 0
		while flow < flow_limit:
			self.level = [-1] * self.n
			self.level[s] = 0
			que = deque([s])
			while que:
				v = que.popleft()
				for (u_to, _, u_cap) in self.g[v]:
					if u_cap == 0 or self.level[u_to] >= 0:
						continue
					self.level[u_to] = self.level[v] + 1
					if u_to == t:
						break
					que.append(u_to)
			if self.level[t] == -1:
				break
			self.iter = [0] * self.n
			while flow < flow_limit:
				f = self.dfs(s, t, flow_limit - flow)
				if not f:
					break
				flow += f
		return flow

	def min_cut(self, s):
		visited = [False] * self.n
		que = deque([s])
		while que:
			v = que.popleft()
			visited[v] = True
			for (u_to, _, u_cap) in self.g[v]:
				if u_cap and (not visited[u_to]):
					visited[u_to] = True
					que.append(u_to)
		return visited
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
(N, M) = map(int, input().split())
grid = [list(input().rstrip()) for _ in range(N)]
g = MF_graph(N * M + 2)
source = N * M
sink = N * M + 1
for i in range(N):
	for j in range(M):
		if grid[i][j] == '#':
			continue
		v = i * M + j
		if (i + j) % 2 == 0:
			g.add_edge(source, v, 1)
		else:
			g.add_edge(v, sink, 1)
for i in range(N):
	for j in range(M):
		if (i + j) % 2 or grid[i][j] == '#':
			continue
		v0 = i * M + j
		if i and grid[i - 1][j] == '.':
			v1 = (i - 1) * M + j
			g.add_edge(v0, v1, 1)
		if j and grid[i][j - 1] == '.':
			v1 = i * M + j - 1
			g.add_edge(v0, v1, 1)
		if i + 1 < N and grid[i + 1][j] == '.':
			v1 = (i + 1) * M + j
			g.add_edge(v0, v1, 1)
		if j + 1 < M and grid[i][j + 1] == '.':
			v1 = i * M + j + 1
			g.add_edge(v0, v1, 1)
res = g.flow(source, sink)
for (frm, to, cap, flow) in g.edges():
	if frm == source or to == sink or flow == 0:
		continue
	(i0, j0) = divmod(frm, M)
	(i1, j1) = divmod(to, M)
	if i0 == i1 + 1:
		grid[i1][j1] = 'v'
		grid[i0][j0] = '^'
	elif j0 == j1 + 1:
		grid[i1][j1] = '>'
		grid[i0][j0] = '<'
	elif i0 == i1 - 1:
		grid[i1][j1] = '^'
		grid[i0][j0] = 'v'
	else:
		grid[i1][j1] = '<'
		grid[i0][j0] = '>'
print(res)
for g in grid:
	print(''.join(g))


from collections import deque
import sys
readline = sys.stdin.readline
INF = 2 ** 62 - 1

def read_int():
	return int(readline())

def read_int_n():
	return list(map(int, readline().split()))

def read_float():
	return float(readline())

def read_float_n():
	return list(map(float, readline().split()))

def read_str():
	return readline().strip()

def read_str_n():
	return readline().strip().split()

def ep(*args):
	print(*args, file=sys.stderr)

def mt(f):
	import time

	def wrap(*args, **kwargs):
		s = time.perf_counter()
		ret = f(*args, **kwargs)
		e = time.perf_counter()
		ep(e - s, 'sec')
		return ret
	return wrap

class Dinic:

	def __init__(self, v):
		self.V = v
		self.G = [list() for _ in range(v)]
		self.level = [0 for _ in range(v)]
		self.iter = [0 for _ in range(v)]
		self.pos = []

	def add_edge(self, from_, to, cap):
		self.pos.append((from_, len(self.G[from_])))
		self.G[from_].append([to, cap, len(self.G[to])])
		self.G[to].append([from_, 0, len(self.G[from_]) - 1])

	def edges(self):
		es = []
		for (f, t) in self.pos:
			e = self.G[f][t]
			re = self.G[e[0]][e[2]]
			e = [f, e[0], e[1] + re[1], re[1]]
			es.append(e)
		return es

	def bfs(self, s):
		self.level = [-1 for _ in range(self.V)]
		self.level[s] = 0
		que = deque()
		que.append(s)
		while que:
			v = que.popleft()
			for i in range(len(self.G[v])):
				e = self.G[v][i]
				if e[1] > 0 and self.level[e[0]] < 0:
					self.level[e[0]] = self.level[v] + 1
					que.append(e[0])

	def dfs(self, v, t, f):
		if v == t:
			return f
		for i in range(self.iter[v], len(self.G[v])):
			self.iter[v] = i
			e = self.G[v][i]
			if e[1] > 0 and self.level[v] < self.level[e[0]]:
				d = self.dfs(e[0], t, min(f, e[1]))
				if d > 0:
					e[1] -= d
					self.G[e[0]][e[2]][1] += d
					return d
		return 0

	def max_flow(self, s, t):
		flow = 0
		while True:
			self.bfs(s)
			if self.level[t] < 0:
				return flow
			self.iter = [0 for _ in range(self.V)]
			f = self.dfs(s, t, INF)
			while f > 0:
				flow += f
				f = self.dfs(s, t, INF)

@mt
def slv(N, M, S):
	S = [list(s) for s in S]
	g = Dinic(N * M + 2)
	s = N * M
	t = s + 1
	for i in range(N):
		for j in range(M):
			if S[i][j] == '#':
				continue
			v = i * M + j
			if (i + j) % 2 == 0:
				g.add_edge(s, v, 1)
			else:
				g.add_edge(v, t, 1)
	for i in range(N):
		for j in range(M):
			if S[i][j] == '#':
				continue
			if (i + j) % 2 == 1:
				continue
			v0 = i * M + j
			for (x, y) in [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]:
				if not (0 <= x < N and 0 <= y < M):
					continue
				v1 = x * M + y
				g.add_edge(v0, v1, 1)
	print(g.max_flow(s, t))
	for (from_, to, _, flow) in g.edges():
		if from_ in {s, t} or to in {s, t} or flow == 0:
			continue
		i0 = from_ // M
		j0 = from_ % M
		i1 = to // M
		j1 = to % M
		if i0 == i1 + 1:
			S[i1][j1] = 'v'
			S[i0][j0] = '^'
		elif j0 == j1 + 1:
			S[i1][j1] = '>'
			S[i0][j0] = '<'
		elif i0 == i1 - 1:
			S[i1][j1] = '^'
			S[i0][j0] = 'v'
		else:
			S[i1][j1] = '<'
			S[i0][j0] = '>'
	for s in S:
		print(''.join(s))

def main():
	(N, M) = read_int_n()
	S = [read_str() for _ in range(N)]
	slv(N, M, S)
main()


(N, M) = map(int, input().split())
S = [list(input()) for i in range(N)]
V = N * M
G = [[] for i in range(V)]
ma = [0] * V
us = [0] * V

def ae(u, v):
	G[u].append(v)
	G[v].append(u)

def df(v):
	us[v] = 1
	for i in range(len(G[v])):
		u = G[v][i]
		w = ma[u]
		if w < 0 or (not us[w] and df(w)):
			ma[v] = u
			ma[u] = v
			return 1
	return 0

def mat():
	r = 0
	for i in range(V):
		ma[i] = -1
	for v in range(V):
		if ma[v] < 0:
			for i in range(V):
				us[i] = 0
			if df(v):
				r += 1
	return r
w4y = [1, 0, -1, 0]
w4x = [0, 1, 0, -1]
for i in range(N):
	for j in range(M):
		if i + j + 1 & 1 and S[i][j] == '.':
			for k in range(4):
				k = [i + w4y[k], j + w4x[k]]
				if min(k) < 0 or k[0] >= N or k[1] >= M:
					continue
				if S[k[0]][k[1]] == '.':
					ae(i * M + j, k[0] * M + k[1])
print(mat())
for i in range(N):
	for j in range(M):
		if ma[i * M + j] < 0:
			continue
		if ma[i * M + j] == i * M + j + M:
			S[i][j] = 'v'
		elif ma[i * M + j] == i * M + j - M:
			S[i][j] = '^'
		elif ma[i * M + j] == i * M + j + 1:
			S[i][j] = '>'
		elif ma[i * M + j] == i * M + j - 1:
			S[i][j] = '<'
	print(''.join(S[i]))


mod = 1000000007
eps = 10 ** (-9)

def main():
	import sys
	input = sys.stdin.readline
	from collections import deque

	class Dinic:

		def __init__(self, N):
			self.N = N
			self.adj = [[] for _ in range(N + 1)]
			self.lv = None
			self.progress = None
			self.inf = 1 << 60

		def add_edge(self, fr, to, cap):
			forward = [to, cap, None]
			backward = forward[2] = [fr, 0, forward]
			self.adj[fr].append(forward)
			self.adj[to].append(backward)

		def bfs(self, s, t):
			que = deque([s])
			lv = [-1] * (self.N + 1)
			lv[s] = 0
			while que:
				v = que.popleft()
				lvv = lv[v]
				for (u, cap, _) in self.adj[v]:
					if cap and lv[u] == -1:
						que.append(u)
						lv[u] = lvv + 1
						if u == t:
							break
			self.lv = lv

		def dfs(self, s, t, flow):
			st = deque([s])
			st_f = deque([flow])
			while st:
				v = st[-1]
				f = st_f[-1]
				if v == t:
					for i in range(len(st) - 1, 0, -1):
						p = st[i - 1]
						edge = self.adj[p][self.progress[p] - 1]
						edge[1] -= f
						edge[2][1] += f
						v = p
					return f
				if self.progress[v] == len(self.adj[v]):
					st.pop()
					st_f.pop()
					continue
				else:
					adj_v = self.adj[v]
					for i in range(self.progress[v], len(adj_v)):
						i = self.progress[v]
						self.progress[v] = i + 1
						(u, cap, rev) = adj_v[i]
						if not cap or self.lv[u] != self.lv[v] + 1:
							continue
						else:
							st.append(u)
							st_f.append(min(st_f[-1], cap))
							break

		def max_flow(self, s, t):
			flow = 0
			while True:
				self.bfs(s, t)
				if self.lv[t] < 0:
					return flow
				self.progress = [0] * (self.N + 1)
				flow_new = self.dfs(s, t, self.inf)
				while flow_new:
					flow += flow_new
					flow_new = self.dfs(s, t, self.inf)
	(H, W) = map(int, input().split())
	grid = [[''] * W for _ in range(H)]
	for h in range(H):
		S = input().rstrip('\n')
		for w in range(W):
			grid[h][w] = S[w]
	D = Dinic(H * W + 2)
	s = H * W + 1
	t = H * W + 2
	dhw = [(0, 1), (0, -1), (1, 0), (-1, 0)]
	for h in range(H):
		for w in range(W):
			if (h + w) % 2 == 0:
				D.add_edge(s, h * W + w + 1, 1)
			else:
				D.add_edge(h * W + w + 1, t, 1)
			if grid[h][w] == '.' and (h + w) % 2 == 0:
				for (dh, dw) in dhw:
					(h_new, w_new) = (h + dh, w + dw)
					if 0 <= h_new < H and 0 <= w_new < W:
						if grid[h_new][w_new] == '.':
							D.add_edge(h * W + w + 1, h_new * W + w_new + 1, 1)
	flow = D.max_flow(s, t)
	print(flow)
	for h in range(H):
		for w in range(W):
			if (h + w) % 2 == 0:
				hw = h * W + w + 1
				for (hw_new, cap, _) in D.adj[hw]:
					if hw_new == s:
						continue
					if cap == 0:
						(h_new, w_new) = divmod(hw_new - 1, W)
						if h == h_new:
							if w < w_new:
								(grid[h][w], grid[h][w_new]) = '><'
							else:
								(grid[h][w_new], grid[h][w]) = '><'
						elif h < h_new:
							(grid[h][w], grid[h_new][w]) = 'v^'
						else:
							(grid[h_new][w], grid[h][w]) = 'v^'
	for h in range(H):
		print(''.join(grid[h]))
main()


class Weigthed_Digraph:

	def __init__(self, vertex=[]):
		self.vertex = set(vertex)
		self.edge_number = 0
		self.vertex_number = len(vertex)
		self.adjacent_out = {v: {} for v in vertex}
		self.adjacent_in = {v: {} for v in vertex}

	def add_vertex(self, *adder):
		for v in adder:
			if v not in self.vertex:
				self.adjacent_in[v] = {}
				self.adjacent_out[v] = {}
				self.vertex_number += 1
				self.vertex.add(v)

	def add_edge(self, From, To, weight=1):
		for v in [From, To]:
			if v not in self.vertex:
				self.add_vertex(v)
		if To not in self.adjacent_in[From]:
			self.edge_number += 1
		self.adjacent_out[From][To] = weight
		self.adjacent_in[To][From] = weight

	def remove_edge(self, From, To):
		for v in [From, To]:
			if v not in self.vertex:
				self.add_vertex(v)
		if To in self.adjacent_out[From]:
			del self.adjacent_out[From][To]
			del self.adjacent_in[To][From]
			self.edge_number -= 1

	def remove_vertex(self, *vertexes):
		for v in vertexes:
			if v in self.vertex:
				self.vertex_number -= 1
				for u in self.adjacent_out[v]:
					del self.adjacent_in[u][v]
					self.edge_number -= 1
				del self.adjacent_out[v]
				for u in self.adjacent_in[v]:
					del self.adjacent_out[u][v]
					self.edge_number -= 1
				del self.adjacent_in[v]

	def add_walk(self, *walk):
		pass

	def add_cycle(self, *cycle):
		pass

	def __vertex_swap(self, p, q):
		self.vertex.sort()

	def vertex_exist(self, v):
		return v in self.vertex

	def edge_exist(self, From, To):
		if not (self.vertex_exist(From) and self.vertex_exist(To)):
			return False
		return To in self.adjacent_out[From]

	def neighbohood(self, v):
		if not self.vertex_exist(v):
			return []
		return list(self.adjacent[v])

	def out_degree(self, v):
		if not self.vertex_exist(v):
			return 0
		return len(self.adjacent_out[v])

	def in_degree(self, v):
		if not self.vertex_exist(v):
			return 0
		return len(self.adjacent_in[v])

	def degree(self, v):
		if not self.vertex_exist(v):
			return 0
		return self.out_degree(v) - self.in_degree(v)

	def vertex_count(self):
		return len(self.vertex)

	def edge_count(self):
		return self.edge_number

	def connected_component(self, v):
		pass

def Flow_by_Dinic(D, source, sink, Mode=False):
	from collections import deque
	from copy import copy

	def bfs(s, t):
		for v in D.vertex:
			Level[v] = None
		Q = deque([s])
		Level[s] = 0
		while Q:
			v = Q.popleft()
			for (w, cap, _) in H[v]:
				if cap and Level[w] is None:
					Level[w] = Level[v] + 1
					Q.append(w)
		return Level[t] is not None

	def dfs(v, t, f):
		if v == t:
			return f
		for e in H[v]:
			(w, cap, rev) = e
			if cap and Level[v] < Level[w]:
				d = dfs(w, t, min(f, cap))
				if d:
					e[1] -= d
					rev[1] += d
					return d
		return 0
	(s, t) = (source, sink)
	inf = float('inf')
	flow = 0
	Level = {v: None for v in D.vertex}
	H = {v: [] for v in D.vertex}
	for u in D.vertex:
		for v in D.adjacent_out[u]:
			F = [v, D.adjacent_out[u][v], None]
			F[2] = B = [u, 0, F]
			H[u].append(F)
			H[v].append(B)
	while bfs(s, t):
		f = inf
		while f:
			f = dfs(s, t, inf)
			flow += f
	if Mode:
		R = {}
		for v in D.vertex:
			R[v] = {}
			for S in H[v]:
				w = S[0]
				if w in D.adjacent_out[v]:
					R[v][w] = S[-1][1]
		return (flow, R)
	else:
		return flow
(N, M) = map(int, input().split())
D = Weigthed_Digraph([(y, x) for x in range(1, M + 1) for y in range(1, N + 1)])
D.add_vertex('s', 't')
S = ['*' * (M + 2) for _ in range(N + 2)]
for i in range(1, N + 1):
	S[i] = '*' + input() + '*'
H = [(1, 0), (-1, 0), (0, 1), (0, -1)]
for y in range(1, N + 1):
	for x in range(1, M + 1):
		if S[y][x] != '.':
			continue
		if (x + y) % 2:
			D.add_edge('s', (y, x), 1)
			for (a, b) in H:
				if S[y + a][x + b] == '.':
					D.add_edge((y, x), (y + a, x + b), 1)
		else:
			D.add_edge((y, x), 't', 1)
(flow, F) = Flow_by_Dinic(D, 's', 't', True)
U = [[S[j][i] for i in range(M + 2)] for j in range(N + 2)]
for y in range(1, N + 1):
	for x in range(1, M + 1):
		for C in F[y, x]:
			if isinstance(C, str):
				continue
			elif F[y, x][C] == 0:
				continue
			(q, p) = C
			if y + 1 == q and x == p:
				(alpha, beta) = ('v', '^')
			elif y - 1 == q and x == p:
				(alpha, beta) = ('^', 'v')
			elif y == q and x + 1 == p:
				(alpha, beta) = ('>', '<')
			elif y == q and x - 1 == p:
				(alpha, beta) = ('<', '>')
			U[y][x] = alpha
			U[q][p] = beta
print(flow)
Y = [''.join(T[1:-1]) for T in U[1:-1]]
print('\n'.join(Y))


import sys
from collections import deque
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7

class Dinic:

	def __init__(self, N):
		self.N = N
		self.G = [[] for _ in range(N)]

	def add_edge(self, fr, to, cap):
		forward = [to, cap, None]
		forward[2] = backward = [fr, 0, forward]
		self.G[fr].append(forward)
		self.G[to].append(backward)

	def add_multi_edge(self, v1, v2, cap1, cap2):
		edge1 = [v2, cap1, None]
		edge1[2] = edge2 = [v1, cap2, edge1]
		self.G[v1].append(edge1)
		self.G[v2].append(edge2)

	def bfs(self, s, t):
		self.level = [None] * self.N
		self.level[s] = 0
		que = deque([s])
		G = self.G
		while que:
			v = que.popleft()
			next_level = self.level[v] + 1
			for (w, cap, _) in G[v]:
				if cap and self.level[w] is None:
					self.level[w] = next_level
					que.append(w)
		return self.level[t] is not None

	def dfs(self, v, t, f):
		if v == t:
			return f
		level = self.level
		for e in self.it[v]:
			(w, cap, rev) = e
			if cap and level[v] < level[w]:
				d = self.dfs(w, t, min(f, cap))
				if d:
					e[1] -= d
					rev[1] += d
					return d
		return 0

	def flow(self, s, t):
		flow = 0
		INF = 10 ** 9 + 7
		G = self.G
		while self.bfs(s, t):
			(*self.it,) = map(iter, self.G)
			f = INF
			while f:
				f = self.dfs(s, t, INF)
				flow += f
		return flow

def resolve():
	(n, m) = map(int, input().split())
	grid = [list(input().rstrip()) for _ in range(n)]
	mf = Dinic(n * m + 2)
	start = n * m
	end = start + 1
	for i in range(n):
		for j in range(m):
			if grid[i][j] == '#':
				continue
			if (i + j) % 2 == 0:
				mf.add_edge(start, i * m + j, 1)
				for (di, dj) in [(0, 1), (1, 0), (-1, 0), (0, -1)]:
					(next_i, next_j) = (i + di, j + dj)
					if next_i < 0 or next_i >= n or next_j < 0 or (next_j >= m):
						continue
					if grid[next_i][next_j] == '#':
						continue
					mf.add_edge(i * m + j, next_i * m + next_j, 1)
			else:
				mf.add_edge(i * m + j, end, 1)
	res = mf.flow(start, end)
	for y in range(n):
		for x in range(m):
			if grid[y][x] == '#' or (y + x) % 2 or y * m + x == start or (y * m + x == end):
				continue
			for (to, cap, _) in mf.G[y * m + x]:
				if cap == 0 and to != start and (to != end):
					(next_y, next_x) = divmod(to, m)
					if y + 1 == next_y:
						grid[y][x] = 'v'
						grid[next_y][next_x] = '^'
					elif y == next_y + 1:
						grid[y][x] = '^'
						grid[next_y][next_x] = 'v'
					elif x + 1 == next_x:
						grid[y][x] = '>'
						grid[next_y][next_x] = '<'
					elif x == next_x + 1:
						grid[y][x] = '<'
						grid[next_y][next_x] = '>'
	print(res)
	print(*[''.join(ret) for ret in grid], sep='\n')
resolve()


class maxflow:

	def __init__(self, n):
		self.pos = []
		self.g = [[] for _ in range(n)]
		self.n = n

	def add_edge(self, frm, to, cap):
		self.pos.append((frm, len(self.g[frm])))
		self.g[frm].append([to, len(self.g[to]), cap])
		self.g[to].append([frm, len(self.g[frm]) - 1, 0])
		return len(self.pos) - 1

	def get_edge(self, i):
		e = self.g[self.pos[i][0]][self.pos[i][1]]
		re = self.g[e[0]][e[1]]
		return (self.pos[i][0], e[0], e[2] + re[2], re[2])

	def edges(self):
		return [self.get_edge(i) for i in range(len(self.pos))]

	def change_edge(self, i, new_cap, new_flow):
		e = self.g[self.pos[i][0]][self.pos[i][1]]
		re = self.g[e[0]][e[1]]
		e[2] = new_cap - new_flow
		re[2] = new_flow

	def flow(self, s, t, flow_limit=-1):
		if flow_limit < 0:
			flow_limit = 10 ** 100
		it = [0] * self.n

		def bfs():
			L = [-1] * self.n
			L[s] = 0
			Q = [s]
			while Q:
				v = Q.pop()
				for e in self.g[v]:
					if e[2] == 0 or L[e[0]] >= 0:
						continue
					L[e[0]] = L[v] + 1
					if e[0] == t:
						return L
					Q.append(e[0])
			return L

		def dfs(v, up):
			if v == s:
				return up
			res = 0
			lv = L[v]
			for i in range(it[v], len(self.g[v])):
				e = self.g[v][i]
				if lv <= L[e[0]] or self.g[e[0]][e[1]][2] == 0:
					continue
				d = dfs(e[0], min(up - res, self.g[e[0]][e[1]][2]))
				if d <= 0:
					continue
				self.g[v][i][2] += d
				self.g[e[0]][e[1]][2] -= d
				res += d
				if res == up:
					break
			return res
		flow = 0
		while flow < flow_limit:
			L = bfs()
			if L[t] == -1:
				break
			it = [0] * self.n
			while flow < flow_limit:
				f = dfs(t, flow_limit - flow)
				if not f:
					break
				flow += f
		return flow

	def min_cut(self, s):
		visited = [0] * self.n
		Q = [s]
		while Q:
			p = Q.pop()
			visited[p] = 1
			for e in self.g[p]:
				if e[2] and visited[e[0]] == 0:
					visited[e[0]] = 1
					Q.append(e[0])
		return visited
(N, M) = map(int, input().split())
mf = maxflow(N * M + 2)
A = [[a for a in input()] for _ in range(N)]
X = [[1 if a == '.' else 0 for a in aa] for aa in A]
s = N * M
t = s + 1
for i in range(N):
	for j in range(M):
		if X[i][j]:
			if (i ^ j) & 1 == 0:
				mf.add_edge(s, i * M + j, 1)
			else:
				mf.add_edge(i * M + j, t, 1)
for i in range(N - 1):
	for j in range(M):
		if X[i][j] and X[i + 1][j]:
			a = i * M + j
			b = a + M
			if (i ^ j) & 1 == 0:
				mf.add_edge(a, b, 1)
			else:
				mf.add_edge(b, a, 1)
for i in range(N):
	for j in range(M - 1):
		if X[i][j] and X[i][j + 1]:
			a = i * M + j
			b = a + 1
			if (i ^ j) & 1 == 0:
				mf.add_edge(a, b, 1)
			else:
				mf.add_edge(b, a, 1)
fl = mf.flow(s, t)
for (s, t, _, f) in mf.edges():
	if f and max(s, t) < N * M:
		if s > t:
			(s, t) = (t, s)
		(i, j) = (s // M, s % M)
		(ii, jj) = (t // M, t % M)
		if i == ii:
			A[i][j] = '>'
			A[ii][jj] = '<'
		else:
			A[i][j] = 'v'
			A[ii][jj] = '^'
print(fl)
for x in A:
	print(''.join(map(str, x)))


from collections import deque

class mf_graph:
	n = 1
	g = [[] for i in range(1)]
	pos = []

	def __init__(self, N):
		self.n = N
		self.g = [[] for i in range(N)]

	def add_edge(self, From, To, cap):
		assert 0 <= From and From < self.n
		assert 0 <= To and To < self.n
		assert 0 <= cap
		m = len(self.pos)
		self.pos.append((From, len(self.g[From])))
		self.g[From].append({'to': To, 'rev': len(self.g[To]), 'cap': cap})
		self.g[To].append({'to': From, 'rev': len(self.g[From]) - 1, 'cap': 0})
		return m

	def get_edge(self, i):
		m = len(self.pos)
		assert 0 <= i and i < m
		_e = self.g[self.pos[i][0]][self.pos[i][1]]
		_re = self.g[_e['to']][_e['rev']]
		return {'from': self.pos[i][0], 'to': _e['to'], 'cap': _e['cap'] + _re['cap'], 'flow': _re['cap']}

	def edges(self):
		m = len(self.pos)
		result = []
		for i in range(m):
			result.append(self.get_edge(i))
		return result

	def change_edge(self, i, new_cap, new_flow):
		m = len(self.pos)
		assert 0 <= i and i < m
		assert 0 <= new_flow and new_flow <= new_cap
		_e = self.g[self.pos[i][0]][self.pos[i][1]]
		_re = self.g[_e['to']][_e['rev']]
		_e['cap'] = new_cap - new_flow
		_re['cap'] = new_flow

	def flow(self, s, t, flow_limit=2 ** 31 - 1):
		assert 0 <= s and s < self.n
		assert 0 <= t and t < self.n
		level = [0 for i in range(self.n)]
		Iter = [0 for i in range(self.n)]
		que = deque([])

		def bfs():
			for i in range(self.n):
				level[i] = -1
			level[s] = 0
			que = deque([])
			que.append(s)
			while len(que) > 0:
				v = que.popleft()
				for e in self.g[v]:
					if e['cap'] == 0 or level[e['to']] >= 0:
						continue
					level[e['to']] = level[v] + 1
					if e['to'] == t:
						return
					que.append(e['to'])

		def dfs(func, v, up):
			if v == s:
				return up
			res = 0
			level_v = level[v]
			for i in range(Iter[v], len(self.g[v])):
				e = self.g[v][i]
				if level_v <= level[e['to']] or self.g[e['to']][e['rev']]['cap'] == 0:
					continue
				d = func(func, e['to'], min(up - res, self.g[e['to']][e['rev']]['cap']))
				if d <= 0:
					continue
				self.g[v][i]['cap'] += d
				self.g[e['to']][e['rev']]['cap'] -= d
				res += d
				if res == up:
					break
			return res
		flow = 0
		while flow < flow_limit:
			bfs()
			if level[t] == -1:
				break
			for i in range(self.n):
				Iter[i] = 0
			while flow < flow_limit:
				f = dfs(dfs, t, flow_limit - flow)
				if not f:
					break
				flow += f
		return flow

	def min_cut(s):
		visited = [False for i in range(self.n)]
		que = deque([])
		que.append(s)
		while len(que) > 0:
			p = que.popleft()
			visited[p] = True
			for e in self.g[p]:
				if e['cap'] and (not visited[e['to']]):
					visited[e['to']] = True
					que.append(e['to'])
		return visited
(N, M) = map(int, input().split())
S = [list(input()) for i in range(N)]
G = mf_graph(N * M + 2)
for i in range(N):
	for j in range(M):
		if S[i][j] == '#':
			continue
		v = i * M + j
		if (i + j) % 2 == 0:
			G.add_edge(N * M, v, 1)
		else:
			G.add_edge(v, N * M + 1, 1)
for i in range(N):
	for j in range(M):
		if (i + j) % 2 or S[i][j] == '#':
			continue
		v0 = i * M + j
		if i > 0 and S[i - 1][j] == '.':
			v1 = (i - 1) * M + j
			G.add_edge(v0, v1, 1)
		if j > 0 and S[i][j - 1] == '.':
			v1 = i * M + (j - 1)
			G.add_edge(v0, v1, 1)
		if i + 1 < N and S[i + 1][j] == '.':
			v1 = (i + 1) * M + j
			G.add_edge(v0, v1, 1)
		if j + 1 < M and S[i][j + 1] == '.':
			v1 = i * M + (j + 1)
			G.add_edge(v0, v1, 1)
print(G.flow(N * M, N * M + 1))
T = [[S[i][j] for j in range(M)] for i in range(N)]
for e in G.edges():
	if e['from'] == N * M or e['to'] == N * M + 1 or e['flow'] == 0:
		continue
	i0 = e['from'] // M
	j0 = e['from'] % M
	i1 = e['to'] // M
	j1 = e['to'] % M
	if i0 == i1 + 1:
		T[i1][j1] = 'v'
		T[i0][j0] = '^'
	elif j0 == j1 + 1:
		T[i1][j1] = '>'
		T[i0][j0] = '<'
	elif i0 == i1 - 1:
		T[i0][j0] = 'v'
		T[i1][j1] = '^'
	else:
		T[i0][j0] = '>'
		T[i1][j1] = '<'
for i in range(N):
	print(''.join(T[i]))


from collections import deque

class MaxFlow:

	def __init__(self, n):
		self.n = n
		self.graph = [[] for _ in range(n)]
		self.pos = []

	def add_edge(self, fr, to, cap):
		m = len(self.pos)
		self.pos.append((fr, len(self.graph[fr])))
		self.graph[fr].append([to, len(self.graph[to]), cap])
		self.graph[to].append([fr, len(self.graph[fr]) - 1, 0])
		return m

	def get_edge(self, idx):
		(to, rev, cap) = self.graph[self.pos[idx][0]][self.pos[idx][1]]
		(rev_to, rev_rev, rev_cap) = self.graph[to][rev]
		return (rev_to, to, cap + rev_cap, rev_cap)

	def edges(self):
		m = len(self.pos)
		for i in range(m):
			yield self.get_edge(i)

	def change_edge(self, idx, new_cap, new_flow):
		(to, rev, cap) = self.graph[self.pos[idx][0]][self.pos[idx][1]]
		self.graph[self.pos[idx][0]][self.pos[idx][1]][2] = new_cap - new_flow
		self.graph[to][rev][2] = new_flow

	def dfs(self, s, v, up):
		if v == s:
			return up
		res = 0
		lv = self.level[v]
		for i in range(self.iter[v], len(self.graph[v])):
			(to, rev, cap) = self.graph[v][i]
			if lv <= self.level[to] or self.graph[to][rev][2] == 0:
				continue
			d = self.dfs(s, to, min(up - res, self.graph[to][rev][2]))
			if d <= 0:
				continue
			self.graph[v][i][2] += d
			self.graph[to][rev][2] -= d
			res += d
			if res == up:
				break
			self.iter[v] += 1
		return res

	def max_flow(self, s, t):
		return self.max_flow_with_limit(s, t, 2 ** 63 - 1)

	def max_flow_with_limit(self, s, t, limit):
		flow = 0
		while flow < limit:
			self.level = [-1] * self.n
			self.level[s] = 0
			queue = deque()
			queue.append(s)
			while queue:
				v = queue.popleft()
				for (to, rev, cap) in self.graph[v]:
					if cap == 0 or self.level[to] >= 0:
						continue
					self.level[to] = self.level[v] + 1
					if to == t:
						break
					queue.append(to)
			if self.level[t] == -1:
				break
			self.iter = [0] * self.n
			while flow < limit:
				f = self.dfs(s, t, limit - flow)
				if not f:
					break
				flow += f
		return flow

	def min_cut(self, s):
		visited = [0] * self.n
		queue = deque()
		queue.append(s)
		while queue:
			p = queue.popleft()
			visited[p] = True
			for (to, rev, cap) in self.graph[p]:
				if cap and (not visited[to]):
					visited[to] = True
					queue.append(to)
		return visited
(n, m) = map(int, input().split())
s = [list(input()) for _ in range(n)]
mf = MaxFlow(n * m + 2)
start = n * m
end = n * m + 1
d = [(1, 0), (-1, 0), (0, 1), (0, -1)]
for i in range(n):
	for j in range(m):
		if s[i][j] == '#':
			continue
		elif (i + j) % 2 == 0:
			mf.add_edge(start, i * m + j, 1)
			for (i1, j1) in d:
				if 0 <= i + i1 < n and 0 <= j + j1 < m:
					if s[i + i1][j + j1] == '.':
						mf.add_edge(i * m + j, (i + i1) * m + (j + j1), 1)
		else:
			mf.add_edge(i * m + j, end, 1)
print(mf.max_flow(start, end))
for i in range(len(mf.pos)):
	(s1, e1, cap, flow) = mf.get_edge(i)
	if flow == 0 or s1 == start or e1 == end:
		continue
	else:
		si = s1 // m
		sj = s1 % m
		ei = e1 // m
		ej = e1 % m
		if s1 - e1 == m:
			s[si][sj] = '^'
			s[ei][ej] = 'v'
		elif e1 - s1 == m:
			s[si][sj] = 'v'
			s[ei][ej] = '^'
		elif s1 - e1 == 1:
			s[si][sj] = '<'
			s[ei][ej] = '>'
		elif e1 - s1 == 1:
			s[si][sj] = '>'
			s[ei][ej] = '<'
for i in s:
	for j in i:
		print(j, end='')
	print()


import sys
from collections import Counter, deque, defaultdict
MOD = 10 ** 9 + 7
INF = 10 ** 9
PI = 3.141592653589793

def read_str():
	return sys.stdin.readline().strip()

def read_int():
	return int(sys.stdin.readline().strip())

def read_ints():
	return map(int, sys.stdin.readline().strip().split())

def read_ints2(x):
	return map(lambda num: int(num) - x, sys.stdin.readline().strip().split())

def read_str_list():
	return list(sys.stdin.readline().strip().split())

def read_int_list():
	return list(map(int, sys.stdin.readline().strip().split()))

def GCD(a: int, b: int) -> int:
	return b if a % b == 0 else GCD(b, a % b)

def LCM(a: int, b: int) -> int:
	return a * b // GCD(a, b)

class Dinic:

	def __init__(self, n):
		self.N = n
		self.level = None
		self.it = None
		self.G = [[] for i in range(self.N)]

	def add_edge(self, _from, _to, cap):
		self.G[_from].append([_to, cap, len(self.G[_to])])
		self.G[_to].append([_from, 0, len(self.G[_from]) - 1])

	def add_multi_edge(self, v1, v2, cap1, cap2):
		edge1 = [v2, cap1, None]
		edge1[2] = edge2 = [v1, cap2, edge1]
		self.G[v1].append(edge1)
		self.G[v2].append(edge2)

	def bfs(self, s):
		level = [-1] * self.N
		level[s] = 0
		que = deque([s])
		while que:
			v = que.popleft()
			for (to, cap, rev) in self.G[v]:
				if cap > 0 and level[to] < 0:
					level[to] = level[v] + 1
					que.append(to)
		self.level = level

	def dfs(self, v, t, flow):
		if v == t:
			return flow
		for i in range(self.it[v], len(self.G[v])):
			self.it[v] = i
			(to, cap, rev) = e = self.G[v][i]
			if cap > 0 and self.level[v] < self.level[to]:
				d = self.dfs(to, t, min(flow, cap))
				if d > 0:
					e[1] -= d
					self.G[to][rev][1] += d
					return d
		return 0

	def max_flow(self, s, t):
		flow = 0
		INF = 10 ** 18
		while True:
			self.bfs(s)
			if self.level[t] < 0:
				return flow
			self.it = [0] * self.N
			f = self.dfs(s, t, INF)
			while f > 0:
				flow += f
				f = self.dfs(s, t, INF)

def Main():
	(n, m) = read_ints()
	grid = [list(read_str()) for _ in range(n)]
	mf = Dinic(n * m + 2)
	start = n * m
	end = start + 1
	dir = [(1, 0), (0, 1)]
	for y in range(n):
		for x in range(m):
			if (y + x) % 2 == 0:
				mf.add_edge(start, m * y + x, 1)
			else:
				mf.add_edge(m * y + x, end, 1)
			if grid[y][x] == '.':
				for (dy, dx) in dir:
					ny = y + dy
					nx = x + dx
					if ny < n and nx < m and (grid[ny][nx] == '.'):
						(f, t) = (y * m + x, ny * m + nx)
						if (y + x) % 2:
							(f, t) = (t, f)
						mf.add_edge(f, t, 1)
	ans = mf.max_flow(start, end)
	for y in range(n):
		for x in range(m):
			for (to, cap, rev) in mf.G[y * m + x]:
				(ny, nx) = divmod(to, m)
				if (y + x) % 2 == 0 and cap == 0 and (to != start) and (to != end) and (y * m + x != start) and (y * m + x != end):
					if y + 1 == ny:
						grid[y][x] = 'v'
						grid[ny][nx] = '^'
					elif y == ny + 1:
						grid[y][x] = '^'
						grid[ny][nx] = 'v'
					elif x + 1 == nx:
						grid[y][x] = '>'
						grid[ny][nx] = '<'
					elif x == nx + 1:
						grid[y][x] = '<'
						grid[ny][nx] = '>'
	print(ans)
	print(*[''.join(ret) for ret in grid], sep='\n')
Main()


def main():
	import collections

	class Dinic:

		def __init__(self, vnum):
			self.edge = [[] for i in range(vnum)]
			self.n = vnum
			self.inf = 10 ** 10

		def add_edge(self, start, end, c):
			self.edge[start].append([end, c, len(self.edge[end])])
			self.edge[end].append([start, 0, len(self.edge[start]) - 1])

		def bfs(self, vst):
			dist = [-1] * self.n
			dist[vst] = 0
			Q = collections.deque([vst])
			while Q:
				nv = Q.popleft()
				for (vt, c, r) in self.edge[nv]:
					if dist[vt] == -1 and c > 0:
						dist[vt] = dist[nv] + 1
						Q.append(vt)
			self.dist = dist

		def dfs(self, nv, en, nf):
			nextv = self.nextv
			if nv == en:
				return nf
			dist = self.dist
			ist = nextv[nv]
			for (i, (vt, c, r)) in enumerate(self.edge[nv][ist:], ist):
				if dist[nv] < dist[vt] and c > 0:
					df = self.dfs(vt, en, min(nf, c))
					if df > 0:
						self.edge[nv][i][1] -= df
						self.edge[vt][r][1] += df
						return df
				nextv[nv] += 1
			return 0

		def get_max_flow(self, st, en):
			mf = 0
			while True:
				self.bfs(st)
				if self.dist[en] == -1:
					break
				self.nextv = [0] * self.n
				while True:
					fl = self.dfs(st, en, self.inf)
					if fl > 0:
						mf += fl
					else:
						break
			return mf
	mod = 10 ** 9 + 7
	(N, M) = map(int, input().split())
	S = []
	for _ in range(N):
		s = list(input())
		S.append(s)
	din = Dinic(N * M + 2)
	s = N * M
	t = N * M + 1
	for i in range(N):
		for j in range(M):
			if S[i][j] == '#':
				continue
			v = M * i + j
			if (i + j) % 2 == 1:
				din.add_edge(s, v, 1)
			else:
				din.add_edge(v, t, 1)
	dx = [0, 0, 1, -1]
	dy = [1, -1, 0, 0]
	for i in range(N):
		for j in range(M):
			if S[i][j] == '#':
				continue
			v = M * i + j
			if (i + j) % 2 == 1:
				for k in range(4):
					ni = i + dx[k]
					nj = j + dy[k]
					if 0 <= ni < N and 0 <= nj < M:
						if S[ni][nj] == '#':
							continue
						nv = M * ni + nj
						din.add_edge(v, nv, 1)
	ans = din.get_max_flow(s, t)
	T = [s[:] for s in S]
	for v in range(N * M):
		(i, j) = divmod(v, M)
		if (i + j) % 2 == 1:
			if S[i][j] == '.':
				for (nv, cap, _) in din.edge[v]:
					if cap == 0 and nv != t and (nv != s):
						(ni, nj) = divmod(nv, M)
						if i == ni:
							if j < nj:
								T[i][j] = '>'
								T[ni][nj] = '<'
							else:
								T[i][j] = '<'
								T[ni][nj] = '>'
						elif i < ni:
							T[i][j] = 'v'
							T[ni][nj] = '^'
						else:
							T[i][j] = '^'
							T[ni][nj] = 'v'
	print(ans)
	for i in range(N):
		print(''.join(map(str, T[i])))
main()


import sys
from collections import deque
from copy import deepcopy
sys.setrecursionlimit(10 ** 7)

def MI():
	return map(int, sys.stdin.readline().rstrip().split())

def LS2():
	return list(sys.stdin.readline().rstrip())

class Dinic:

	def __init__(self, N):
		self.N = N
		self.G = [[] for _ in range(N)]

	def add_edge(self, fr, to, cap):
		forward = [to, cap, None]
		forward[2] = backward = [fr, 0, forward]
		self.G[fr].append(forward)
		self.G[to].append(backward)

	def add_multi_edge(self, v1, v2, cap1, cap2):
		edge1 = [v2, cap1, None]
		edge1[2] = edge2 = [v1, cap2, edge1]
		self.G[v1].append(edge1)
		self.G[v2].append(edge2)

	def bfs(self, s, t):
		self.level = level = [None] * self.N
		deq = deque([s])
		level[s] = 0
		G = self.G
		while deq:
			v = deq.popleft()
			lv = level[v] + 1
			for (w, cap, _) in G[v]:
				if cap and level[w] is None:
					level[w] = lv
					deq.append(w)
		return level[t] is not None

	def dfs(self, v, t, f):
		if v == t:
			return f
		level = self.level
		for e in self.it[v]:
			(w, cap, rev) = e
			if cap and level[v] < level[w]:
				d = self.dfs(w, t, min(f, cap))
				if d:
					e[1] -= d
					rev[1] += d
					return d
		return 0

	def flow(self, s, t):
		flow = 0
		INF = 10 ** 9 + 7
		G = self.G
		while self.bfs(s, t):
			(*self.it,) = map(iter, self.G)
			f = INF
			while f:
				f = self.dfs(s, t, INF)
				flow += f
		return flow
(N, M) = MI()
S = [LS2() for _ in range(N)]
D = Dinic(N * M + 2)
(s, t) = (N * M, N * M + 1)
for i in range(N):
	for j in range(M):
		if (i + j) % 2 == 0:
			D.add_edge(s, M * i + j, 1)
		else:
			D.add_edge(M * i + j, t, 1)
for i in range(N - 1):
	for j in range(M):
		if S[i][j] == S[i + 1][j] == '.':
			(a, b) = (M * i + j, M * (i + 1) + j)
			if (i + j) % 2 == 1:
				(a, b) = (b, a)
			D.add_edge(a, b, 1)
for i in range(N):
	for j in range(M - 1):
		if S[i][j] == S[i][j + 1] == '.':
			(a, b) = (M * i + j, M * i + (j + 1))
			if (i + j) % 2 == 1:
				(a, b) = (b, a)
			D.add_edge(a, b, 1)
print(D.flow(s, t))
ANS = deepcopy(S)
for a in range(N * M):
	for (b, cap, _) in D.G[a]:
		if b == s or b == t:
			continue
		(ai, aj) = divmod(a, M)
		(bi, bj) = divmod(b, M)
		if (ai + aj) % 2 == 0 and cap == 0:
			if ai + 1 == bi:
				ANS[ai][aj] = 'v'
				ANS[bi][bj] = '^'
			elif ai == bi + 1:
				ANS[ai][aj] = '^'
				ANS[bi][bj] = 'v'
			elif aj + 1 == bj:
				ANS[ai][aj] = '>'
				ANS[bi][bj] = '<'
			elif aj == bj + 1:
				ANS[ai][aj] = '<'
				ANS[bi][bj] = '>'
for i in range(N):
	print(''.join(ANS[i]))


from collections import deque
from sys import setrecursionlimit
setrecursionlimit(10 ** 9)

class Dinic:

	def __init__(self, n):
		self.n = n
		self.G = [[] for _ in range(n)]

	def add_edge(self, fr, to, cap):
		forward = [to, cap, None]
		forward[2] = backward = [fr, 0, forward]
		self.G[fr].append(forward)
		self.G[to].append(backward)

	def bfs(self, source, sink):
		self.level = level = [None] * self.n
		deq = deque([source])
		level[source] = 0
		G = self.G
		while deq:
			v = deq.popleft()
			lv = level[v] + 1
			for (w, cap, _) in G[v]:
				if cap and level[w] is None:
					level[w] = lv
					deq.append(w)
		return level[sink] is not None

	def dfs(self, v, sink, f):
		if v == sink:
			return f
		level = self.level
		for edge in self.it[v]:
			(w, cap, rev) = edge
			if cap and level[v] < level[w]:
				d = self.dfs(w, sink, min(f, cap))
				if d:
					edge[1] -= d
					rev[1] += d
					return d
		return 0

	def flow(self, source, sink, inf=2 ** 63 - 1):
		flow = 0
		G = self.G
		while self.bfs(source, sink):
			(*self.it,) = map(iter, self.G)
			f = inf
			while f:
				f = self.dfs(source, sink, inf)
				flow += f
		return flow
from sys import stdin

def input():
	return stdin.readline().strip()

def main():
	(n, m) = map(int, input().split())
	s = [list(input()) for _ in range(n)]
	dnc = Dinic(n * m + 2)
	source = n * m
	sink = n * m + 1
	d = ((1, 0), (-1, 0), (0, 1), (0, -1))
	for i in range(n):
		for j in range(m):
			if s[i][j] == '#':
				continue
			ind = m * i + j
			if (i + j) % 2 == 0:
				dnc.add_edge(source, ind, 1)
				for (dx, dy) in d:
					if 0 <= i + dx < n and 0 <= j + dy < m and (s[i + dx][j + dy] == '.'):
						dnc.add_edge(ind, m * (i + dx) + j + dy, 1)
			else:
				dnc.add_edge(ind, sink, 1)
	print(dnc.flow(source, sink))
	for ind in range(n * m):
		(i, j) = divmod(ind, m)
		if (i + j) % 2 == 1:
			continue
		for (v, cap, rev) in dnc.G[ind]:
			if v == source or v == sink or rev[1] == 0:
				continue
			(x, y) = divmod(v, m)
			if i + 1 == x:
				s[i][j] = 'v'
				s[x][y] = '^'
			elif i - 1 == x:
				s[i][j] = '^'
				s[x][y] = 'v'
			elif j + 1 == y:
				s[i][j] = '>'
				s[x][y] = '<'
			else:
				s[i][j] = '<'
				s[x][y] = '>'
	for row in s:
		print(''.join(row))
main()


from collections import deque
from collections import defaultdict
import sys
sys.setrecursionlimit(10 ** 6)
INF = 10 ** 9 + 1
MOD = 10 ** 9 + 7
INF = 10 ** 10

def init():
	global edges
	edges = defaultdict(dict)

def add_edge(frm, to, capacity):
	edges[frm][to] = capacity
	edges[to][frm] = 0

def bfs(start, goal):
	global distance_from_start
	distance_from_start = [-1] * (MAX_VERTEX + 1)
	queue = deque()
	distance_from_start[start] = 0
	queue.append(start)
	while queue and distance_from_start[goal] == -1:
		frm = queue.popleft()
		for to in edges[frm]:
			if edges[frm][to] > 0 and distance_from_start[to] == -1:
				distance_from_start[to] = distance_from_start[frm] + 1
				queue.append(to)
	return distance_from_start[goal] != -1

def dfs(current, goal, flow):
	if current == goal:
		return flow
	i = itertion_count[current]
	while itertion_count[current] < len(edges[current]):
		to = edges_index[current][i]
		capacity = edges[current][to]
		if capacity > 0 and distance_from_start[current] < distance_from_start[to]:
			d = dfs(to, goal, min(flow, capacity))
			if d > 0:
				edges[current][to] -= d
				edges[to][current] += d
				return d
		itertion_count[current] += 1
		i += 1
	return 0

def max_flow(start, goal):
	global itertion_count, edges_index, original_edges, MAX_VERTEX
	from copy import deepcopy
	original_edges = deepcopy(edges)
	flow = 0
	edges_index = {frm: list(edges[frm]) for frm in edges}
	MAX_VERTEX = max(edges) if edges else goal
	while bfs(start, goal):
		itertion_count = [0] * (MAX_VERTEX + 1)
		f = dfs(start, goal, INF)
		while f > 0:
			flow += f
			f = dfs(start, goal, INF)
	return flow

def get_flow():
	result = []
	for v in original_edges:
		for u in original_edges[v]:
			if original_edges[v][u] > 0:
				d = original_edges[v][u] - edges[v][u]
				if d > 0:
					result.append((v, u, d))
	return result

def debug(*x):
	print(*x, file=sys.stderr)

def solve(SOLVE_PARAMS):
	pass

def readMap(H, W, S=1):
	global SENTINEL, HEIGHT, WIDTH
	SENTINEL = S
	HEIGHT = H + SENTINEL * 2
	WIDTH = W + SENTINEL * 2
	data = [0] * (HEIGHT * WIDTH)
	ok = ord('.')
	for i in range(H):
		S = input().strip()
		y = (i + SENTINEL) * WIDTH
		for j in range(W):
			data[y + (j + SENTINEL)] = 1 if S[j] == ok else 0
	return data

def main():
	init()
	(N, M) = map(int, input().split())
	data = readMap(N, M)
	odd = []
	even = []
	from collections import defaultdict
	tmp_edges = defaultdict(list)
	for i in range(len(data) - WIDTH):
		if not data[i]:
			continue
		(y, x) = divmod(i, WIDTH)
		if (x + y) % 2:
			odd.append(i)
			isEven = False
		else:
			even.append(i)
			isEven = True
		j = i + 1
		if data[j]:
			if isEven:
				tmp_edges[j].append(i)
			else:
				tmp_edges[i].append(j)
		j = i + WIDTH
		if data[j]:
			if isEven:
				tmp_edges[j].append(i)
			else:
				tmp_edges[i].append(j)
	START = 0
	GOAL = 1
	for v in odd:
		tmp_edges[START].append(v)
	for v in even:
		tmp_edges[v].append(GOAL)
	mapping = {}
	vs = odd + even + [START, GOAL]
	for (i, v) in enumerate(vs):
		mapping[v] = i
	for v in tmp_edges:
		for u in tmp_edges[v]:
			add_edge(v, u, 1)
	ret = max_flow(START, GOAL)
	print(ret)
	flow = get_flow()
	outmap = ['.' if x else '#' for x in data]
	for (v, u, _c) in flow:
		if v == START:
			continue
		if u == GOAL:
			continue
		if u < v:
			(u, v) = (v, u)
		if u - v == 1:
			outmap[u] = '<'
			outmap[v] = '>'
		if u - v == WIDTH:
			outmap[u] = '^'
			outmap[v] = 'v'
	for y in range(N):
		start = (y + 1) * WIDTH + SENTINEL
		end = start + M
		print(''.join(outmap[start:end]))
T1 = '\n3 3\n#..\n..#\n...\n'
TEST_T1 = '\n>>> as_input(T1)\n>>> main()\n3\n#><\n><#\n><.\n'
T2 = '\n10 10\n.#........\n#.#.......\n.#........\n..........\n..........\n..........\n......#...\n..........\n..........\n..........\n'
TEST_T2 = '\n>>> as_input(T2)\n>>> main()\n46\n.#><><><><\n#.#><><><v\nv#><><><v^\n^><><><v^v\n><><><v^v^\n><><><^v^v\n><><><#^v^\n><><><><^v\n><><><><v^\n><><><><^.\n'
T3 = '\n1 5\n.....\n'
TEST_T3 = '\n>>> as_input(T3)\n>>> main()\n2\n><><.\n'
T4 = '\n3 1\n.\n.\n.\n'
TEST_T4 = '\n>>> as_input(T4)\n>>> main()\n1\nv\n^\n.\n'
T5 = '\n3 1\n.\n#\n.\n'
TEST_T5 = '\n>>> as_input(T5)\n>>> main()\n0\n.\n#\n.\n'
T6 = '\n1 3\n###\n'
TEST_T6 = '\n>>> as_input(T6)\n>>> main()\nresult\n'

def _test():
	import doctest
	doctest.testmod()
	g = globals()
	for k in sorted(g):
		if k.startswith('TEST_'):
			doctest.run_docstring_examples(g[k], g, name=k)

def as_input(s):
	import io
	f = io.StringIO(s.strip())
	g = globals()
	g['input'] = lambda : bytes(f.readline(), 'ascii')
	g['read'] = lambda : bytes(f.read(), 'ascii')
input = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
if sys.argv[-1] == '-t':
	print('testing')
	_test()
	sys.exit()
main()