Bạn đang chuẩn bị tiệc cho một nhóm trẻ em và phục vụ một chiếc bánh có dạng lưới gồm \(R\) hàng và \(C\) cột. Trợ lý đã bắt đầu trang trí bằng cách viết chữ cái đầu tên của mỗi đứa trẻ bằng kem lên đúng một ô bánh. Mỗi ô chứa nhiều nhất một chữ cái; vì không có hai đứa trẻ nào có cùng chữ cái đầu, không chữ cái nào xuất hiện quá một lần trên bánh.

Mỗi đứa trẻ muốn nhận một miếng bánh hình chữ nhật duy nhất, có các cạnh theo đường lưới, chứa chữ cái đầu của mình và không chứa chữ cái đầu của bất kỳ đứa trẻ nào khác. Bạn có thể gán mọi ô trống của chiếc bánh cho một đứa trẻ sao cho đạt yêu cầu đó không? Đề bảo đảm luôn có thể làm được. Không cần chia bánh đều; thậm chí một hoặc nhiều em có thể chỉ nhận miếng \(1\times1\) — đây sẽ là một bài học cuộc sống quý giá về sự bất công.

Dữ liệu vào

Dòng đầu chứa số lượng bộ test \(T\). Mỗi bộ test bắt đầu bằng một dòng chứa hai số nguyên \(R\) và \(C\). Sau đó là \(R\) dòng, mỗi dòng gồm \(C\) ký tự mô tả chiếc bánh. Mỗi ký tự hoặc là một chữ cái tiếng Anh viết hoa (trợ lý đã viết chữ đó vào ô), hoặc là ? (ô còn trống).

Dữ liệu ra

Với mỗi bộ test, trước tiên in một dòng chỉ chứa Case #x:, trong đó x là số thứ tự bộ test (bắt đầu từ 1). Sau đó in thêm \(R\) dòng, mỗi dòng \(C\) ký tự.

Lưới đầu ra phải giống hệt lưới đầu vào, ngoại trừ mọi dấu ? được thay bằng một chữ cái tiếng Anh viết hoa, biểu thị ô đó thuộc miếng bánh của đứa trẻ có chữ cái đầu tương ứng. Không được thêm chữ cái nào vốn không xuất hiện trong đầu vào. Với mỗi chữ cái, miền gồm tất cả các ô mang chữ đó phải là một hình chữ nhật duy nhất có cạnh theo đường lưới.

Nếu có nhiều đáp án, có thể in bất kỳ đáp án nào.

Ràng buộc

• \(1 \le T \le 100\).
• Lưới đầu vào có ít nhất một chữ cái.
• Không chữ cái nào xuất hiện trong nhiều hơn một ô của lưới đầu vào.
• Mỗi bộ test được bảo đảm có ít nhất một đáp án.

Phân nhóm

• Test Set 1 (Visible): \(1 \le R \le 12\), \(1 \le C \le 12\), \(R\times C\le12\).
• Test Set 2 (Hidden): \(1 \le R \le 25\), \(1 \le C \le 25\).

Đ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
3 3
G??
?C?
??J
3 4
CODE
????
?JAM
2 2
CA
KE

Case #1:
GGJ
CCJ
CCJ
Case #2:
CODE
COAE
JJAM
Case #3:
CA
KE

Nguồn

Google Code Jam 2017, Vòng 1A, bài Alphabet Cake.

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