AtCoder Library Practice Contest - MinCostFlow

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). A nonnegative integer A_{i,j} is written for each square (i,j).

You choose some of the squares so that each row and column contains at most K chosen squares. Under this constraint, calculate the maximum value of the sum of the integers written on the chosen squares. Additionally, calculate a way to choose squares that acheives the maximum.

Constraints

* 1 \leq N \leq 50
* 1 \leq K \leq N
* 0 \leq A_{i,j} \leq 10^9
* All values in Input are integer.

Input

Input is given from Standard Input in the following format:


N K
A_{1,1} A_{1,2} \cdots A_{1,N}
A_{2,1} A_{2,2} \cdots A_{2,N}
\vdots
A_{N,1} A_{N,2} \cdots A_{N,N}


Output

On the first line, print the maximum value of the sum of the integers written on the chosen squares.

On the next N lines, print a way that achieves the maximum.

Precisely, output the strings t_1,t_2,\cdots,t_N, that satisfies t_{i,j}=`X` if you choose (i,j) and t_{i,j}=`.` otherwise.

You may print any way to choose squares that maximizes the sum.

Examples

Input

3 1
5 3 2
1 4 8
7 6 9


Output

19
X..
..X
.X.


Input

3 2
10 10 1
10 10 1
1 1 10


Output

50
XX.
XX.
..X

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
import heapq

class mcf_graph:

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

	def add_edge(self, frm, to, cap, cost):
		m = len(self.pos)
		e1 = self._edge(to, cap, cost)
		e2 = self._edge(frm, 0, -cost)
		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, cost):
			self.frm = frm
			self.to = to
			self.cap = cap
			self.flow = flow
			self.cost = cost

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

	def get_edge(self, i):
		e = self.pos[i]
		re = e.rev
		return self.edge(re.to, e.to, e.cap + re.cap, re.cap, e.cost)

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

	def flow(self, s, t, flow_limit=float('inf')):
		return self.slope(s, t, flow_limit)[-1]

	def slope(self, s, t, flow_limit=float('inf')):
		(pop, push) = (heapq.heappop, heapq.heappush)
		n = self._n
		g = self.g
		dual = [0] * n
		dist = [0] * n
		pv = [0] * n
		pe = [None] * n
		vis = [False] * n
		INF = float('inf')
		flow = 0
		cost = 0
		prev_cost = -1
		result = [(flow, cost)]
		while flow < flow_limit:
			for i in range(n):
				dist[i] = INF
				vis[i] = False
			dist[s] = 0
			que = [(0, s)]
			while que:
				(_, v) = pop(que)
				if vis[v]:
					continue
				vis[v] = True
				if v == t:
					break
				for e in g[v]:
					w = e.to
					if vis[w] or not e.cap:
						continue
					ndist = dist[v] + e.cost - dual[w] + dual[v]
					if ndist < dist[w]:
						dist[w] = ndist
						pv[w] = v
						pe[w] = e
						push(que, (dist[w], w))
			else:
				break
			for v in range(n):
				if not vis[v]:
					continue
				dual[v] -= dist[t] - dist[v]
			c = flow_limit - flow
			v = t
			while v != s:
				c = min(c, pe[v].cap)
				v = pv[v]
			v = t
			while v != s:
				e = pe[v]
				e.cap -= c
				e.rev.cap += c
				v = pv[v]
			d = -dual[s]
			flow += c
			cost += c * d
			if prev_cost == d:
				result[-1] = (flow, cost)
			else:
				result.append((flow, cost))
			prev_cost = cost
		return result

	class _edge:

		def __init__(self, to, cap, cost):
			self.to = to
			self.cap = cap
			self.cost = cost

	class _edge:

		def __init__(self, to, cap, cost):
			self.to = to
			self.cap = cap
			self.cost = cost
(n, k) = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]
mx = max((aij for ai in a for aij in ai))
s = n * n
t = s + 1
rs = t + 1
cs = rs + n
vcnt = cs + n
d = mcf_graph(vcnt)
for i in range(n):
	d.add_edge(s, rs + i, k, 0)
for i in range(n):
	for j in range(n):
		d.add_edge(rs + i, i * n + j, 1, mx - a[i][j])
for i in range(n):
	for j in range(n):
		d.add_edge(i * n + j, cs + j, 1, 0)
for j in range(n):
	d.add_edge(cs + j, t, k, 0)
