Centre for Gifted Education - Hanoi university of Technology

Đệ quy (tiếng Anh: recursion) là phương pháp dùng trong các chương trình máy tính trong đó có một hàm tự gọi chính nó.

Kỹ thuật nhánh cận:

Kỹ thuật này thêm vào quay lui khả năng đành giá theo từng bước, nếu tại bước i, giá trị thử gán cho X-i không có hy vọng tìm thấy cấu hình tốt hơn cấu hình BESTCONFIG thì thử gán giá trị khác mà không phải gọi đệ qui tìm tiếp hay ghi nhận kết quả làm gì. Nghiệm của bài toán sẽ được làm tốt dần bởi khi tìm ra một cấu hình mới nhất, ta không in kết quả ngay mà sẽ cập nhật BESTCONFIG bằng cấu hình mới vừa tìm được.

Hãy dùng kỹ thuật nhánh cận để giải bài toán SUDOKU:

SUDOKU là một loại trò chơi lôgic trên 1 ma trận 9 x 9. Cách chơi là điền số từ 1 đến 9 vào những ô trống của ma trận thoả mãn:

1. Mỗi cột dọc đều có đủ các số từ 1 đến 9.

2. Mỗi hàng ngang đều có đủ các số từ 1 đến 9.

3. Mỗi vùng ô vuông 3 x 3 được chia như hình vẽ đều có đủ các số từ 1 đến 9.

Input

Ma trận 9 x 9 trong đó có 1 số ô đã được điền sẵn, những ô chưa được điền là ô trống và được đánh số 0.

Output

In ra ma trận SUDOKU sau khi đã được giải, nếu có nhiều kết quả bạn chỉ cần in ra 1 kết quả bất kỳ.

Example

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

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