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).
chocolate chips cchocholaiptes
chocolate chips bananasplit
*** NOT A MERGE ***
abac bad ababacd