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