Sudoku

Sudoku là một trò chơi điền số trên bảng kích thước \(9 \times 9\).

Ban đầu, một số ô đã chứa các số từ \(1\) đến \(9\), còn các ô chưa điền được ký hiệu bằng số \(0\).

Một bảng Sudoku hợp lệ phải đồng thời thỏa mãn các điều kiện sau:

• Mỗi hàng chứa đầy đủ các số từ \(1\) đến \(9\), mỗi số xuất hiện đúng một lần.
• Mỗi cột chứa đầy đủ các số từ \(1\) đến \(9\), mỗi số xuất hiện đúng một lần.
• Mỗi ô vuông con kích thước \(3 \times 3\) ở các góc chứa đầy đủ các số từ \(1\) đến \(9\), mỗi số xuất hiện đúng một lần.

Yêu cầu. Hãy điền các ô còn trống để thu được một bảng Sudoku hợp lệ.

Đề bài đảm bảo bảng Sudoku đầu vào có ít nhất 1 nghiệm.

Input

Gồm đúng \(9\) dòng.

Mỗi dòng chứa \(9\) số nguyên \(a_{i,1}, a_{i,2}, \ldots, a_{i,9}\).

Mỗi số thỏa mãn

Trong đó, số \(0\) biểu thị một ô chưa được điền.

Output

In ra đúng \(9\) dòng.

Mỗi dòng gồm \(9\) số nguyên biểu diễn bảng Sudoku sau khi đã được hoàn thành.

Input

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

Output

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

Notes

Trong ví dụ trên, bảng Sudoku sau khi hoàn thành thỏa mãn các quy tắc của trò chơi.