Problem G - Together to the End

Define a merge of two strings to be any string formed from all the characters in both strings, interspersed, but in their original order. For example, for the strings chocolate and chips, cchocholaiptes is a merge, but chocochilatspe or bananasplit are not. This problem requires writing a program that can tell if a given string is a merge of two other given strings. For the purposes of this problem, the input strings will contain only lowercase alphabetic characters.

The input file consists of three strings A, B, and C, in that order, one string per line. The file contains no blank lines, and the end of the input is marked by the end of the file. The strings A and B will not exceed 1000 characters, and C will not exceed 2000 characters (rest assured that input cases of this length will be tested).

If C is not a merge of A and B, write a single line to the output file that reads "*** NOT A MERGE ***". If C is a merge, write to the output file the string C rewriften with the characters from A in uppercase. If more than one merge is possible, string C should be wriften with each character of A occurring as early as possible (examine the sample input below for such examples).

Examples

1. INPUT FILE:

   chocolate
   chips
   cchocholaiptes

   OUTPUT FILE:

   CcHOChOLAipTEs cchocholaiptes

   
   
   

2. INPUT FILE:

   chocolate
   chips
   bananasplit

   OUTPUT FILE:

   *** NOT A MERGE ***

   
   
   

3. INPUT FILE:

   abac
   bad
   ababacd

   OUTPUT FILE:

   ABAbaCd