Hoàn thiện bảng Sudoku

Sudoku là trò chơi điền số trên lưới \(9 \times 9\) chia thành chín khối con \(3 \times 3\). Một lưới được điền đầy đủ khi mỗi hàng, mỗi cột và mỗi khối con \(3 \times 3\) đều chứa mỗi chữ số từ \(1\) đến \(9\) đúng một lần.

Cho một lưới Sudoku đã điền sẵn một số ô (các ô còn trống được ghi bằng số \(0\)). Hãy điền nốt các ô trống để hoàn thiện lưới. Dữ liệu đảm bảo lưới ban đầu chỉ có đúng một cách hoàn thiện.

Input

Gồm \(9\) dòng, mỗi dòng gồm \(9\) số nguyên từ \(0\) đến \(9\) cách nhau một dấu cách; số \(0\) nghĩa là ô trống.

Output

In ra lưới đã hoàn thiện gồm \(9\) dòng, mỗi dòng \(9\) số cách nhau một dấu cách.

Constraints

• Mỗi số trong lưới thuộc đoạn \([0, 9]\); các số khác \(0\) không vi phạm luật Sudoku.
• Lưới có đúng một nghiệm.

Sample Input

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

Sample Output

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