Hãy tìm một lời giải cho bảng Sudoku còn dở dang. Nếu có nhiều hơn một lời giải, in ra một lời giải bất kỳ.

Một bảng Sudoku hoàn chỉnh là bảng ~9 \times 9~ trong đó mỗi hàng, mỗi cột và mỗi khối con ~3 \times 3~ đều chứa đủ các chữ số từ ~1~ đến ~9~, mỗi chữ số đúng một lần.

Dữ liệu đảm bảo tồn tại ít nhất một lời giải.

Dữ liệu vào

Gồm ~9~ dòng, mỗi dòng chứa ~9~ số nguyên trong đoạn ~[0, 9]~. Số ~0~ nghĩa là ô còn trống.

Kết quả

Gồm ~9~ dòng, mỗi dòng chứa ~9~ số nguyên trong đoạn ~[1, 9]~ — một lời giải hợp lệ. Các chữ số đã cho trong dữ liệu vào phải được giữ nguyên.

Ví dụ

Đầu vào:

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

Đầu ra:

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

Giải thích: Mọi hàng, mọi cột và mọi khối ~3 \times 3~ đều chứa đủ các chữ số từ ~1~ đến ~9~, và tất cả các chữ số đã cho ban đầu đều được giữ nguyên.

Giới hạn

Bảng luôn có kích thước ~9 \times 9~ và luôn tồn tại ít nhất một lời giải. Số ô trống có thể lên tới ~81~ (bảng trống hoàn toàn).