Олимпиадный тренинг

Задача 33141. Names


Задача

Темы: "Два указателя"
On the distant planet Tau Ceti there are customs that we do not understand. For example, it is very unusual for Taukitians to choose names for their children. The parents choose the name of the child in such a way that it can be obtained both by removing a certain set of letters from the father's name and by removing a certain set of letters from the mother's name. For example, if the father's name is "abacaba" and the mother's name is — "bbccaa", then their child may be named "a", "bba", "bcaa", but cannot be named "aaa", "ab" or "bbc". It is possible for a child's name to be the same as the name of the father and/or mother if it can be derived from the other parent's name by removing a few (possibly none) of the letters.
 
Have a father named X and a mother named Y choose a name for their newborn child. Since in Taukitian schools, students are often called to the board in the lexicographic order of the names of the students, that is, in the order of the names in the dictionary, they want to choose a name for their child so that it follows lexicographically as late as possible.
 
- Formally, the string S is lexicographically greater than the string T if one of two conditions is true: the string T is obtained from S by removing one or more letters from the end of the string S;
- the first (i - 1) characters of strings T and S do not differ, and the letter in the i-th position of the string T follows in the alphabet before the letter in the i-th position of the string S.

It is required to write a program that, given the names of the father and mother, finds the lexicographically largest name for their child.
 
Input
The first line of the input file contains X — father's name. The second line of the input file contains Y — mother's name. Each name consists of lowercase Latin letters, includes at least one letter, and is no longer than 105 letters.
 
Output
The output file must contain the lexicographically largest possible child name you are looking for. If there is no suitable name for the child, the output file must be empty.
 
Input Output
abcabca
abcda
ca
ccba
accbaa
ccba