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*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*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