스도쿠 3

자하크를 물리칠 예언의 주인공인 전설적인 페르시아 영웅 페리이든은 강한 정신과 강한 육체가 함께 필요하다고 믿는다. 그는 얼마 전 일본 상인에게서 스도쿠라는 새로운 퍼즐을 배웠다. 스도쿠는 $n^2 \times n^2$ 칸의 격자판에서 진행된다. 전체 격자는 각각 $n \times n$ 크기인 $n^2$개의 부분 격자로 나뉜다. 각 칸은 비어 있거나 1부터 $n^2$까지의 정수를 가질 수 있다. 스도쿠 보드는 다음 조건을 모두 만족하면 유효하다. 1. 각 행의 모든 수는 서로 달라야 한다. 2. 각 열의 모든 수는 서로 달라야 한다. 3. 각 부분 격자의 모든 수는 서로 달라야 한다. 다음 그림은 빈칸이 없는 유효한 스도쿠 보드 두 개를 보여준다. 페리이든에게는 빈칸이 일부 있는 유효한 보드가 있고, 그는 도움을 요청했다. 보드를 유효한 상태로 유지하면서 빈칸을 최대한 많이 채우는 것이 과제다. 빈칸을 모두 채울 수 있는 방법이 적어도 하나 있다고 보장된다. 이 문제는 출력 전용 문제이므로 소스 코드를 제출할 필요가 없다. 테스트 케이스는 10개이다. 각 테스트 케이스는 스도쿠 보드의 초기 상태인 표 $A$가 담긴 입력 파일로 주어진다. 빈칸 일부를 채운 최종 상태의 표 $B$를 담은 출력 파일을 제출한다. 모든 $A[i][j]$와 $B[i][j]$ 값($1 \le i,j \le n^2$)은 0 이상 $n^2$ 이하의 정수이며, 0은 빈칸을 뜻한다.

첫 줄에 $n$이 주어진다. $1+i$번째 줄($1 \le i \le n^2$)에는 $A[i][1]$부터 $A[i][n^2]$까지의 값이 공백으로 구분되어 주어진다.

$i$번째 줄($1 \le i \le n^2$)에 $B[i][1]$부터 $B[i][n^2]$까지의 값을 공백으로 구분해 출력한다.

$2 \le n \le 20$. $0 \le A[i][j] \le n^2$. 보드 $A$는 유효하며, 빈칸 전부를 유효성을 유지하면서 채울 수 있다.