Names
On the distant planet Tau Ceti, the customs are quite different from ours. For instance, Tau Cetians have a unique method for naming their children. A child's name is chosen such that it can be formed by removing certain letters from both the father's and the mother's names. For example, if the father's name is "abacaba" and the mother's name is "bbccaa", possible names for their child include "a", "bba", and "bcaa". However, names like "aaa", "ab", or "bbc" are not possible. The child's name can be identical to either parent's name if it can be derived from the other parent's name by removing some letters.
Let the father, named X, and the mother, named Y, decide on a name for their newborn. Since in Tau Cetian schools, students are often called to the board in lexicographical order, like in a dictionary, they wish to choose a name for their child that is as late as possible lexicographically.
Formally, a string S is considered lexicographically greater than a string T if one of the following conditions is true:
The string T can be obtained from S by removing one or more letters from the end of S;
The first (i - 1) characters of both strings T and S are identical, and the i-th character of T precedes the i-th character of S in the alphabet.
Your task is to write a program that determines the lexicographically largest possible name for the child, given the father's and mother's names.
Input
The first line of the input contains X — the father's name. The second line contains Y — the mother's name. Each name is composed of lowercase Latin letters, contains at least one letter, and is no longer than 10^5 characters.
Output
The output should be the lexicographically largest possible name for the child. If no suitable name exists, the output should be empty.
Explanation of the example
In the first example, the child's name cannot start with a letter greater than c, as the father's name does not contain such letters. The letter c is present in both names, so the child's name can start with this letter. The only letter that can follow c in the child's name is a.