На далекій планеті Тау Кіта є незрозумілі нам звичаї. Наприклад, таукитяни надзвичайно незвичайно для землян обирають імена своїм дітям. Батьки так вибирають ім'я дитині, щоб вона могла бути отримана як видаленням деякого набору букв з імені батька, так і видаленням деякого набору букв з імені матері. Наприклад, якщо батька звуть "abacaba", а мати - "bbccaa", то їх дитина може носити імена "a", "bba", "bcaa", але не може носити імена "aaa", "ab" або "bbc" . Можливо, що ім'я дитини збігається з ім'ям батька та/або матері, якщо воно може бути отримане з імені іншого з батьків видаленням кількох (можливо, жодної) літер.

Нехай батько на ім'я \(X\) і мати на ім'я \(Y\) обирають ім'я своїй новонародженій дитині. Так як у таукитянських школах учнів часто викликають до дошці в лексикографічному порядку імен учнів, тобто в порядку проходження імен у словнику, то вони хочуть вибрати своїй дитині таке ім'я, щоб вона лексикографічно слідувала якомога пізніше.

• Формально, рядок \(S\) лексикографічно більший за рядок \(T\), якщо виконується одна з двох умов: рядок \(T\) виходить із \(S\) видаленням однієї або більше літер з кінця рядка \(S\);
• перші \((i - 1)\) символів рядків \(T\) і \(S\) не відрізняються, а літера в \(i\)-й позиції рядка \(T\) слідує в алфавіті раніше літери в \(i\)-ї позиції рядка \(S\).

Потрібно написати програму, яка за іменами батька та матері знаходить лексикографічне найбільше ім'я для їхньої дитини.

Формат вхідних даних

Перший рядок містить \(X\) – ім'я батька.

Другий рядок містить \(Y\) – ім'я матері. Кожне ім'я складається з малих літер латинського алфавіту, що включає хоча б одну літеру і має довжину не більше \(10^5\) літер.

Формат вихідних даних

Вихідний файл повинен містити лексикографічно найбільше з можливих імен дитини. У випадку, якщо потрібного імені для дитини не існує, вихідний файл повинен бути порожнім.

Система оцінювання

Правильні рішення для тестів, в яких імена містять лише літери «a» та «b» і мають довжину не більше 1000, оцінюватимуться з 20 балів.

Правильні рішення для тестів, у яких імена містять лише літери «a» та «b» і мають довжину не більше \(10^5\), оцінюватимуться з 40 балів.

Правильні рішення для тестів, у яких імена мають довжину не більше 1000, оцінюватимуться з 40 балів.

Приклад вхідних даних

abcabca
abcda

Приклад вихідних даних

ca

Приклад вхідних даних

ccba
accbbaa

Приклад вихідних даних

ccba