스도쿠 5

자흐하크를 이겨내야 한다는 예언을 지닌 전설적인 페르시아 영웅 페레이둔은 강한 육체와 함께 강한 정신도 필요하다고 믿는다. 그는 일본 상인에게서 스도쿠라는 새로운 두뇌 퍼즐을 막 배웠다.

스도쿠는 $n^2 \times n^2$개의 칸으로 이루어진 격자판에서 한다. 격자판 전체는 $n \times n$ 크기의 $n^2$개 부분 격자로 나뉜다. 각 칸은 비어 있거나 $1$ 이상 $n^2$ 이하의 정수를 담을 수 있다. 스도쿠 판은 다음 조건을 만족하면 유효하다.

1. 각 행에 있는 수는 모두 다르다.
2. 각 열에 있는 수는 모두 다르다.
3. 각 부분 격자에 있는 수는 모두 다르다.

다음 그림은 빈 칸이 없는 유효한 스도쿠 판 두 개를 보여 준다.

페레이둔은 빈 칸이 몇 개 있는 유효한 판을 가지고 여러분의 도움을 청한다. 여러분은 판을 유효하게 유지하면서 최대한 많은 빈 칸을 채워야 한다. 빈 칸을 모두 채우면서 판을 유효하게 유지하는 방법이 적어도 하나 존재함은 보장된다.

이 문제는 출력 전용 문제이므로 소스 코드를 제출할 필요가 없다. 테스트 케이스는 $10$개이다. 각 테스트 케이스마다 스도쿠 판의 초기 상태인 표 $A$가 담긴 입력 파일이 주어지며, 여러분은 빈 칸 일부를 채운 뒤의 스도쿠 판 최종 상태인 표 $B$를 담은 출력 파일을 제출해야 한다. ($1 \leq i,j \leq n^2$인) 모든 $A[i][j]$와 $B[i][j]$ 값은 $0$ 이상 $n^2$ 이하의 정수이고, 값 $0$은 빈 칸을 나타낸다.

입력은 다음 형식으로 주어진다.

• $1$번째 줄: $\;\;n$
• $1+i$번째 줄 ($1 \leq i \leq n^2$): $\;\; A[i][1] \;\; A[i][2] \;\ldots \; A[i][n^2]$

출력은 다음 형식이어야 한다.

• $i$번째 줄 ($1 \leq i \leq n^2$): $\;\; B[i][1] \;\; B[i][2] \;\ldots \; B[i][n^2]$

• $2 \leq n \leq 20$,
• $0 \leq A[i][j] \leq n^2$,
• 판 $A$는 유효하고, 빈 칸을 모두 채우면서 판을 유효하게 유지할 수 있다.