문제

스도쿠는 $9\times 9$ 격자의 각 칸에 $1$부터 $N$까지의 숫자를 채우는 게임이다. 몇몇 칸에는 이미 숫자가 채워져 있고, 빈칸에 숫자를 채우면 되는데 각 행과 각 열 그리고 $9$개의 $3\times 3$ 크기의 격자에 $1$부터 $9$까지의 숫자가 중복 없이 나타나도록 칸을 채우면 된다.

초기 격자의 예시다.

조건을 지키면서 숫자를 잘 채워넣었다.

하다 만 스도쿠 격자가 주어질 때, 마저 칸을 채우는 프로그램을 작성해 보자.

입력

$9$개 줄에 $9$개의 숫자가 공백으로 구분되어 주어진다. 아직 숫자가 채워지지 않은 칸은 $0$으로 주어진다.

초기 빈칸의 개수가 $45$개 이하인 스도쿠 격자만 주어진다.

출력

모든 칸을 채운 스도쿠 격자를 출력한다.

만약 정답이 여러 개라면 그중 하나만 출력한다.

예제 입력 1

0 0 0 0 0 0 0 0 7
0 0 0 4 0 5 0 0 0
0 5 0 1 9 0 0 8 3
0 4 0 0 0 0 0 0 0
0 3 0 0 0 7 0 5 0
5 1 8 0 2 0 4 0 6
0 2 0 7 6 0 0 3 1
0 7 1 3 5 0 0 2 0
0 0 0 0 8 0 7 0 0

예제 출력 1

1 6 9 8 3 2 5 4 7 
2 8 3 4 7 5 6 1 9 
4 5 7 1 9 6 2 8 3 
7 4 6 5 1 8 3 9 2 
9 3 2 6 4 7 1 5 8 
5 1 8 9 2 3 4 7 6 
8 2 5 7 6 4 9 3 1 
6 7 1 3 5 9 8 2 4 
3 9 4 2 8 1 7 6 5