Alice yêu thích trò chơi Sudoku. Bảng Sudoku 9×9 gồm 9 hàng, 9 cột, chia thành 9 ô vuông 3×3. Mỗi hàng, mỗi cột và mỗi ô 3×3 phải chứa đầy đủ các số từ 1 đến 9, không trùng lặp.

Cho một bảng Sudoku với một số ô đã được điền sẵn (số 0 thể hiện ô trống). Hãy dùng quay lui (backtracking) để điền các ô trống và in ra bảng Sudoku hoàn chỉnh.

Đảm bảo mỗi bảng chỉ có duy nhất một nghiệm.

Input

9 dòng, mỗi dòng 9 số nguyên, số 0 thể hiện ô trống.

Output

9 dòng, mỗi dòng 9 số nguyên, là bảng Sudoku hoàn chỉnh.

Example

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

Output:

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