Bạn đang bán những bức tranh hình học tuyệt đẹp. Mỗi bức tranh bao gồm các ô vuông kích thước \(1 \times 1\) được sắp xếp thành một lưới không chồng chéo. Ví dụ:

    .##..
    .####
    .####
    .##..

Các ô màu xanh lam được đại diện bởi ký tự #, và các ô màu trắng được đại diện bởi ký tự .. Bạn không sử dụng các màu khác.

Tuy nhiên, không phải ai cũng thích màu xanh lam, và một số khách hàng muốn bạn thay thế tất cả các ô màu xanh trong tranh bằng các ô màu đỏ. Ngặt nỗi, các ô màu đỏ chỉ có kích thước lớn hơn là \(2 \times 2\), điều này khiến việc thay thế trở nên khó khăn.

Bạn có thể che bất kỳ khối ô vuông xanh \(2 \times 2\) nào bằng một ô màu đỏ duy nhất, và lặp lại cho đến khi hoàn tất. Một ô màu đỏ không được đè lên ô màu đỏ khác, không được che các ô màu trắng và không được nằm ngoài phạm vi bức tranh. Ví dụ, bạn có thể thêm các ô màu đỏ vào bức tranh trước đó như sau:

    ./\..
    .\//\
    ./\\/
    .\/..

Mỗi ô màu đỏ ở đây được đại diện bởi một cặp ký tự / ở góc trên bên trái và góc dưới bên phải, và một cặp ký tự \ ở hai góc còn lại.

Cho một bức tranh xanh và trắng, liệu bạn có thể biến nó thành một bức tranh đỏ và trắng theo cách này không?

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào cho biết số lượng bộ thử nghiệm, \(T\). Tiếp theo là \(T\) bộ thử nghiệm.

Mỗi bộ thử nghiệm bắt đầu bằng một dòng chứa \(R\) và \(C\), số hàng và số cột trong bức tranh. \(R\) dòng tiếp theo, mỗi dòng chứa đúng \(C\) ký tự, mô tả bức tranh. Như đã nêu trên, ký tự # đại diện cho ô màu xanh, và ký tự . đại diện cho ô màu trắng.

Dữ liệu ra

Với mỗi bộ thử nghiệm, đầu tiên in ra một dòng chứa "Case #x:", trong đó x là số thứ tự bộ thử nghiệm (bắt đầu từ 1).

Nếu có thể che các ô màu xanh bằng các ô màu đỏ không chồng chéo, hãy in ra \(R\) dòng, mỗi dòng chứa \(C\) ký tự, mô tả bức tranh đỏ và trắng thu được. Như trên, các ô màu đỏ nên được đại diện bởi các ký tự / và \, trong khi các ô màu trắng được đại diện bởi ký tự .. Nếu có nhiều giải pháp khả thi, bạn có thể in ra bất kỳ giải pháp nào.

Nếu nhiệm vụ là bất khả thi, hãy in ra một dòng duy nhất chứa văn bản "Impossible".

Ràng buộc

Phân nhóm

• Small dataset (Test set 1): \(1 \le T \le 20\); \(1 \le R \le 6\); \(1 \le C \le 6\).
• Large dataset (Test set 2): \(1 \le T \le 50\); \(1 \le R \le 50\); \(1 \le C \le 50\).

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

3
2 3
###
###
1 1
.
4 5
.##..
.####
.####
.##..

Case #1:
Impossible
Case #2:
.
Case #3:
./\..
.\//\
./\\/
.\/..

Nguồn

Google Code Jam 2011, Vòng 1C, bài Square Tiles.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.