시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 (추가 시간 없음) 512 MB 216 58 49 27.072%

문제

SNUPC(SNU Patisserie Cafe)에서는 유명한 케이크를 팔고 있다. 이 케이크는 N개의 행과 N개의 열로 나눌 수 있는 정사각형 모양이다. 그리고 이 케이크를 1 × 1 크기의 정사각형 조각 N2개로 잘랐을 때, 각 조각 위에 체리가 하나씩 올려져 있다. ij열 조각 위의 체리는 Ci,j만큼의 당도를 가지고 있다. 이 케이크는 한 번에 먹기에는 너무 크기 때문에, 각 변이 축에 평행하고 각 꼭짓점의 x좌표와 y좌표가 정수인 정사각형 모양으로 잘라내어 판매하고 있는데, 잘라낸 정사각형의 한 변의 길이를 X라고 했을 때, 잘라낸 조각을 X2원에 판매한다.

이 가게에 슈퍼 부자 Corea가 방문하였다. Corea는 이전 가게에서 이미 너무 많은 음식을 먹었기 때문에, 케이크를 산 다음 그 위에 있는 체리 중 가장 단 체리 한 조각만을 먹으려고 한다. 또, 이 케이크의 특정한 조각을 하나 골라서, 그 조각은 반드시 포함되도록 구매하려고 한다.

Corea는 돈을 낭비하는 것을 별로 좋아하지 않기 때문에, 자신이 먹게 될 체리의 당도에서 케이크를 사는데 내는 비용을 뺀 값을 최대화하려고 한다. 하지만 Corea는 그런 사소한 결정을 하는데 낭비할 시간이 없기 때문에, Corea가 케이크에 포함될 조각을 고를 동안 당신은 Corea가 선택할 수 있는 모든 경우의 수에 대해서 Corea가 먹게 될 체리의 당도에서 케이크의 비용을 뺀 값의 최댓값을 계산해야 한다.

입력

첫 번째 줄에 전체 케이크의 행과 열의 길이 N(1 ≤ N ≤ 1,000)이 주어진다.

두 번째 줄부터 총 N개의 줄에 각각 N개의 정수 Ci,j (1 ≤ Ci,j ≤ 1,000)가 주어지는데, 이는 ij열 조각 위에 놓인 체리의 당도이다.

출력

공백으로 구분된 N개의 정수를 N줄에 걸쳐 출력한다.

i번째 줄의 j번째 정수로 출력하는 값은 ij열 조각을 포함하도록 케이크를 구매했을 때 Corea가 먹게 될 체리의 당도에서 케이크의 비용을 뺀 값의 최댓값이다.

예제 입력 1

2
2 1
4 1

예제 출력 1

1 0
3 0

예제 입력 2

3
1 2 3
4 5 6
7 8 9

예제 출력 2

1 2 2
4 5 5
6 7 8