5487 - Partitions
一个矩形的划分是指把一个矩形分成若干个较小的、不重叠的子矩形。图一展示了几个划分的例子。
图二展示了被划分成子矩形的三个相同大小的矩形。B是A通过划分A的两个子矩形得来的。通常的，如果B是A通过划分它的一个或多个子矩形得来，那么我们说B比A更精细，或者说A比B更粗糙。这一关系是偏序的：例如C不比A,B中的任意一个精细或粗糙。
给定同一矩形的两种划分D和E，存在无穷多的比D和E都要精细。在图三中F和G都比D和E要精细。在比D和E精细的划分中，存在唯一的一种最粗糙的划分。这种划分被称为D和E的下确界。在图三中，F是D和E的下确界。
在图四中H和J都比D和E粗糙。J是比D和E都粗糙的所有划分中最精细的，所以称J为D和E的上确界。
写一个程序，给出两种对于相同矩形的划分，求出它们的下确界和上确界。
输入
输入文件包括一个或多个测试数据。每个数据第一行给出矩形的宽度h和高度w(0<w,h<21)。接下来h+1如样例所示给出两种划分。每行包括4*w+3个字符。其中前2*w+1个字符属于第一种划分；最后2*w+1个字符属于第二种划分。一个空格分开两种划分，水平线条用下划线“_”表示，垂直线条用“|”。
输入以两个0结束。
输出
对于输入文件每个数据，输出包括单独一行数据编号(格式如样例所示)，其次是两种划分的下确界和上确界，使用和输入数据相同个格式。
每组数据后输出一个空行。
样例
输入
3 3 _ _ _ _ _ _ |_|_ _| |_| | | | | | | |_ _ _| |_|_ _| 0 0
输出
Case 1: _ _ _ _ _ _ |_|_ _| | | | | | | | |_|_ _| |_ _ _|
来源
蓝桥杯训练