Mikhail은 일반화된 체스를 배우기로 결심했습니다. 이를 위해 그는 $n \times n$개의 셀로 구성된 체스판을 준비했습니다. $i$번째 행과 $j$번째 열이 교차하는 각 셀은 $a_{ij}$ 색상으로 칠해져 있습니다.

Mikhail은 초보 플레이어이므로 보드를 잘못 칠했을 수도 있습니다. 따라서 보드의 일부 셀을 다시 칠해야 할 수도 있습니다. 보드가 올바르게 칠해졌다고 간주되려면 두 가지 조건을 만족해야 합니다.

• 보드의 셀은 두 가지 이하의 서로 다른 색상으로 칠해져 있어야 합니다.
• 같은 색상으로 칠해진 인접한 셀(변을 공유하는)이 없어야 합니다.

Mikhail은 큰 보드에서 플레이하는 것이 너무 어렵다는 것을 깨달았습니다. 따라서 그는 자신의 보드에서 처음 $r$개의 행과 처음 $c$개의 열로 구성된 직사각형 영역을 잘라내어 이 영역만 올바르게 칠하기로 결정했습니다. $1 \le r \le n$ 및 $1 \le c \le n$인 각 숫자 쌍 $(r, c)$에 대해 $b_{rc}$ 값을 계산하십시오. 이는 처음 $r$개의 행과 처음 $c$개의 열로 이루어진 직사각형 영역이 올바르게 칠해지도록 다시 칠해야 하는 최소 셀 개수입니다.

입력

첫 번째 줄에는 정수 $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