Fortune Telling with Words
Fortune-telling machines are known for crafting stories for those who insert a coin. Occasionally, these predictions do come true.
The company "Mocrosoft–Fortune" is developing a new fortune-telling machine. Users provide two words, A and B, and the machine generates a third word, C, as the result of the prophecy. This word is constructed using the letters from A and B, maintaining the order of letters as they appear in the original words. The machine arranges these letters so that the sequence in C is as ordered as possible, minimizing the number of adjacent letter pairs that are in descending alphabetical order. Assist the programmers at "Mocrosoft–Fortune" in achieving this.
You are given two words, A and B, composed of uppercase Latin letters {A, B, …, Z}. Your task is to insert the letters of word B into word A while preserving the order of letters in B. The goal is to minimize the number of descending (alphabetically) adjacent letter pairs in the resulting word C.
Example: Suppose A = "opq" and B = "leti". The optimal prophecy would be C = "LopqETI". Here, "lopq" and "et" are in non-descending alphabetical order, while "qe" and "ti" form two descending pairs.
Input
The input consists of two lines: the first line contains the word A, and the second line contains the word B. The lengths of both words A and B range from 1 to 100.
Output
On the first line, output the number of descending pairs in the new word C, ensuring this number is minimized. On the second line, output the resulting word C, with the letters from word B in uppercase. If multiple optimal solutions exist, you may output any one of them.