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.

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}$

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.

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