새로운 과일

상근이는 두 과일의 유전자를 합쳐 새로운 과일을 만든다. 두 과일을 합치는 데 성공하면, 새로운 과일의 맛은 두 과일을 동시에 먹는 맛과 같다.

상근이는 작업을 시작하기 전에 새로운 과일의 이름부터 짓는다. 사과(apple)와 배(pear)를 합친 과일을 그냥 apple-pear라고 불러도 되지만, 이런 이름은 흥미를 끌지 못한다.

그래서 상근이는 두 과일의 이름을 각각 부분 수열(subsequence) 로 포함하는 문자열 중에서 길이가 가장 짧은 것을 새 과일의 이름으로 쓰려고 한다. 부분 수열이란 원래 순서를 유지하되 반드시 연속일 필요는 없는 문자들의 나열을 뜻한다. 예를 들어 applear는 apple(a, p, p, l, e)과 pear(p, e, a, r)를 모두 부분 수열로 포함하며, 그러한 문자열 중에서 길이가 가장 짧다.

두 과일의 이름이 주어졌을 때, 새 과일의 이름을 구하는 프로그램을 작성하시오.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스는 한 줄에 합치려는 두 과일의 이름이 공백으로 구분되어 주어진다. 각 이름은 알파벳 소문자로 이루어지며, 길이는 최대 100이다. 입력은 파일의 끝까지 계속된다.

각 테스트 케이스마다, 두 과일의 이름을 모두 부분 수열로 포함하는 가장 짧은 이름을 한 줄에 하나씩 출력한다. 그러한 이름이 여러 개이면 사전순으로 가장 앞서는 것을 출력한다.