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

Задача 34823. Names in Tau Ceti


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 are indistinguishable, and the letter in the i-th position of the string T follows the letter in the i-th position of the string S in the alphabet.

You need 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 letters of the Latin alphabet, includes at least one letter and has a length of no more than 105 letters.

Output

The output file must contain the lexicographically largest possible child name you are looking for. In case there is no suitable name for the child, the output file should be empty.

Examples
input
abcabca
abcda
output
ca

input
ccba
accbbaa
output
ccba