Joy sắp đi nghỉ dài ngày, nên cô thuê kỹ thuật viên lắp một hệ thống an ninh dùng tia laser hồng ngoại. Họ đưa cho cô sơ đồ ngôi nhà dưới dạng lưới ô vuông đơn vị gồm \(R\) hàng và \(C\) cột. Mỗi ô chứa một trong các ký hiệu:

• /: gương hai mặt chạy từ góc dưới trái đến góc trên phải của ô.
• \\: gương hai mặt chạy từ góc trên trái đến góc dưới phải của ô.
• -: máy phát bắn tia theo phương ngang vào ô ngay bên trái và bên phải, nếu có.
• |: máy phát bắn tia theo phương dọc vào ô ngay phía trên và phía dưới, nếu có.
• #: tường. Ngôi nhà không nhất thiết được bao kín bởi một viền tường — đó cũng là một lý do Joy cần hệ thống an ninh!
• .: ô trống.

Tia đi thẳng qua các ô trống. Khi gặp gương, tia phản xạ 90 độ rồi tiếp tục. Một tia đi sang phải gặp gương / sẽ đổi hướng lên; các tia đi lên, sang trái, xuống gặp / lần lượt đổi sang phải, xuống, trái. Gương \\ hoạt động tương tự: tia đi sang phải, lên, trái, xuống lần lượt đổi sang xuống, trái, lên, phải. Tia dừng khi gặp tường hoặc ra ngoài lưới. Các tia có thể cắt nhau; nhưng nếu một tia chạm bất kỳ máy phát nào, kể cả máy đã phát ra nó, máy phát đó sẽ bị phá hủy.

Joy muốn mọi ô trống trong nhà có ít nhất một tia đi qua và không máy phát nào bị phá hủy — phá thiết bị chỉ tổ phí tiền! Các kỹ thuật viên đã lắp xong, nên cô chỉ có thể xoay một số máy phát hiện có 90 độ: có thể đổi - thành | hoặc ngược lại cho bất kỳ số máy nào, kể cả không máy nào.

Hãy tìm một cách đạt mục tiêu của Joy hoặc xác định rằng điều đó là không thể. Không cần cực tiểu hóa số máy phát bị xoay.

Dữ liệu vào

Dòng đầu tiên chứa số bộ test \(T\). Mỗi bộ test bắt đầu bằng hai số nguyên \(R,C\), số hàng và số cột của lưới. Tiếp theo là \(R\) dòng, mỗi dòng gồm \(C\) ký tự thuộc /, \\, -, |, #, . như mô tả.

Dữ liệu ra

Với mỗi bộ test, in Case #x: y, trong đó x là số thứ tự bộ test (bắt đầu từ 1), còn y là IMPOSSIBLE nếu Joy không thể đạt mục tiêu hoặc POSSIBLE nếu có thể. Nếu khả thi, in tiếp đúng \(R\) dòng gồm \(C\) ký tự của lưới đầu vào, trong đó có thể thay không hoặc nhiều ký tự - bằng | hay ngược 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\le100\).
• \(1\le C\le50\).
• Mỗi ký tự lưới thuộc /, \\, -, |, #, ..
• Tổng số máy phát (- và |) từ 1 đến 100.
• Có ít nhất một ô ..

Phân nhóm

Test Set 1 (Visible): \(1\le R\le5\) và lưới không có gương / hay \\.

Test Set 2 (Hidden): \(1\le R\le50\).

Đ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ụ

5
1 3
-.-
3 4
#.##
#--#
####
2 2
-.
#|
4 3
.|.
-//
.-.
#\/
3 3
/|\
\\/
./#

Case #1: IMPOSSIBLE
Case #2: POSSIBLE
#.##
#||#
####
Case #3: POSSIBLE
|.
#|
Case #4: POSSIBLE
.-.
|//
.|.
#\/
Case #5: IMPOSSIBLE

.-.
|//
.-.
#\/

Nguồn

Google Code Jam 2017, Vòng 2, bài Beaming With Joy.

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