Code Merging

Background

Version control is the art of managing changes to information. It has long been a critical tool for programmers, who typically spend their time making small changes to software and then undoing those changes the next day. But the usefulness of version control software extends far beyond the bounds of the software development world. Anywhere you can find people using computers to manage information that changes often, there is room for version control.

Some version control systems are also software configuration management (SCM) systems. These systems are specifically tailored to manage trees of source code, and have many features that are specific to software development-such as natively understanding programming languages, or supplying tools for building software.

One nice feature that many SCM systems provide is called "Code Merging", which allows a code to be modified simultaneously by two coders. As long as they work on DIFFERENT parts of the code, modifications could be merged gracefully.

Consider the following code:

void idle(){}
void goShoppingWithGirlFriend(){...}
void playGames(){...}
int main()
{
if (today.isSunday())
idle();
}

Mr. T added a function "greeting Pan Xi" by changing the original code into:

void greetingPX(){ printf("greeting Pan Xi"); }
void idle(){}
void goShoppingWithGirlFriend(){...}
void playGames(){...}
int main()
{
if (today.isSunday())
idle();
}

At the same time, Mr. L added a function "greeting Xue Xiaoyuan" by changing the original code into:

void idle(){}
void goShoppingWithGirlFriend(){...}
void playGames(){...}
void greetingXXY(){ printf("greeting Xue Xiaoyuan"); }
int main()
{
if (today.isSunday())
idle();
}

Note that two modifications are made in different parts of the code, so smart SCMs can happily merge them, preserving both new functionalities:

void greetingPX(){ printf("greeting Pan Xi"); }
void idle(){}
void goShoppingWithGirlFriend(){...}
void playGames(){...}
void greetingXXY(){ printf("greeting Xue Xiaoyuan"); }
int main()
{
if (today.isSunday())
idle();
}

Amazing, right?

But life's not always easy. If someone else changed the last part into:

if(today.isSunday())
playGames();

And another anonymous coder wrote the following:

if(today.isSunday())
goShoppingWithGirlFriend();

I bet no SCM in the world really knows what to do - it totally depends on the coder, though Mr. T and Mr. L both prefer the latter.

Task

In this problem, your task is to implement the following code merging algorithm:

* Each line of a code is considered as an atomic element, so the algorithm actually takes as input two sequences A and B.
* Calculates the longest common subsequence (LCS) of these two sequences, denoted by (a1,b1), (a2,b2), ..., (ak,bk), i.e. The ai-th line of code A matches the bi-th line of code B, and k is the length of the LCS. By "matching", two lines should be exactly the same, including whitespace characters.
* By the definition of LCS, a1<a2<a3<...<ak, b1<b2<b3<...<bk, which are called match points. We split both sequences into k+1 so-called diff-sections by their own match points, then merge each pair of diff-sections one by one.
* Print the merged diff-sections, separated by the lines in the LCS.

IMPORTANT: in order for the result to be stable, the integer sequence (a1, b1, a2, b2, ..., ak, bk) should be lexicographically smallest. Thus, the output of the algorithm is always unique.

For people who're still confused, here is some more technical information: let M[i] be the i-th match-point, i.e., M[i] = A[ai] = B[bi], DA[i] be the i-th diff-section of A, i.e. DA[i] = {A[ai-1+1 ... ai-1]} (note that a0=0, ak+1=len(A)+1). It's not hard to see that code A can be rewritten as: DA[1], M[1], DA[2], M[2], ..., DA[k], M[k], DA[k+1]. We can define DB[i] similarly.

With these symbols, we can easily express the final output of this problem as:

merge(DA[1],DB[1])
M[1]
merge(DA[2],DB[2])
M[2]
merge(DA[3],DB[3])
M[3]
...
M[k]
merge(DA[k+1],DB[k+1])

Where merge(DA[i],DB[i]) is calculated as follows:

* If one of DA[i] and DB[i] is empty, return the other (though it can be again empty)
* otherwise, report a conflict, showing content of the diff-sections in both codes (see sample output below).

The first line contains a single integer T (T <= 20), the number of test cases. Each case contains code A followed by code B. Both codes end with a line containing 9 character #CODE-END (excluding the newline character). Each code contains at most 1000 lines, each line contains no more than 200 characters, and is guaranteed to be followed by a newline character.

For each test case, print the case number in a separate line, then the merged code. The output of each case should be followed by an empty line, including the last test case.

2
void greetingPX(){ printf("greeting Pan Xi"); }
void idle(){}
void goShoppingWithGirlFriend(){...}
void playGames(){...}
int main()
{
    if (today.isSunday())
        idle();
}
#CODE-END
void idle(){}
void goShoppingWithGirlFriend(){...}
void playGames(){...}
void greetingXXY(){ printf("greeting Xue Xiaoyuan"); }
int main()
{
    if (today.isSunday())
        idle();
}
#CODE-END
int main()
{
    if(today.isSunday())
        playGames();
}
#CODE-END
int main()
{
    if(today.isSunday())
        goShoppingWithGirlFriend();
}
#CODE-END

Case 1:
void greetingPX(){ printf("greeting Pan Xi"); }
void idle(){}
void goShoppingWithGirlFriend(){...}
void playGames(){...}
void greetingXXY(){ printf("greeting Xue Xiaoyuan"); }
int main()
{
    if (today.isSunday())
        idle();
}

Case 2:
int main()
{
    if(today.isSunday())
//**** CONFLICT STARTS ****//
//code in A:
        playGames();
//code in B:
        goShoppingWithGirlFriend();
//***** CONFLICT ENDS *****//
}

2009 Asia Regional Ningbo Online