이름

아득히 먼 행성 타우 키타에는 지구인이 이해하기 어려운 풍습이 있다. 예를 들어 타우키타인은 자녀의 이름을 지구인과 아주 다르게 짓는다. 부모는 자녀의 이름이 아버지의 이름에서 몇 글자를 지워서도 얻을 수 있고 어머니의 이름에서 몇 글자를 지워서도 얻을 수 있도록 이름을 고른다. 예를 들어 아버지의 이름이 «abacaba»이고 어머니의 이름이 «bbccaa»라면 자녀는 «a», «bba», «bcaa»라는 이름을 가질 수 있지만 «aaa», «ab», «bbc»라는 이름은 가질 수 없다. 자녀의 이름이 아버지나 어머니의 이름과 같아도, 다른 부모의 이름에서 몇 글자(0글자일 수도 있다)를 지워 얻을 수 있다면 된다.

아버지의 이름이 X이고 어머니의 이름이 Y일 때 두 사람은 갓 태어난 자녀의 이름을 정하려 한다. 타우키타의 학교에서는 학생을 이름의 사전 순서로, 즉 사전에서 이름이 나오는 순서로 자주 불러 세우므로, 두 사람은 자녀의 이름이 사전에서 가능한 한 뒤에 오도록 이름을 정하려 한다.

형식적으로, 문자열 S가 문자열 T보다 사전에서 뒤에 온다는 것은 다음 두 조건 가운데 하나가 성립한다는 뜻이다.

• 문자열 T는 S의 끝에서 한 글자 이상을 지워 얻을 수 있다.
• T와 S의 처음 (i - 1)개 문자가 같고, T의 i번째 위치에 있는 글자가 S의 i번째 위치에 있는 글자보다 알파벳에서 앞선다.

아버지와 어머니의 이름이 주어질 때 자녀가 가질 수 있는 이름 가운데 사전에서 가장 뒤에 오는 이름을 찾는 프로그램을 작성해야 한다.

입력 파일의 첫째 줄에는 아버지의 이름 X가 들어 있다. 둘째 줄에는 어머니의 이름 Y가 들어 있다. 각 이름은 라틴 알파벳 소문자로 이루어져 있고, 글자가 적어도 하나 있으며, 길이는 105글자 이하다.

출력 파일에는 자녀가 가질 수 있는 이름 가운데 사전에서 가장 뒤에 오는 이름을 출력한다. 자녀의 이름으로 알맞은 것이 없으면 출력 파일은 비어 있어야 한다.

첫 번째 예에서 자녀의 이름은 c보다 뒤에 오는 글자로 시작할 수 없다. 아버지의 이름에 그런 글자가 없기 때문이다. 글자 c는 두 이름에 모두 들어 있으므로 자녀의 이름은 이 글자로 시작할 수 있다. 자녀의 이름에서 c 다음에 올 수 있는 글자는 a뿐이다.