Game Sudoku là một bảng số có kích thước $9x9$ đã điền sẵn một số vị trí có các giá trị trị từ 1 đến 9 còn lại là các ô trống. Nhiệm vụ của người chơi là điền vào các ô trống sao cho mỗi hàng mỗi cột đều chỉ có đúng 1 số từ 1 đến 9 (không có 2 hàng, hai cột nào có giá trị giống nhau). Ngoài ra thì Bảng số còn chia ra 9 khu vực tương đều có kích cỡ $3x3$ bởi hai đường cắt ngang và cắt dọc. Mỗi khu vực này cũng tuân thủ quy tắc như hàng và như cột tức là cũng nhận các giá trị từ 1 đến 9 và không có hai giá trị nào bằng nhau.

https://vi.wikipedia.org/wiki/Sudoku

Người chơi sẽ nhận được một bảng số có sắn trong đó có rất nhiều vị trí được bỏ trống, người chơi phải điền các số vào các ô trống này thỏa mãn các quy tắc ở trên.

Nhiệm vụ của bạn là đọc một ma trận Sudoku, những vị trí chưa được điền có giá trị là 0 bạn phải xuất ra ma trận kết quả của bài toán

Input

Gồm ma trận $9\ast 9$ gồm các giá trị từ 0 đến 9, vị trí nào chưa điền có giá trị $0$

Output

Ma trận $9\ast 9$ là lời giải của game biết rằng mỗi bài chỉ có duy nhất 1 lời giải

Ví dụ

Input

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

Output

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