{"raw_statement":[{"iden":"problem statement","content":"There is an $N\\times N$ grid where each cell contains an integer between $0$ and $5$, inclusive. Let $(i,j)$ denote the cell at the $i$\\-th row from the top and the $j$\\-th column from the left $(1\\leq i,j\\leq N)$. The integer written in cell $(i,j)$ is $A _ {i,j}$.\nYou can perform the following operation any number of times, possibly zero:\n\n*   Choose a cell $(i,j)$ with $0$ written in it and an integer $x$ between $1$ and $5$, inclusive. Change the number written in the chosen cell to $x$.\n\nAfter the operations, let $B _ {i,j}$ be the integer written in cell $(i,j)$. The **cost** of the grid is defined as the sum of the squares of the differences between the integers written in adjacent cells. In other words, the cost is represented by the following formula:\n\n<center>$\\displaystyle\\sum _ {i=1} ^ N\\sum _ {j=1} ^ {N-1}(B _ {i,j}-B _ {i,j+1})^2+\\sum _ {i=1} ^ {N-1}\\sum _ {j=1} ^ N(B _ {i,j}-B _ {i+1,j})^2$</center>\n\nAmong all possible states of the grid after the operations, find the one with the minimum cost.\nIf multiple grid states have the minimum cost, you may print any of them."},{"iden":"constraints","content":"*   $1\\leq N\\leq20$\n*   $0\\leq A _ {i,j}\\leq 5\\ (1\\leq i\\leq N,1\\leq j\\leq N)$\n*   All input values are integers."},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$N$\n$A _ {1,1}$ $A _ {1,2}$ $\\ldots$ $A _ {1,N}$\n$A _ {2,1}$ $A _ {2,2}$ $\\ldots$ $A _ {2,N}$\n $\\vdots$  $\\ \\vdots$  $\\ddots$  $\\vdots$\n$A _ {N,1}$ $A _ {N,2}$ $\\ldots$ $A _ {N,N}$"},{"iden":"sample input 1","content":"5\n0 2 1 0 4\n4 0 0 0 2\n3 1 0 3 0\n1 0 0 0 0\n0 0 2 0 5"},{"iden":"sample output 1","content":"3 2 1 2 4\n4 2 2 2 2\n3 1 2 3 3\n1 1 2 3 4\n1 1 2 3 5\n\nThe given grid is as follows:\n![image](https://img.atcoder.jp/abc347/0748d5e94455d9f4c627617596f61af6.png)\nAfter performing operations to achieve the state shown on the right of the figure, the cost will be $2 ^ 2\\times6+1 ^ 2\\times18+0 ^ 2\\times16=42$.\nThe cost cannot be $41$ or less, so printing the corresponding $B _ {i,j}$ for this state would be accepted."},{"iden":"sample input 2","content":"3\n0 0 0\n0 0 0\n0 0 0"},{"iden":"sample output 2","content":"0 0 0\n0 0 0\n0 0 0\n\nThe cost is already $0$ from the beginning, so not performing any operations minimizes the cost.\nIf multiple grid states have the minimum cost, you may print any of them, so the following output would also be accepted:\n\n2 2 2\n2 2 2\n2 2 2"},{"iden":"sample input 3","content":"10\n1 0 0 3 0 0 0 0 0 0\n1 0 0 4 0 1 0 5 0 0\n0 0 0 0 0 0 2 0 3 0\n0 0 2 0 0 0 4 0 0 3\n0 3 4 3 3 0 3 0 0 5\n4 1 3 4 4 0 2 1 0 0\n2 0 1 0 5 2 0 1 1 5\n0 0 0 5 0 0 3 2 4 0\n4 5 0 0 3 2 0 3 5 0\n4 0 0 5 0 0 0 3 0 5"},{"iden":"sample output 3","content":"1 2 3 3 3 2 3 4 4 4\n1 2 3 4 3 1 3 5 4 4\n2 2 2 3 3 2 2 3 3 3\n2 2 2 3 3 3 4 3 3 3\n3 3 4 3 3 3 3 2 3 5\n4 1 3 4 4 3 2 1 2 4\n2 2 1 4 5 2 2 1 1 5\n3 3 3 5 4 3 3 2 4 5\n4 5 4 4 3 2 3 3 5 5\n4 4 4 5 4 3 3 3 4 5"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}