Các thực khách tại Ngôi nhà Bánh kếp Vô hạn đã chán bánh kếp hình tròn, nên các đầu bếp sắp đưa ra một lựa chọn mới trong thực đơn: bánh waffle! Để quảng bá, họ đã làm một chiếc waffle lớn có dạng lưới ô vuông gồm \(R\) hàng và \(C\) cột. Mỗi ô của chiếc waffle hoặc trống, hoặc chứa đúng một hạt sô-cô-la.

Giờ là lúc các đầu bếp chia chiếc waffle cho những thực khách đang đói. Một đường cắt ngang chạy dọc toàn bộ đường lưới nằm giữa hai hàng; một đường cắt dọc chạy dọc toàn bộ đường lưới nằm giữa hai cột. Để làm việc hiệu quả, một đầu bếp sẽ thực hiện đúng \(H\) đường cắt ngang khác nhau và một đầu bếp khác sẽ thực hiện đúng \(V\) đường cắt dọc khác nhau. Nhờ đó, họ tạo ra đúng một miếng cho mỗi người trong số \((H+1)\times(V+1)\) thực khách. Các miếng không nhất thiết có cùng kích thước, nhưng điều đó không sao; nghiên cứu thị trường cho thấy thực khách không quan tâm đến chuyện này.

Điều thực khách quan tâm là số hạt sô-cô-la họ nhận được, vì vậy mỗi miếng phải có chính xác cùng một số hạt sô-cô-la. Bạn có thể xác định liệu các đầu bếp có đạt được mục tiêu này với số đường cắt ngang và dọc đã cho hay không?

Dữ liệu vào

Dòng đầu tiên chứa số lượng bộ test \(T\); tiếp theo là \(T\) bộ test. Mỗi bộ bắt đầu bằng một dòng chứa bốn số nguyên \(R\), \(C\), \(H\), \(V\): số hàng và số cột của chiếc waffle, cùng số đường cắt ngang và dọc chính xác mà các đầu bếp phải thực hiện. Sau đó có thêm \(R\) dòng, mỗi dòng gồm \(C\) ký tự; ký tự thứ \(j\) trên dòng thứ \(i\) biểu diễn ô ở hàng \(i\), cột \(j\) của chiếc waffle. Mỗi ký tự là @, nghĩa là ô đó có một hạt sô-cô-la, hoặc ., nghĩa là ô đó trống.

Dữ liệu ra

Với mỗi bộ test, in một dòng Case #x: y, trong đó x là số thứ tự bộ test (bắt đầu từ 1), còn y là POSSIBLE nếu các đầu bếp có thể đạt mục tiêu như mô tả ở trên, hoặc IMPOSSIBLE nếu không thể.

Ràng buộc

• \(1\le T\le100\).

Phân nhóm

Test Set 1 (Hiển thị):

• \(2\le R\le10\).
• \(2\le C\le10\).
• \(H=1\).
• \(V=1\).

Test Set 2 (Ẩn):

• \(2\le R\le100\).
• \(2\le C\le100\).
• \(1\le H<R\).
• \(1\le V<C\).

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

6
3 6 1 1
.@@..@
.....@
@.@.@@
4 3 1 1
@@@
@.@
@.@
@@@
4 5 1 1
.....
.....
.....
.....
4 4 1 1
..@@
..@@
@@..
@@..
3 4 2 2
@.@@
@@.@
@.@@
3 4 1 2
.@.@
@.@.
.@.@

Case #1: POSSIBLE
Case #2: IMPOSSIBLE
Case #3: POSSIBLE
Case #4: IMPOSSIBLE
Case #5: POSSIBLE
Case #6: IMPOSSIBLE

.@@. .@
.... .@

@.@. @@

Nguồn

Google Code Jam 2018, Vòng 1A, bài Waffle Choppers.

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