You are given two strings a and b. You have to remove the minimum possible number of consecutive (standing one after another) characters from string b in such a way that it becomes a submultiset of string a. It can happen that you will not need to remove any characters at all, or maybe you will have to remove all of the characters from b and make it empty.

Input

The first line contains string a, and the second line contains string b. Both of these strings are non-empty and consist of lowercase letters of English alphabet. The length of each string is no bigger than 10⁵ characters.

Output

On the first line output a submultiset of string a in sorted order, obtained from b. If multiple answers exist, output lexicographically smallest.

If the answer consists of zero characters, output "-" (a minus sign).

Example

Input:
abacaba
abcdcba
Output:
aabbc

Input:
abcdy
abdxybc

Output:
abcd

Note: ouput is abcd not abcy since abcd is lexicographically smaller.