d.add_edge(s, t, n * n, mx)
(_, res) = d.flow(s, t, n * n)
print(n * n * mx - res)
ans = [['.'] * n for _ in range(n)]
for (frm, to, cap, flow, cost) in d.edges():
	if frm < n * n and flow:
		(i, j) = (frm // n, frm % n)
		ans[i][j] = 'X'
for t in ans:
	print(''.join(t))


from heapq import heappop, heappush, heapify

class MinCostFlow:

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

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

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

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

	def dual_ref(self, s, t):
		dist = [2 ** 63 - 1] * self.n
		dist[s] = 0
		vis = [0] * self.n
		self.pv = [-1] * self.n
		self.pe = [-1] * self.n
		queue = []
		heappush(queue, (0, s))
		while queue:
			(k, v) = heappop(queue)
			if vis[v]:
				continue
			vis[v] = True
			if v == t:
				break
			for i in range(len(self.graph[v])):
				(to, rev, cap, cost) = self.graph[v][i]
				if vis[to] or cap == 0:
					continue
				cost += self.dual[v] - self.dual[to]
				if dist[to] - dist[v] > cost:
					dist[to] = dist[v] + cost
					self.pv[to] = v
					self.pe[to] = i
					heappush(queue, (dist[to], to))
		if not vis[t]:
			return False
		for v in range(self.n):
			if not vis[v]:
				continue
			self.dual[v] -= dist[t] - dist[v]
		return True

	def flow(self, s, t):
		return self.flow_with_limit(s, t, 2 ** 63 - 1)

	def flow_with_limit(self, s, t, limit):
		return self.slope_with_limit(s, t, limit)[-1]

	def slope(self, s, t):
		return self.slope_with_limit(s, t, 2 ** 63 - 1)

	def slope_with_limit(self, s, t, limit):
		flow = 0
		cost = 0
		prev_cost = -1
		res = [(flow, cost)]
		self.dual = [0] * self.n
		while flow < limit:
			if not self.dual_ref(s, t):
				break
			c = limit - flow
			v = t
			while v != s:
				c = min(c, self.graph[self.pv[v]][self.pe[v]][2])
				v = self.pv[v]
			v = t
			while v != s:
				(to, rev, cap, _) = self.graph[self.pv[v]][self.pe[v]]
				self.graph[self.pv[v]][self.pe[v]][2] -= c
				self.graph[v][rev][2] += c
				v = self.pv[v]
			d = -self.dual[s]
			flow += c
			cost += c * d
			if prev_cost == d:
				res.pop()
			res.append((flow, cost))
			prev_cost = cost
		return res
MAX = 10 ** 9
(N, K) = map(int, input().split())
A = [tuple(map(int, input().split())) for _ in range(N)]
mcf = MinCostFlow(2 * N + 2)
s = 2 * N
t = 2 * N + 1
mcf.add_edge(s, t, N * K, MAX)
for i in range(N):
	mcf.add_edge(s, i, K, 0)
	mcf.add_edge(i + N, t, K, 0)
	for j in range(N):
		mcf.add_edge(i, j + N, 1, MAX - A[i][j])
print(N * K * MAX - mcf.flow_with_limit(s, t, N * K)[1])
res = [['.' for j in range(N)] for i in range(N)]
for (fr, to, cap, flow, cost) in mcf.edges():
	if flow == 0 or fr == s or to == t:
		continue
	res[fr][to - N] = 'X'
for r in res:
	print(''.join(r))


import heapq

class PrimalDual:

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

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

	def min_cost_flow(self, s: int, t: int, f: int) -> int:
		res = 0
		potential = [0] * self.n
		prv_v = [0] * self.n
		prv_e = [None] * self.n
		while f > 0:
			dist = [self.INF] * self.n
			dist[s] = 0
			q = [(0, s)]
			while q:
				(cost, _from) = heapq.heappop(q)
				if dist[_from] < cost:
					continue
				for edge in self.graph[_from]:
					(to, capacity, cost, _) = edge
					p_diff = potential[_from] - potential[to]
					if capacity > 0 and dist[_from] + cost + p_diff < dist[to]:
						dist[to] = dist[_from] + cost + p_diff
						prv_v[to] = _from
						prv_e[to] = edge
						heapq.heappush(q, (dist[to], to))
			if dist[t] == self.INF:
				return -1
			for i in range(self.n):
				if dist[i] != self.INF:
					potential[i] += dist[i]
			d = f
			v = t
			while v != s:
				d = min(d, prv_e[v][1])
				v = prv_v[v]
			f -= d
			res += potential[t] * d
			v = t
			while v != s:
				edge = prv_e[v]
				edge[1] -= d
				edge[3][1] += d
				v = prv_v[v]
		return res
(n, k) = map(int, input().split())
a = [list(map(int, input().split())) for i in range(n)]
INF = 10 ** 18
pd = PrimalDual(n + n + 2)
s = n + n
t = n + n + 1
pd.add_edge(s, t, INF, 0)
for i in range(n):
	pd.add_edge(s, n + i, k, 0)
	pd.add_edge(i, t, k, 0)
for i in range(n):
	for j in range(n):
		pd.add_edge(n + i, j, 1, -a[i][j])
ans = -pd.min_cost_flow(s, t, INF)
res = [['.' for i in range(n)] for i in range(n)]
for i in range(n):
	for (j, cap, cost, _) in pd.graph[n + i]:
		if 0 <= j <= n and cap == 0:
			res[i][j] = 'X'
print(ans)
for r in res:
	print(''.join(r))


import heapq

class mcf_graph_int_cost:

	def __init__(self, n):
		self.n = n
		self.log = n.bit_length()
		self.mask = (1 << self.log) - 1
		self.pos = []
		self.g = [[] for _ in range(n)]

	def add_edge(self, from_, to, cap, cost):
		assert 0 <= from_ < self.n
		assert 0 <= to < self.n
		m = len(self.pos)
		self.pos.append((from_, len(self.g[from_])))
		self.g[from_].append(self.__class__._edge(to, len(self.g[to]), cap, cost))
		self.g[to].append(self.__class__._edge(from_, len(self.g[from_]) - 1, 0, -cost))
		return m

	class edge:

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

	def get_edge(self, i):
		_e = self.g[self.pos[i][0]][self.pos[i][1]]
		_re = self.g[_e.to][_e.rev]
		return self.__class__.edge(self.pos[i][0], _e.to, _e.cap + _re.cap, _re.cap, _e.cost)

	def edges(self):
		ret = []
		for i in range(len(self.pos)):
			_e = self.g[self.pos[i][0]][self.pos[i][1]]
			_re = self.g[_e.to][_e.rev]
			ret.append(self.__class__.edge(self.pos[i][0], _e.to, _e.cap + _re.cap, _re.cap, _e.cost))
		return ret

	def slope(self, s, t, flow_limit=float('inf')):
		dual = [0] * self.n
		dist = [float('inf')] * self.n
		pv = [-1] * self.n
		pe = [-1] * self.n
		vis = [False] * self.n

		def _dual_ref():
			nonlocal dual, dist, pv, pe, vis
			dist = [float('inf')] * self.n
			pv = [-1] * self.n
			pe = [-1] * self.n
			vis = [False] * self.n
			que = [s]
			dist[s] = 0
			while que:
				v = heapq.heappop(que) & self.mask
				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 e.cap == 0:
						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
						heapq.heappush(que, (dist[e.to] << self.log) + 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 = [(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

	def flow(self, s, t, flow_limit=float('inf')):
		return self.slope(s, t, flow_limit)[-1]

	class _edge:

		def __init__(self, to, rev, cap, cost):
			self.to = to
			self.rev = rev
			self.cap = cap
			self.cost = cost
BIG = 10 ** 9
import sys
input = sys.stdin.readline
(N, K) = map(int, input().split())
g = mcf_graph_int_cost(2 * N + 2)
s = 2 * N
t = 2 * N + 1
g.add_edge(s, t, N * K, BIG)
for i in range(N):
	g.add_edge(s, i, K, 0)
	g.add_edge(N + i, t, K, 0)
for i in range(N):
	As = map(int, input().split())
	for (j, A) in enumerate(As):
		g.add_edge(i, N + j, 1, BIG - A)
result = g.flow(s, t, N * K)
print(N * K * BIG - result[1])
grid = [['.' for _ in range(N)] for _ in range(N)]
edges = g.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'
for row in grid:
	print(''.join(row))


from heapq import heappush, heappop

class MinCostFlow_by_Dijkstra:
	INF = float('inf')

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

	def add_edge(self, fr, to, cap, cost):
		forward = [to, cap, cost, None]
		backward = forward[3] = [fr, 0, -cost, forward]
		self.G[fr].append(forward)
		self.G[to].append(backward)
		self.E.add((fr, to))

	def flow(self, s, t, f, Mode=False):
		N = self.N
		G = self.G
		INF = MinCostFlow_by_Dijkstra.INF
		res = 0
		H = [0] * N
		prv_v = [0] * N
		prv_e = [None] * N
		d0 = [INF] * N
		dist = [INF] * N
		while f:
			dist[:] = d0
			dist[s] = 0
			que = [(0, s)]
			while que:
				(c, v) = heappop(que)
				if dist[v] < c:
					continue
				r0 = dist[v] + H[v]
				for e in G[v]:
					(w, cap, cost, _) = e
					if cap > 0 and r0 + cost - H[w] < dist[w]:
						dist[w] = r = r0 + cost - H[w]
						prv_v[w] = v
						prv_e[w] = e
						heappush(que, (r, w))
			if dist[t] == INF:
				return None
			for i in range(N):
				H[i] += dist[i]
			d = f
			v = t
			while v != s:
				d = min(d, prv_e[v][1])
				v = prv_v[v]
			f -= d
			res += d * H[t]
			v = t
			while v != s:
				e = prv_e[v]
				e[1] -= d
				e[3][1] += d
				v = prv_v[v]
		if Mode:
			R = {}
			for v in range(self.N):
				R[v] = {}
				for S in self.G[v]:
					w = S[0]
					if (v, w) in self.E:
						R[v][w] = S[-1][1]
			return (res, R)
		else:
			return res
(N, K) = map(int, input().split())
A = [[0] * N for _ in range(N)]
for i in range(N):
	A[i] = list(map(int, input().split()))
inf = float('inf')
huge = 10 ** 18
D = MinCostFlow_by_Dijkstra(2 * N + 2)
s = 2 * N
t = 2 * N + 1
for i in range(N):
	D.add_edge(s, i, K, 0)
	D.add_edge(N + i, t, K, 0)
D.add_edge(s, t, N * K, huge)
for i in range(N):
	for j in range(N):
		D.add_edge(i, N + j, 1, huge - A[i][j])
(p, R) = D.flow(s, t, N * K, True)
p = huge * N * K - p
S = [['.'] * N for _ in range(N)]
for i in range(N):
	for j in range(N):
		if R[i][N + j] == 1:
			S[i][j] = 'X'
T = [''.join(a) for a in S]
print(p)
print('\n'.join(T))


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))

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')
from heapq import heappop, heappush

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_E()


import heapq
NUMERIC_LIMITS = 10 ** 18

class mcf_graph:
	pos = []

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

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

	class edge:

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

	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, _e.cost)

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

	def flow(self, s, t, flow_limit=NUMERIC_LIMITS):
		return self.slope(s, t, flow_limit)[-1]

	def slope(self, s, t, flow_limit=NUMERIC_LIMITS):
		push = heapq.heappush
		pop = heapq.heappop
		(dual, dist) = ([0] * self._n, [0] * self._n)
		(pv, pe) = ([0] * self._n, [0] * self._n)
		vis = [False] * self._n

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

			class Q:

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

				def __lt__(s, r):
					return s.key < r.key
			que = []
			dist[s] = 0
			push(que, Q(0, s))
			while len(que):
				v = pop(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
						push(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, prev_cost) = (0, -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, rev, cap, cost):
			(s.to, s.rev) = (to, rev)
			(s.cap, s.cost) = (cap, cost)

def main():
	(N, K) = list(map(int, input().split()))
	A = [list(map(int, input().split())) for _ in range(N)]
	BIG = 10 ** 9
	g = mcf_graph(2 * N + 2)
	s = 2 * N
	t = 2 * N + 1
	g.add_edge(s, t, N * K, BIG)
	for i in range(N):
		g.add_edge(s, i, K, 0)
		g.add_edge(N + i, t, K, 0)
	for i in range(N):
		for j in range(N):
			g.add_edge(i, N + j, 1, BIG - A[i][j])
	result = g.flow(s, t, N * K)
	print(N * K * BIG - result[1])
	grid = [['.'] * N for _ in range(N)]
	edges = g.edges()
	for e in edges:
		if e.frm == s or e.to == t or e.flow == 0:
			continue
		grid[e.frm][e.to - N] = 'X'
	for g in grid:
		print(''.join(g))
main()


import sys
sys.setrecursionlimit(10 ** 7)

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

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

class MinCostFlow:

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

	def addEdge(self, f, t, cap, cost):
		self.G[f].append([t, cap, cost, len(self.G[t])])
		self.G[t].append([f, 0, -cost, len(self.G[f]) - 1])

	def minCostFlow(self, s, t, f):
		n = self.n
		G = self.G
		prevv = [0] * n
		preve = [0] * n
		INF = 10 ** 18
		res = 0
		while f:
			dist = [INF] * n
			dist[s] = 0
			update = 1
			while update:
				update = 0
				for v in range(n):
					if dist[v] == INF:
						continue
					gv = G[v]
					for i in range(len(gv)):
						(to, cap, cost, rev) = gv[i]
						if cap > 0 and dist[v] + cost < dist[to]:
							dist[to] = dist[v] + cost
							prevv[to] = v
							preve[to] = i
							update = 1
			if dist[t] == INF:
				return -1
			d = f
			v = t
			while v != s:
				d = min(d, G[prevv[v]][preve[v]][1])
				v = prevv[v]
			f -= d
			res += d * dist[t]
			v = t
			while v != s:
				e = G[prevv[v]][preve[v]]
				e[1] -= d
				G[v][e[3]][1] += d
				v = prevv[v]
		return res
(N, K) = MI()
A = [LI() for _ in range(N)]
max = 10 ** 13
MCF = MinCostFlow(2 * N + 2)
(s, t) = (2 * N, 2 * N + 1)
MCF.addEdge(s, t, N * K, max)
for i in range(N):
	MCF.addEdge(s, i, K, 0)
	MCF.addEdge(i + N, t, K, 0)
	for j in range(N):
		MCF.addEdge(i, j + N, 1, max - A[i][j])
print(N * K * max - MCF.minCostFlow(s, t, N * K))
ANS = [['.'] * N for _ in range(N)]
for i in range(N):
	for (to, cap, cost, _) in MCF.G[i]:
		if cap == 0 and N <= to < 2 * N:
			ANS[i][to - N] = 'X'
for i in range(N):
	print(''.join(ANS[i]))


from heapq import heappush, heappop

class MinCostFlow:
	INF = 10 ** 18

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

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

	def flow(self, s, t, f):
		N = self.N
		G = self.G
		INF = MinCostFlow.INF
		res = 0
		H = [0] * N
		prv_v = [0] * N
		prv_e = [None] * N
		d0 = [INF] * N
		dist = [INF] * N
		while f:
			dist[:] = d0
			dist[s] = 0
			que = [(0, s)]
			while que:
				(c, v) = heappop(que)
				if dist[v] < c:
					continue
				r0 = dist[v] + H[v]
				for e in G[v]:
					(w, cap, cost, _) = e
					if cap > 0 and r0 + cost - H[w] < dist[w]:
						dist[w] = r = r0 + cost - H[w]
						prv_v[w] = v
						prv_e[w] = e
						heappush(que, (r, w))
			if dist[t] == INF:
				return None
			for i in range(N):
				H[i] += dist[i]
			d = f
			v = t
			while v != s:
				d = min(d, prv_e[v][1])
				v = prv_v[v]
			f -= d
			res += d * H[t]
			v = t
			while v != s:
				e = prv_e[v]
				e[1] -= d
				e[3][1] += d
				v = prv_v[v]
		return res
from sys import stdin
input = stdin.buffer.readline

def main():
	(n, k) = map(int, input().split())
	a = [list(map(int, input().split())) for _ in range(n)]
	mcf = MinCostFlow(n * (n + 2) + 2)
	source = n * (n + 2)
	sink = n * (n + 2) + 1
	mcf.add_edge(source, sink, n * k, 0)
	for i in range(n):
		mcf.add_edge(source, n * n + i, k, 0)
		mcf.add_edge(n * (n + 1) + i, sink, k, 0)
		for j in range(n):
			mcf.add_edge(n * n + i, n * i + j, 1, -a[i][j])
			mcf.add_edge(n * i + j, n * (n + 1) + j, 1, 0)
	print(-mcf.flow(source, sink, n * k))
	ans = [['.'] * n for _ in range(n)]
	for i in range(n):
		for j in range(n):
			if mcf.G[n * i + j][0][1]:
				ans[i][j] = 'X'
	for row in ans:
		print(''.join(row))
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 ** 18
MOD = 10 ** 9 + 7
EPS = 10 ** (-10)

class MinCostFlow:
	INF = 10 ** 18

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

	def copy(self):
		res = MinCostFlow(self.N)
		res.G = [[a[:] for a in b] for b in self.G]
		res.pos = [a[:] for a in self.pos]
		return res

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

	def flow(self, s, t, f):
		from heapq import heappush, heappop
		N = self.N
		G = self.G
		INF = MinCostFlow.INF
		res = 0
		H = [0] * N
		prv_v = [0] * N
		prv_e = [0] * N
		while f:
			dist = [INF] * N
			dist[s] = 0
			que = [(0, s)]
			while que:
				(c, v) = heappop(que)
				if dist[v] < c:
					continue
				for (i, (to, cap, cost, _)) in enumerate(G[v]):
					if cap > 0 and dist[to] > dist[v] + cost + H[v] - H[to]:
						dist[to] = r = dist[v] + cost + H[v] - H[to]
						prv_v[to] = v
						prv_e[to] = i
						heappush(que, (r, to))
			if dist[t] == INF:
				return INF
			for i in range(N):
				H[i] += dist[i]
			d = f
			v = t
			while v != s:
				d = min(d, G[prv_v[v]][prv_e[v]][1])
				v = prv_v[v]
			f -= d
			res += d * H[t]
			v = t
			while v != s:
				e = G[prv_v[v]][prv_e[v]]
				e[1] -= d
				G[v][e[3]][1] += d
				v = prv_v[v]
		return res

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

	def get_edges(self):
		M = len(self.pos)
		res = []
		for i in range(M):
			res.append(self.get_edge(i))
		return res
(N, K) = MAP()
grid = [[] for i in range(N)]
for i in range(N):
	grid[i] = LIST()
offset = 10 ** 12
mcf = MinCostFlow(N * 2 + 2)
s = N * 2
t = N * 2 + 1
mcf.add_edge(s, t, N * N, offset)
for i in range(N):
	mcf.add_edge(s, i, K, 0)
	mcf.add_edge(N + i, t, K, 0)
	for j in range(N):
		mcf.add_edge(i, N + j, 1, offset - grid[i][j])
mn = mcf.flow(s, t, N * N)
mn -= offset * N * N
ans = [['.' for j in range(N)] for i in range(N)]
edges = mcf.get_edges()
for (fr, to, cap, f, c) in edges:
	if fr != s and to != t and f:
		h = fr
		w = to - N
		ans[h][w] = 'X'
print(-mn)
for i in range(N):
	print(''.join(ans[i]))


(N, K) = map(int, input().split())
MAP = [list(map(int, input().split())) for i in range(N)]
start = 2 * N + 1
goal = 2 * N + 2
V = 2 * N + 5
EDGE = [[[0, 0] for j in range(V)] for i in range(V)]
for i in range(N):
	EDGE[start][i] = [K, 0]
	EDGE[N + i][goal] = [K, 0]
for i in range(N):
	for j in range(N):
		EDGE[i][N + j] = [1, -MAP[i][j]]
		EDGE[N + j][i] = [0, MAP[i][j]]
EDGE[start][goal] = [float('inf'), 0]
BACK = [-1] * V
LA = 0
for flow in range(K * N):
	ANS = [float('inf')] * V
	ANS[start] = 0
	for rep in range(V):
		flag = 0
		for fr in range(V):
			for to in range(V):
				(c, d) = EDGE[fr][to]
				if c > 0 and ANS[to] > ANS[fr] + d:
					ANS[to] = ANS[fr] + d
					flag = 1
					BACK[to] = fr
		if flag == 0:
			break
	if ANS[goal] == 0:
		break
	LA += ANS[goal]
	NOW = goal
	while NOW != start:
		fr = BACK[NOW]
		EDGE[fr][NOW][0] -= 1
		EDGE[NOW][fr][0] += 1
		NOW = fr
print(-LA)
ALIST = [['.'] * N for i in range(N)]
for i in range(N):
	for j in range(N):
		if EDGE[i][N + j][0] == 0:
			ALIST[i][j] = 'X'
for alist in ALIST:
	print(''.join(alist))


from heapq import heappush, heappop

class MinCostFlow:
	INF = 10 ** 18

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

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

	def flow(self, s, t, f):
		N = self.N
		G = self.G
		INF = MinCostFlow.INF
		res = 0
		H = [0] * N
		prv_v = [0] * N
		prv_e = [None] * N
		d0 = [INF] * N
		dist = [INF] * N
		while f:
			dist[:] = d0
			dist[s] = 0
			que = [(0, s)]
			while que:
				(c, v) = heappop(que)
				if dist[v] < c:
					continue
				r0 = dist[v] + H[v]
				for e in G[v]:
					(w, cap, cost, _) = e
					if cap > 0 and r0 + cost - H[w] < dist[w]:
						dist[w] = r = r0 + cost - H[w]
						prv_v[w] = v
						prv_e[w] = e
						heappush(que, (r, w))
			if dist[t] == INF:
				return None
			for i in range(N):
				H[i] += dist[i]
			d = f
			v = t
			while v != s:
				d = min(d, prv_e[v][1])
				v = prv_v[v]
			f -= d
			res += d * H[t]
			v = t
			while v != s:
				e = prv_e[v]
				e[1] -= d
				e[3][1] += d
				v = prv_v[v]
		return res
(N, K) = map(int, input().split())
A = [list(map(int, input().split())) for i in range(N)]
G = MinCostFlow(2 * N + 3)
G.add_edge(0, 2 * N + 2, 10 ** 18, 0)
G.add_edge(2 * N + 2, 2 * N + 1, 10 ** 18, 0)
for i in range(N):
	G.add_edge(0, i + 1, K, 0)
	for j in range(N):
		G.add_edge(i + 1, N + 1 + j, 1, -A[i][j])
for j in range(N):
	G.add_edge(N + 1 + j, 2 * N + 1, K, 0)
f = G.flow(0, 2 * N + 1, N ** 2)
print(-f)
res = [['.' for j in range(N)] for i in range(N)]
for i in range(N):
	for (w, cap, _, _) in G.G[i + 1]:
		if N + 1 <= w <= 2 * N:
			j = w - (N + 1)
			if cap == 0:
				res[i][j] = 'X'
for i in range(N):
	print(''.join(res[i]))


(N, K) = map(int, input().split())
A = [list(map(int, input().split())) for i in range(N)]
V = 2 * N + 2
INF = 10 ** 14
G = [[] for i in range(V)]
D = [INF] * V
(PV, PE) = ([0] * V, [0] * V)

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

def mcf(s, t, f):
	global G, V, INF, D, PV, PE
	for i in range(V):
		for j in range(len(G[i])):
			G[i][j][4] = 0
	r = 0
	z = f
	while z > 0:
		D = [INF] * V
		D[s] = 0
		ud = True
		while ud:
			ud = False
			for x in range(V):
				if D[x] == INF:
					continue
				for i in range(len(G[x])):
					if G[x][i][1] > 0 and D[G[x][i][0]] > D[x] + G[x][i][2]:
						D[G[x][i][0]] = D[x] + G[x][i][2]
						PV[G[x][i][0]] = x
						PE[G[x][i][0]] = i
						ud = True
		if D[t] == INF:
			return -INF
		d = z
		x = t
		while x != s:
			d = min(d, G[PV[x]][PE[x]][1])
			x = PV[x]
		z -= d
		r += d * D[t]
		x = t
		while x != s:
			G[PV[x]][PE[x]][1] -= d
			G[PV[x]][PE[x]][4] += d
			G[x][G[PV[x]][PE[x]][3]][1] += d
			G[x][G[PV[x]][PE[x]][3]][4] -= d
			x = PV[x]
	return r
s = N * 2
t = s + 1
for i in range(N):
	ae(s, i, K, 0)
	ae(N + i, t, K, 0)
	for j in range(N):
		ae(i, N + j, 1, 10 ** 10 - A[i][j])
ae(s, t, N * K, 10 ** 10)
print(N * K * 10 ** 10 - mcf(s, t, N * K))
P = [['.'] * N for i in range(N)]
for i in range(N):
	for j in range(len(G[i])):
		if G[i][j][4] > 0:
			P[i][G[i][j][0] - N] = 'X'
	print(''.join(P[i]))


from heapq import heappop, heappush, heapify
import sys
sys.setrecursionlimit(10 ** 6)
INF = 10 ** 9 + 1
MOD = 10 ** 9 + 7

class MinCostFlow:

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

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

	def get_edge(self, idx):
		(to, rev, cap, cost) = self.graph[self.pos[idx][0]][self.pos[idx][1]]
		(_rev_to, _rev_rev, rev_cap, _rev_cost) = self.graph[to][rev]
		return (self.pos[idx][0], to, cap + rev_cap, rev_cap, cost)

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

	def dual_ref(self, s, t):
		dist = [2 ** 63 - 1] * self.n
		dist[s] = 0
		vis = [0] * self.n
		self.pv = [-1] * self.n
		self.pe = [-1] * self.n
		queue = []
		heappush(queue, (0, s))
		while queue:
			(k, v) = heappop(queue)
			if vis[v]:
				continue
			vis[v] = True
			if v == t:
				break
			for i in range(len(self.graph[v])):
				(to, _rev, cap, cost) = self.graph[v][i]
				if vis[to] or cap == 0:
					continue
				cost += self.dual[v] - self.dual[to]
				if dist[to] - dist[v] > cost:
					dist[to] = dist[v] + cost
					self.pv[to] = v
					self.pe[to] = i
					heappush(queue, (dist[to], to))
		if not vis[t]:
			return False
		for v in range(self.n):
			if not vis[v]:
				continue
			self.dual[v] -= dist[t] - dist[v]
		return True

	def flow(self, s, t):
		return self.flow_with_limit(s, t, 2 ** 63 - 1)

	def flow_with_limit(self, s, t, limit):
		return self.slope_with_limit(s, t, limit)[-1]

	def slope(self, s, t):
		return self.slope_with_limit(s, t, 2 ** 63 - 1)

	def slope_with_limit(self, s, t, limit):
		flow = 0
		cost = 0
		prev_cost = -1
		res = [(flow, cost)]
		self.dual = [0] * self.n
		while flow < limit:
			if not self.dual_ref(s, t):
				break
			c = limit - flow
			v = t
			while v != s:
				c = min(c, self.graph[self.pv[v]][self.pe[v]][2])
				v = self.pv[v]
			v = t
			while v != s:
				(_to, rev, _cap, _) = self.graph[self.pv[v]][self.pe[v]]
				self.graph[self.pv[v]][self.pe[v]][2] -= c
				self.graph[v][rev][2] += c
				v = self.pv[v]
			d = -self.dual[s]
			flow += c
			cost += c * d
			if prev_cost == d:
				res.pop()
			res.append((flow, cost))
			prev_cost = cost
		return res

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

def solve(N, data, K):
	mcf = MinCostFlow(2 * N + 2)
	start = 2 * N
	goal = 2 * N + 1
	mcf.add_edge(start, goal, N * K, INF)
	for i in range(N):
		mcf.add_edge(start, i, K, 0)
		mcf.add_edge(i + N, goal, K, 0)
		for j in range(N):
			mcf.add_edge(i, j + N, 1, INF - data[i][j])
	print(N * K * INF - mcf.flow_with_limit(start, goal, N * K)[1])
	ret = [['.' for j in range(N)] for i in range(N)]
	for (frm, to, _cap, flow, _cost) in mcf.edges():
		if flow == 0 or frm == start or to == goal:
			continue
		ret[frm][to - N] = 'X'
	for r in ret:
		print(''.join(r))

def main():
	(N, K) = map(int, input().split())
	data = []
	for _i in range(N):
		data.append(list(map(int, input().split())))
	solve(N, data, K)
T1 = '\n3 1\n5 3 2\n1 4 8\n7 6 9\n'
TEST_T1 = '\n>>> as_input(T1)\n>>> main()\n19\nX..\n..X\n.X.\n'
T2 = '\n3 2\n10 10 1\n10 10 1\n1 1 10\n'
TEST_T2 = '\n>>> as_input(T2)\n>>> main()\n50\nXX.\nXX.\n..X\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()


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 Edge:

	def __init__(self, t, f, r, ca, co):
		self.to = t
		self.fron = f
		self.rev = r
		self.cap = ca
		self.cost = co

class MinCostFlow:
	size = 0
	graph = []

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

	def add_edge(self, f, t, ca, co):
		self.graph[f].append(Edge(t, f, len(self.graph[t]), ca, co))
		self.graph[t].append(Edge(f, t, len(self.graph[f]) - 1, 0, -co))

	def min_path(self, s, t):
		dist = [inf] * self.size
		route = [None] * self.size
		que = collections.deque()
		inq = [False] * self.size
		dist[s] = 0
		que.append(s)
		inq[s] = True
		while que:
			u = que.popleft()
			inq[u] = False
			for e in self.graph[u]:
				if e.cap == 0:
					continue
				v = e.to
				if dist[v] > dist[u] + e.cost:
					dist[v] = dist[u] + e.cost
					route[v] = e
					if not inq[v]:
						que.append(v)
						inq[v] = True
		if dist[t] == inf:
			return (inf, 0)
		if dist[t] > 0:
			return (dist[t], -1)
		flow = inf
		v = t
		while v != s:
			e = route[v]
			if flow > e.cap:
				flow = e.cap
			v = e.fron
		c = 0
		v = t
		while v != s:
			e = route[v]
			e.cap -= flow
			self.graph[e.to][e.rev].cap += flow
			c += e.cost * flow
			v = e.fron
		return (dist[t], flow)

	def calc_min_cost_flow(self, s, t, flow):
		total_cost = 0
		while flow > 0:
			(c, f) = self.min_path(s, t)
			if f == 0:
				return inf
			if f < 0:
				return total_cost
			f = min(flow, f)
			total_cost += c * f
			flow -= f
		return total_cost

def main():
	(n, k) = LI()
	aa = [LI() for _ in range(n)]
	ri = [n * n + i for i in range(n)]
	ci = [n * n + n + i for i in range(n)]
	s = n * n + n * 2
	t = n * n + n * 2 + 1
	mcf = MinCostFlow(n * n + n * 2 + 2)
	for i in range(n):
		mcf.add_edge(s, ri[i], k, 0)
		mcf.add_edge(ci[i], t, k, 0)
	for r in range(n):
		for c in range(n):
			rc = r * n + c
			mcf.add_edge(ri[r], rc, 1, -aa[r][c])
			mcf.add_edge(rc, ci[c], 1, 0)
	res = -mcf.calc_min_cost_flow(s, t, n * k)
	ra = [['.'] * n for _ in range(n)]
	for r in range(n):
		for c in range(n):
			rc = r * n + c
			for gr in mcf.graph[rc]:
				if gr.to == ci[c] and gr.cap == 0:
					ra[r][c] = 'X'
	return f'{res}\n' + JAA(ra, '\n', '')
print(main())


from heapq import heappop, heappush

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
import sys
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():
	(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')
Main()


import sys
readline = sys.stdin.readline
from heapq import heappop as hpp, heappush as hp

class MinCostFlowwithDijkstra:
	INF = 1 << 60

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

	def add_edge(self, st, en, cap, cost):
		self.Edge[st].append([en, cap, cost, len(self.Edge[en])])
		self.Edge[en].append([st, 0, -cost, len(self.Edge[st]) - 1])

	def get_mf(self, so, si, fl):
		N = self.N
		INF = self.INF
		res = 0
		Pot = [0] * N
		geta = N
		prv = [None] * N
		prenum = [None] * N
		while fl:
			dist = [INF] * N
			dist[so] = 0
			Q = [so]
			while Q:
				(cost, vn) = divmod(hpp(Q), geta)
				if dist[vn] < cost:
					continue
				for enum in range(len(self.Edge[vn])):
					(vf, cap, cost, _) = self.Edge[vn][enum]
					cc = dist[vn] + cost - Pot[vn] + Pot[vf]
					if cap > 0 and dist[vf] > cc:
						dist[vf] = cc
						prv[vf] = vn
						prenum[vf] = enum
						hp(Q, cc * geta + vf)
			if dist[si] == INF:
				return -1
			for i in range(N):
				Pot[i] -= dist[i]
			cfl = fl
			vf = si
			while vf != so:
				cfl = min(cfl, self.Edge[prv[vf]][prenum[vf]][1])
				vf = prv[vf]
			fl -= cfl
			res -= cfl * Pot[si]
			vf = si
			while vf != so:
				e = self.Edge[prv[vf]][prenum[vf]]
				e[1] -= cfl
				self.Edge[vf][e[3]][1] += cfl
				vf = prv[vf]
		return res
(N, K) = map(int, readline().split())
MAX = 10 ** 9 + 7
A = [list(map(int, readline().split())) for _ in range(N)]
T = MinCostFlowwithDijkstra(2 * N + 2)
st = 2 * N
en = st + 1
T.add_edge(st, en, MAX, MAX)
for i in range(N):
	T.add_edge(st, i, K, 0)
	T.add_edge(N + i, en, K, 0)
for i in range(N):
	for j in range(N):
		T.add_edge(i, N + j, 1, MAX - A[i][j])
ff = N // K * K * K + (N % K) ** 2
print(MAX * MAX - T.get_mf(st, en, MAX))
dot = ord('.')
cross = ord('X')
Ans = [[dot] * N for _ in range(N)]
cnt = 0
for j in range(N):
	for (vf, cap, _, _) in T.Edge[N + j]:
		if cap == 1 and vf != en:
			Ans[vf][j] = cross
print('\n'.join((''.join(map(chr, a)) for a in Ans)))


(N, K) = map(int, input().split())
A = [list(map(int, input().split())) for i in range(N)]
import heapq

class MinCostFlow:

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

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

	def get_edges(self):
		ret = []
		for (fr, i) in self.pos:
			(to, rev, cap, cost) = self.es[fr][i]
			flow = self.es[to][rev][2]
			cap += flow
			ret.append((fr, to, cap, flow, cost))
		return ret

	def flow(self, s, t, flow_limit=2 ** 63):
		return self.slope(s, t, flow_limit)[-1]

	def slope(self, s, t, flow_limit=2 ** 63):
		self.dual = [0] * self.n
		self.dist = [2 ** 63] * self.n
		self.pv = [-1] * self.n
		self.pe = [-1] * self.n
		self.vis = [False] * self.n

		def _dual_ref():
			self.dist = [2 ** 63] * self.n
			self.pv = [-1] * self.n
			self.pe = [-1] * self.n
			self.vis = [False] * self.n
			hq = [(0, s)]
			self.dist[s] = 0
			while hq:
				p = heapq.heappop(hq)
				v = p[1]
				if self.vis[v]:
					continue
				self.vis[v] = True
				if v == t:
					break
				for (i, (to, rev, cap, cost)) in enumerate(self.es[v]):
					if self.vis[to] or not cap:
						continue
					_cost = cost - self.dual[to] + self.dual[v]
					if self.dist[to] - self.dist[v] > _cost:
						self.dist[to] = self.dist[v] + _cost
						self.pv[to] = v
						self.pe[to] = i
						heapq.heappush(hq, (self.dist[to], to))
			if not self.vis[t]:
				return False
			for v in range(self.n):
				if not self.vis[v]:
					continue
				self.dual[v] -= self.dist[t] - self.dist[v]
			return True
		(flow, cost, prev_cost) = (0, 0, -1)
		ret = [(flow, cost)]
		while flow < flow_limit:
			if not _dual_ref():
				break
			c = flow_limit - flow
			v = t
			while v != s:
				c = min(c, self.es[self.pv[v]][self.pe[v]][2])
				v = self.pv[v]
			v = t
			while v != s:
				self.es[self.pv[v]][self.pe[v]][2] -= c
				self.es[v][self.es[self.pv[v]][self.pe[v]][1]][2] += c
				v = self.pv[v]
			d = -self.dual[s]
			flow += c
			cost += c * d
			if prev_cost == d:
				ret.pop()
			ret.append((flow, cost))
			prev_cost = cost
		return ret
mcf = MinCostFlow(2 * N + 2)
(src, dst) = (2 * N, 2 * N + 1)
BIG = 10 ** 9
mcf.add_edge(src, dst, N * K, BIG)
for i in range(N):
	mcf.add_edge(src, i, K, 0)
	mcf.add_edge(N + i, dst, K, 0)
for (i, row) in enumerate(A):
	for (j, a) in enumerate(row):
		mcf.add_edge(i, N + j, 1, BIG - a)
(_, mincost) = mcf.flow(src, dst, N * K)
ans = [['.'] * N for _ in range(N)]
print(N * K * BIG - mincost)
for (fr, to, cap, flow, cost) in mcf.get_edges():
	if fr == src or to == dst or flow == 0:
		continue
	ans[fr][to - N] = 'X'
for row in ans:
	print(''.join(row))


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

def main():
	import sys
	input = sys.stdin.readline
	from heapq import heappush, heappop

	class Mincostflow:

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

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

		def flow(self, s, t, f):
			N = self.N
			adj = self.adj
			inf = self.inf
			res = 0
			H = [0] * (N + 1)
			prev_v = [0] * (N + 1)
			prev_e = [None] * (N + 1)
			dist0 = [inf] * (N + 1)
			dist = [inf] * (N + 1)
			while f:
				dist[:] = dist0
				dist[s] = 0
				pq = [(0, s)]
				while pq:
					(d, v) = heappop(pq)
					if d > dist[v]:
						continue
					r0 = dist[v] + H[v]
					for e in adj[v]:
						(u, cap, cost, _) = e
						if cap > 0 and r0 + cost - H[u] < dist[u]:
							dist[u] = r = r0 + cost - H[u]
							heappush(pq, (r, u))
							prev_v[u] = v
							prev_e[u] = e
				if dist[t] == inf:
					return None
				for i in range(1, N + 1):
					H[i] += dist[i]
				g = f
				v = t
				while v != s:
					g = min(g, prev_e[v][1])
					v = prev_v[v]
				f -= g
				res += g * H[t]
				v = t
				while v != s:
					e = prev_e[v]
					e[1] -= g
					e[-1][1] += g
					v = prev_v[v]
			return res
	(N, K) = map(int, input().split())
	grid = []
	for _ in range(N):
		grid.append(list(map(int, input().split())))
	s = 2 * N + 1
	t = 2 * N + 2
	mcf = Mincostflow(N * 2 + 2)
	mcf.add_edge(s, t, N * K, val_max)
	for i in range(1, N + 1):
		mcf.add_edge(s, i, K, 0)
		mcf.add_edge(i + N, t, K, 0)
	for i in range(1, N + 1):
		for j in range(N + 1, 2 * N + 1):
			mcf.add_edge(i, j, 1, val_max - grid[i - 1][j - 1 - N])
	print(val_max * N * K - mcf.flow(s, t, N * K))
	ans = [['.'] * N for _ in range(N)]
	for i in range(1, N + 1):
		for (j, cap, cost, _) in mcf.adj[i]:
			if cap == 0:
				ans[i - 1][j - 1 - N] = 'X'
	for i in range(N):
		print(''.join(ans[i]))
main()


import heapq

class MCF_graph(object):

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

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

	def __get_edge(self, i):
		(e_to, e_rev, e_cap, e_cost) = 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, e_cost)

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

	def flow(self, s, t, flow_limit=10 ** 18):
		return self.slope(s, t, flow_limit)[-1]

	def slope(self, s, t, flow_limit=10 ** 18):
		dual = [0] * self.n
		flow = 0
		cost = 0
		prev_cost = -1
		result = [(0, 0)]
		while flow < flow_limit:
			dist = [10 ** 18] * self.n
			pv = [-1] * self.n
			pe = [-1] * self.n
			vis = [False] * self.n
			dist[s] = 0
			que = [(0, s)]
			while que:
				(_, v) = heapq.heappop(que)
				if vis[v]:
					continue
				vis[v] = True
				if v == t:
					break
				for (i, (e_to, _, e_cap, e_cost)) in enumerate(self.g[v]):
					if vis[e_to] or not e_cap:
						continue
					tmp_cost = e_cost - dual[e_to] + dual[v]
					if dist[e_to] > dist[v] + tmp_cost:
						dist[e_to] = dist[v] + tmp_cost
						pv[e_to] = v
						pe[e_to] = i
						heapq.heappush(que, (dist[e_to], e_to))
			if not vis[t]:
				break
			for (v, visited) in enumerate(vis):
				if not visited:
					continue
				dual[v] -= dist[t] - dist[v]
			c = flow_limit - flow
			v = t
			while v != s:
				c = min(c, self.g[pv[v]][pe[v]][2])
				v = pv[v]
			v = t
			while v != s:
				(i, j) = (pv[v], pe[v])
				self.g[i][j][2] -= c
				self.g[v][self.g[i][j][1]][2] += c
				v = i
			d = -dual[s]
			flow += c
			cost += c * d
			if prev_cost == d:
				result.pop()
			result.append((flow, cost))
			prev_cost = cost
		return result
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 18
(N, K) = map(int, input().split())
g = MCF_graph(2 * N + 2)
source = 2 * N
sink = 2 * N + 1
g.add_edge(source, sink, N * K, inf)
for i in range(N):
	g.add_edge(source, i, K, 0)
	g.add_edge(N + i, sink, K, 0)
A = list((list(map(int, input().split())) for _ in range(N)))
for (i, ai) in enumerate(A):
	for (j, a) in enumerate(ai):
		g.add_edge(i, N + j, 1, inf - a)
(res_flow, res_cost) = g.flow(source, sink, N * K)
print(N * K * inf - res_cost)
res = [['.'] * N for _ in range(N)]
for (frm, to, cap, flow, cost) in g.edges():
	if frm == source or to == sink or (not flow):
		continue
	res[frm][to - N] = 'X'
for g in res:
	print(''.join(g))


from heapq import heappop, heappush
NUMERIC_LIMITS = (1 << 63) - 1

class McfGraph:

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

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

	class edge:
		__slots__ = ('frm', 'to', 'cap', 'flow', 'cost')

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

	def get_edge(self, i):
		_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):
		for i in range(len(self.pos)):
			yield self.get_edge(i)

	def flow(self, s, t, flow_limit=NUMERIC_LIMITS):
		return self.slope(s, t, flow_limit)[-1]

	def dual_ref(self, s, t):
		dist = [NUMERIC_LIMITS] * self._n
		self.pv = [-1] * self._n
		self.pe = [-1] * self._n
		vis = [False] * self._n
		que = []
		dist[s] = 0
		heappush(que, (0, s))
		while que:
			(_, v) = heappop(que)
			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 - self.dual[e.to] + self.dual[v]
				if dist[e.to] - dist[v] > cost:
					dist[e.to] = dist[v] + cost
					self.pv[e.to] = v
					self.pe[e.to] = i
					heappush(que, (dist[e.to], e.to))
		if not vis[t]:
			return False
		for v in range(self._n):
			if not vis[v]:
				continue
			self.dual[v] -= dist[t] - dist[v]
		return True

	def slope(self, s, t, flow_limit=NUMERIC_LIMITS):
		self.dual = [0] * self._n
		flow = 0
		(cost, prev_cost) = (0, -1)
		result = [(flow, cost)]
		while flow < flow_limit:
			if not self.dual_ref(s, t):
				break
			c = flow_limit - flow
			v = t
			while v != s:
				c = min(c, self.g[self.pv[v]][self.pe[v]].cap)
				v = self.pv[v]
			v = t
			while v != s:
				e = self.g[self.pv[v]][self.pe[v]]
				e.cap -= c
				self.g[v][e.rev].cap += c
				v = self.pv[v]
			d = -self.dual[s]
			flow += c
			cost += c * d
			if prev_cost == d:
				result.pop()
			result.append((flow, cost))
			prev_cost = cost
		return result

	class _edge:
		__slots__ = ('to', 'rev', 'cap', 'cost')

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

def atcoder_practice2_e():
	import sys
	input = sys.stdin.buffer.readline
	(N, K) = list(map(int, input().split()))
	A = [tuple(map(int, input().split())) for _ in range(N)]
	BIG = 10 ** 9
	g = McfGraph(2 * N + 2)
	s = 2 * N
	t = 2 * N + 1
	g.add_edge(s, t, N * K, BIG)
	for i in range(N):
		g.add_edge(s, i, K, 0)
		g.add_edge(N + i, t, K, 0)
	for i in range(N):
		for j in range(N):
			g.add_edge(i, N + j, 1, BIG - A[i][j])
	result = g.flow(s, t, N * K)
	print(N * K * BIG - result[1])
	grid = [['.'] * N for _ in range(N)]
	edges = g.edges()
	for e in edges:
		if e.frm == s or e.to == t or e.flow == 0:
			continue
		grid[e.frm][e.to - N] = 'X'
	for g in grid:
		print(''.join(g))
atcoder_practice2_e()


(N, K) = map(int, input().split())
MAP = [list(map(int, input().split())) for i in range(N)]
start = 2 * N + 1
goal = 2 * N + 2
V = 2 * N + 5
EDGE = [[[0, 0] for j in range(V)] for i in range(V)]
for i in range(N):
	EDGE[start][i] = [K, 0]
	EDGE[N + i][goal] = [K, 0]
for i in range(N):
	for j in range(N):
		EDGE[i][N + j] = [1, 10 ** 9 - MAP[i][j]]
		EDGE[N + j][i] = [0, -(10 ** 9 - MAP[i][j])]
EDGE[start][goal] = [float('inf'), 10 ** 9]
BACK = [-1] * V
LA = 0
import heapq
for flow in range(K * N):
	ANS = [float('inf')] * V
	Q = [(0, start)]
	ANS[start] = 0
	while Q:
		(time, fr) = heapq.heappop(Q)
		if time > ANS[fr]:
			continue
		for to in range(V):
			(c, d) = EDGE[fr][to]
			if c > 0 and ANS[to] > ANS[fr] + d:
				ANS[to] = ANS[fr] + d
				BACK[to] = fr
				heapq.heappush(Q, (ANS[to], to))
	LA += ANS[goal]
	NOW = goal
	while NOW != start:
		fr = BACK[NOW]
		EDGE[fr][NOW][0] -= 1
		EDGE[NOW][fr][0] += 1
		NOW = fr
print(K * N * 10 ** 9 - LA)
ALIST = [['.'] * N for i in range(N)]
for i in range(N):
	for j in range(N):
		if EDGE[i][N + j][0] == 0:
			ALIST[i][j] = 'X'
for alist in ALIST:
	print(''.join(alist))