📖 Bài giảng & lời giải: đây là Bài tập 7 trong bài giảng Thuật toán qua trò chơi 3: Sudoku trên blog Lập trình thuật toán – có lý thuyết, mô phỏng từng bước, gợi ý và code C++ / Python.

⚠️ Lưu ý: hãy đảm bảo em đã thật sự cố gắng tự làm bài trước, rồi mới xem gợi ý và lời giải nhé!

🎓 Khóa học Lập trình Thuật toán thi đấu của thầy Nguyễn Việt Nam Sơn – 111 buổi video, kèm cặp cá nhân, luyện thi chuyên Tin · HSG Tin học · Tin học trẻ · đội tuyển quốc gia · Olympic/ICPC. 👉 Xem chi tiết khóa học · Thành tích học viên

📞 Đăng ký học: Zalo 0767 666 702 · Facebook Nguyễn Việt Nam Sơn · 🌐 laptrinhthuattoan.blogspot.com

Sudoku chẵn lẻ là một biến thể của Sudoku $9 \times 9$: ngoài luật thông thường (mỗi hàng, mỗi cột, mỗi khối $3 \times 3$ chứa đủ các số từ 1 đến 9), một số ô được đánh dấu C (phải điền số chẵn) hoặc L (phải điền số lẻ).

Cho đề bài, bảo đảm có đúng một lời giải. Hãy in lời giải đó.

Dữ liệu vào

• 9 dòng đầu, mỗi dòng 9 số nguyên từ $0$ đến $9$ cách nhau bởi dấu cách: các số cho sẵn ($0$ là ô trống).
• 9 dòng tiếp theo, mỗi dòng là một xâu độ dài 9 gồm các ký tự ., C, L: ký tự thứ $j$ của dòng $i$ cho biết ô $(i, j)$ không có ràng buộc (.), phải chẵn (C) hay phải lẻ (L). Ô cho sẵn số cũng có thể được đánh dấu, và khi đó số cho sẵn luôn đúng với dấu.

Kết quả

In ra 9 dòng, mỗi dòng 9 số của lời giải, cách nhau một dấu cách.

Sample Input

0 0 0 0 0 0 0 0 6
3 0 0 8 0 0 0 5 0
0 0 0 0 7 6 0 0 0
0 8 0 1 0 0 4 0 0
6 0 3 0 0 0 0 0 0
0 5 0 0 0 0 0 0 0
5 0 0 9 0 0 0 6 0
0 0 0 0 0 0 9 0 0
0 0 4 0 1 0 0 0 0
.LCL.L.C.
L.CC.LL..
L..C.CCC.
.C.....L.
..L...L..
C.L.....C
L...L....
..C..C..L
L....C..L

Sample Output

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