Задачі
Гадання на словах
Гадання на словах
Усім давно відомо, що гадальні автомати дуже часто придумують історії для того, хто кинув у нього монетку. Звичайно, іноді буває і так, що пророкування збувається.
Компанія "\textit{Mocrosoft--Fortune}" вирішила розробити новий гадальний автомат. Користувач називає два слова \textbf{A} та \textbf{B}, а потім автомат з букв цих слів складає третє слово -- \textbf{C}, яке є результатом пророцтва. Причому букви зі слова \textbf{A} та зі слова \textbf{B} зустрічаються у слові \textbf{С} у тому ж порядку, що і у самих словах \textbf{A} та \textbf{B}. Гадальна машина бере букви з \textbf{A} та \textbf{B} у такому порядку, що букви у новому слові \textbf{C} получаються максимально упорядкованими. Тобто дві букви, які стоять поруч у \textbf{C} йдуть у спадному порядку якомога рідше. Допоможіть програмістам компанії "\textit{Mocrosoft--Fortune}".
Вам задано два слова \textbf{A} та \textbf{B}, які складаються з прописних букв латинського алфавіту \textbf{\{a, b, …, z\}}. У слово \textbf{A} необхідно вставити букви слова \textbf{B} так, щоб при цьому порядок слідовання букв слова \textbf{B} зберігся. При цьому кількість спадних (за алфавітом) пар двох букв, які стоять поруч, у отриманому слові \textbf{C} повинен бути мінімальним.
\textit{\textbf{Примітка:}} Для прикладу візьмемо \textbf{A} = "\textbf{opq}" та \textbf{B} = "\textbf{leti}", тоді оптимальним пророцтвом буде \textbf{C} = "\textbf{LopqETI}". Тут "\textbf{lopq}" та "\textbf{et}" -- йдуть за неспаданням у відповідності з алфавітом, де "\textbf{qe}" та "\textbf{ti}" - дві пари у спадному порядку.
\InputFile
У вхідному файлі у першому рядку задано слово \textbf{A}, потім у другому рядку задано слово \textbf{B}. Довжини слів \textbf{A} та \textbf{B }знаходяться у межах від \textbf{1} до \textbf{100}.
\OutputFile
У першому рядку виведіть кількість пар у новому слові \textbf{C}, які йдуть у спадному порядку. Ця кількість повинна бути мінімально можливою.
У другому рядку виведіть отримане слово \textbf{C}. Для наочності, букви слова \textbf{B} виведіть великими буквами. Якщо оптимальних розв'язків декілька, то виведіть довільний.
Вхідні дані #1
a b
Вихідні дані #1
0 aB