SP2276 RECTNG2 - Partitions

一个矩形的划分可以是完整的矩形本身，也可以是将矩形分为上下两部分或左右两部分，而每个部分都可以继续划分。图 1 展示了几个划分的示例。  图 2 则展示了三个相同大小的矩形，分别被划分为若干子矩形。划分 B 是通过对 A 的两个子矩形进行进一步划分得到的。通常来说，如果一个划分 B 是通过进一步划分 A 的一个或多个子矩形得到的，我们称 B 比 A 更细，或者说 A 比 B 更粗。这个关系并不具有普遍性：划分 C 既不比 A 更粗也不比 A 更细，同样也不比 B 更粗或更细。  对于同一个矩形的两个划分 D 和 E，存在无限多的划分比 D 和 E 都更细。在图 3 中，划分 F 和 G 都比 D 和 E 更细。在这些更细的划分中，唯一存在一个最粗的划分，这称为 D 和 E 的下确界。在图 3 中，划分 F 是 D 和 E 的下确界。  图 4 中的 H 和 J 都比 D 和 E 更粗。J 是其中最细的比 D 和 E 更粗的划分，因此 J 是 D 和 E 的上确界。  请编写一个程序，给定同一个矩形的两个划分，找出这两个划分的下确界和上确界。

输入包含一个或多个测试用例。每个测试用例的第一行给出矩形的宽度 $w$ 和高度 $h$（$0 < w, h \leq 20$）。接下来的 $h+1$ 行中给出了两个划分的具体结构，如样例所示。每一行包含 $4 \times w + 3$ 个字符。前 $2 \times w + 1$ 个字符属于第一个划分；后 $2 \times w + 1$ 个字符属于第二个划分。两个划分之间有一个空格间隔。水平线用下划线 ‘\_’ 表示，垂直线用 ‘|’ 表示。 输入以一对零结束。

对于每个测试用例，输出一行，包含测试用例编号（格式如样例所示），随后是两个划分的下确界和上确界，以与输入相同的格式输出。 在每个测试用例的输出后留一个空行。 **本翻译由 AI 自动生成**