Bessie에게는 $N\times N$ ($1\le N\le 1000$) 덧셈 표가 있다. 모든 $1\le r,c\le N$에 대해 $r$행 $c$열의 정수는 $r+c$이다. 예를 들어 $N=3$이면 다음과 같다.

2 3 4
3 4 5
4 5 6

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

1. 두 행 바꾸기

2. 두 열 바꾸기

3. 표에 모두 존재하는 두 값 $a$와 $b$를 골라 모든 $a$를 $b$로, 모든 $b$를 $a$로 동시에 바꾸기.

종류는 항상 증가하는 순서로 수행한다. 먼저 종류 $1$을 원하는 만큼 (0번일 수도 있다), 다음 종류 $2$, 마지막으로 종류 $3$을 수행한다.

종류 $1$과 $2$를 전부 마치고 종류 $3$은 아직 수행하지 않았을 때 가능한 표 상태를 복원하여라. 답이 여러 개면 사전순으로 가장 작은 것을 출력한다.

표의 사전순을 비교하려면 자연스러운 순서 (행은 위에서 아래로, 각 행은 왼쪽에서 오른쪽으로)로 읽고 처음으로 다른 값을 비교한다.

입력

첫째 줄에는 $N$이 주어진다.

다음 $N$개의 줄에는 각각 $N$개의 정수가 주어지며 Elsie가 섞은 뒤의 덧셈 표이다.

출력

종류 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
3 4 5
4 5 6
-> (연산 1: 열 2와 3 바꾸기)
2 4 3
3 5 4
4 6 5
-> (연산 1: 열 1과 2 바꾸기)
4 2 3
5 3 4
6 4 5
-> (연산 3: 값 2와 3 바꾸기)
4 3 2
5 2 4
6 4 5
-> (연산 3: 값 3과 4 바꾸기)
3 4 2
5 2 3
6 3 5

참고: 다음 상태도 종류 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

서브태스크

• 입력 4-5: $N\le 6$
• 입력 6-7: $N\le 8$
• 입력 8-11: $N\le 100$
• 입력 12-15: 추가 제한이 없다.

문제 제작: Benjamin Qi