베시는 \(N\times N\) 크기의 덧셈표를 가지고 있다. 모든 \(1\le r,c\le N\)에 대해 \(r\)행 \(c\)열에 적힌 정수는 \(r+c\)이다. 예를 들어 \(N=3\)이면 표는 다음과 같다.

2 3 4
3 4 5
4 5 6

안타깝게도 엘시가 이 표를 가져가 다음 세 종류의 연산을 원하는 만큼 수행하여 표를 뒤섞었다.

1. 두 행을 서로 바꾼다.
2. 두 열을 서로 바꾼다.
3. 표에 모두 존재하는 두 값 \(a\)와 \(b\)를 선택한다. 값이 \(a\)인 모든 칸을 동시에 \(b\)로 바꾸고, 값이 \(b\)인 모든 칸을 동시에 \(a\)로 바꾼다.

엘시는 항상 종류 번호가 증가하는 순서로 연산을 수행한다. 즉, 먼저 1번 연산을 원하는 만큼 수행하고, 그다음 2번 연산을 원하는 만큼 수행한 뒤, 마지막으로 3번 연산을 원하는 만큼 수행한다. 어떤 종류의 연산은 한 번도 수행하지 않을 수도 있다.

엘시가 1번과 2번 연산을 모두 끝낸 뒤, 3번 연산을 시작하기 전 표의 가능한 상태 하나를 복구하여라. 가능한 답이 여러 개라면 사전순으로 가장 작은 표를 출력한다.

두 표의 사전순을 비교할 때에는 각 표를 위쪽 행부터 아래쪽 행의 순서로, 각 행에서는 왼쪽부터 오른쪽 순서로 읽는다. 이 순서에서 처음으로 값이 다른 칸의 값이 더 작은 표가 사전순으로 더 작다.

입력

첫째 줄에 정수 \(N\)이 주어진다. (\(1\le N\le 1000\))

다음 \(N\)개의 줄에 엘시가 모든 연산을 끝낸 뒤의 덧셈표가 주어진다. 각 줄에는 \(N\)개의 정수가 공백으로 구분되어 주어진다.

출력

엘시가 1번과 2번 연산을 모두 끝낸 뒤, 3번 연산을 시작하기 전 표로 가능한 상태 중 사전순으로 가장 작은 것을 출력한다. 답이 존재함이 보장된다.

예제 입력 1

1
2

예제 출력 1

2

엘시가 어떤 연산을 수행하더라도 표는 변하지 않는다.

예제 입력 2

3
3 4 2
5 2 3
6 3 5

예제 출력 2

4 2 3
5 3 4
6 4 5

엘시가 수행했을 수 있는 연산 과정 하나는 다음과 같다.

2 3 4       2 4 3       4 2 3       4 3 2       3 4 2
3 4 5  ->   3 5 4  ->   5 3 4  ->   5 2 4  ->   5 2 3
4 5 6       4 6 5       6 4 5       6 4 5       6 3 5

앞의 두 화살표에서는 각각 두 열을 교환했고, 뒤의 두 화살표에서는 각각 값 \(2\)와 \(3\), 값 \(3\)과 \(4\)를 교환했다.

다음 표도 1번과 2번 연산이 끝난 뒤의 가능한 상태이지만, 올바른 답보다 첫째 행의 두 번째 값이 크므로 사전순으로 가장 작지 않다.

4 6 5
3 5 4
2 4 3

예제 입력 3

6
8 10 5 6 7 4
12 11 10 4 8 2
5 4 6 7 9 8
10 2 4 8 5 12
6 8 7 9 3 5
4 12 8 5 6 10

예제 출력 3

7 5 8 9 10 6
4 2 5 6 7 3
8 6 9 10 11 7
5 3 6 7 8 4
9 7 10 11 12 8
6 4 7 8 9 5

서브태스크

출처

USACO 2025 January Contest, Silver, Problem 3. Table Recovery