RECTNG2 - Partitions

no tags 

A partition of a rectangle is either a whole rectangle or a subdivision the rectangle into either a upper part and a lower part or a left part and a right part, and each part is a partition of the corresponding rectangle. Figure 1 shows several examples of partitions.

Figure 2 shows three equal sized rectangles, partitioned into sub-rectangles. Partition B is obtained from partition A by partitioning two of the sub-rectangles of A. Generally, if a partition B is obtained from A by partitioning one or more of its sub-rectangles, we say that B is finer than A, or that A is coarser than B. This relation is partial: partition C is neither coarser nor finer than A or B.

Given two partitions D and E of the same rectangle, infinitely many partitions exist that are finer than both D and E. In Figure 3 both F and G are finer than D and E. Among the partitions that are finer than both D and E, a unique one exists that is coarsest. This partition is called the infimum of D and E. In Figure 3, partition F is the infimum of D and E.

In Figure 4, both H and J are coarser than D and E. Here J is the finest partition that is coarser than D and E. Then J is the supremum of D and E.

Write a program that, given two partitions of the same rectangle, finds the infimum and the supremum of these partitions.

Input

The input file contains one or more test cases. The first line of each test case gives the width w and height h of the rectangle (0 < w, h <= 20). In the next h+1 lines the two partitions are given, as in the sample. Each of these lines contains 4*w+3 characters. The first 2*w+1 of these belong to the first partition; the last 2*w+1 of these belong to the second partition. A space separates the two partitions. Horizontal lines are created using underscores ‘_’, vertical lines using ‘|’.

The input is terminated by a pair of zeroes.

Output

For every case in the input file the output contains a single line containing the case number (in the format shown in the sample), followed by the infimum and the supremum of the two partitions, using the same format as the input.

Place a blank line after the output of each test case.

Example

Input:
4 3
 _ _ _ _   _ _ _ _ 
|_ _ _ _| |_|_ _ _|
|   |   | |       |
|_ _|_ _| |_ _ _ _|
3 4
 _ _ _   _ _ _ 
| |   | | |   |
| |   | |_|_ _|
|_|_ _| |   | |
|_ _|_| |_ _|_|
0 0

Output:
Case 1:
 _ _ _ _   _ _ _ _ 
|_|_ _ _| |_ _ _ _|
|   |   | |       |
|_ _|_ _| |_ _ _ _|

Case 2:
 _ _ _   _ _ _ 
| |   | |     |
|_|_ _| |     |
|_|_|_| |     |
|_ _|_| |_ _ _|

Please read the problem statement carefully. The judge compares your output and the expected output, any extra whitespace will cause Wrong Answer.

hide comments
John Stephanus Peter: 2015-11-24 12:14:13

Can you tell me what is wrong with my code?

[Rampage] Blue.Mary: 2011-12-15 06:33:02

Thanks :D. To jiangh33: You must read the problem statement CAREFULLY, and the test cases here is by me and my friend g201513.

:D: 2011-12-15 06:33:02

The test cases don't have to be the same on SPOJ. You even have a note in the description: "unofficial testdata". Knowing XilinX, the cases here are stronger than official ones.
If you still think than there's an error here, please open a topic on the forum and attach your source code.

Last edit: 2010-11-28 07:27:41
jiangh33: 2011-12-15 06:33:02

I got AC in ACM/ICPC Live Archive, but WA here

:D: 2011-12-15 06:33:02

Solution to the first is the another imput rectangle. To the second: empty rectangle.

Last edit: 2010-08-09 15:05:53
sofia: 2011-12-15 06:33:02

What is the solution if one rectangle is empty?
There is no rectangle that is corser.
On the other hand there is no rectangle that is finer than a full filled rectangle.


Added by:Fudan University Problem Setters
Date:2008-01-03
Time limit:0.200s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: C99 ERL JS-RHINO PERL6
Resource:ACM/ICPC World Final 2002 (unofficial testdata)