Common Permutation

Given two lowercase strings a and b, find the longest string x such that x can be formed by rearranging a subsequence of a and also by rearranging a subsequence of b.

The input contains multiple test cases until end of file. Each test case consists of two lines.

The first line contains string a, and the second line contains string b.

Each string has at most 1000 lowercase English letters.

For each test case, print x on one line.

If there are several longest possible strings x, print the lexicographically smallest one. If no character can be chosen in common, print an empty line.