ミハイルは一般化チェスを学ぶことにした。そのために、彼は $n \times n$ マスのチェス盤を用意した。行 $i$ と列 $j$ の交点にある各マスは、色 $a_{ij}$ で塗られている。

ミハイルは初心者であり、盤を誤って塗っている可能性がある。そのため、盤上のいくつかのマスを塗り直す必要があるかもしれない。盤が正しく塗られているとみなされるのは、以下の2つの条件が満たされる場合である：

• 盤上のマスは、高々2種類の異なる色で塗られている。
• 同じ色で塗られた隣接するマス（辺を共有する）が存在しない。

ミハイルは、大きな盤でプレイするのは自分には難しすぎると気づいた。そのため、彼は盤から最初の $r$ 行と最初の $c$ 列からなる長方形領域を切り出し、この領域のみを正しく塗ることにしたかもしれない。 各数値のペア $(r, c)$（$1 \le r \le n$, $1 \le c \le n$）について、最初の $r$ 行と最初の $c$ 列からなる長方形領域が正しく塗られるようにするために塗り直す必要のあるセルの最小数である値 $b_{rc}$ を計算せよ。

入力

1行目には整数 $n$（$1 \le n \le 400$）が含まれる。これは盤のサイズである。 次の $n$ 行は盤の状態を表す。これらのうち $i$ 行目には $n$ 個の整数 $a_{i1}, \dots, a_{in}$（$1 \le a_{ij} \le 10^9$）が含まれる。これは $i$ 行目の各マスの色である。

出力

$n$ 行を出力せよ。$i$ 行目には $n$ 個の整数 $b_{i1}, \dots, b_{in}$ が含まれるべきである。

小課題

入出力例

入力例 1

2
7 7
7 7

出力例 1

0 1
1 2

入力例 2

3
1 1 2
2 4 4
3 1 2

出力例 2

0 1 1
0 2 4
1 3 5