Description

无限煎饼屋的食客们已经厌倦了圆形煎饼，因此厨师们即将推出新的菜单选项：华夫饼！作为宣传噱头，他们制作了一个巨大的华夫饼，这个华夫饼是一个由 $\mathrm{R}$ 行 $\mathrm{C}$ 列方格组成的网格。每个格子要么是空的，要么包含一颗巧克力豆。

现在，厨师们要把华夫饼分给饥饿的食客们。一条水平切割沿着两行之间的整条网格线切开；一条垂直切割沿着两列之间的整条网格线切开。为了效率，一位厨师会恰好进行 $\mathbf{H}$ 次不同的水平切割，另一位厨师会恰好进行 $\mathbf{V}$ 次不同的垂直切割。这样就会方便地为每位食客分出 $(\mathbf{H}+1) \times (\mathbf{V}+1)$ 块华夫饼。每块的大小不一定相等，但这没关系；市场调研显示食客们并不在意这一点。

食客们真正关心的是他们能分到多少巧克力豆，因此每一块中必须恰好有相同数量的巧克力豆。你能判断厨师们能否用给定数量的水平和垂直切割实现这个目标吗？

Input Format

输入的第一行包含测试用例数 $\mathbf{T}$；接下来有 $\mathbf{T}$ 组测试数据。每组测试数据的第一行包含四个整数 $\mathbf{R}, \mathbf{C}, \mathbf{H}, \mathbf{V}$，分别表示华夫饼的行数、列数，以及厨师们必须进行的水平和垂直切割次数。接下来有 $\mathbf{R}$ 行，每行有 $\mathbf{C}$ 个字符；第 $i$ 行第 $j$ 个字符表示华夫饼第 $i$ 行第 $j$ 列的格子。每个字符要么是 @（表示该格子有一颗巧克力豆），要么是 .（表示该格子为空）。

Output Format

对于每组测试数据，输出一行 Case #x: y，其中 $x$ 是测试用例编号（从 1 开始），$y$ 为 POSSIBLE（如果厨师们能实现目标）或 IMPOSSIBLE（如果不能）。

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

Hint

样例解释

注意，最后两个样例不会出现在测试集 1 中。

在样例 1 中，一种可行的切割方式是在从上往下数的第二行和第三行之间进行水平切割，在从左往右数的第四列和第五列之间进行垂直切割。这样会得到如下的分块，每块恰好有两颗巧克力豆：

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

@.@. @@

在样例 2 中，无论如何切割，都会得到包含不同数量巧克力豆的分块，因此该情况不可能实现。

在样例 3 中，华夫饼中没有巧克力豆。任何切割方式都会得到每块都含有相同数量巧克力豆（零颗），因此食客们会满意……不过也许没有巧克力豆他们就没那么开心了！

在样例 4 中，和样例 2 一样，无论如何切割都无法实现目标。

在样例 5 中，厨师们可以进行仅有的两次水平切割，并在第一列和第三列右侧进行两次垂直切割。

虽然样例 6 在其他水平和垂直切割次数下可能可行，但请记住你必须恰好使用 $H$ 次水平切割和 $V$ 次垂直切割。无论如何进行一次水平切割和两次垂直切割，都无法实现目标。

数据范围

• $1 \leqslant \mathrm{T} \leqslant 100$。

测试集 1（9 分，公开）

• $2 \leqslant \mathbf{R} \leqslant 10$。
• $2 \leqslant \mathbf{C} \leqslant 10$。
• $\mathbf{H}=1$。
• $\mathbf{V}=1$。

测试集 2（16 分，隐藏）

• $2 \leqslant \mathbf{R} \leqslant 100$。
• $2 \leqslant \mathbf{C} \leqslant 100$。
• $1 \leqslant \mathbf{H}<\mathbf{R}$。
• $1 \leqslant \mathbf{V}<\mathbf{C}$。

由 ChatGPT 4.1 翻译