신중한 성명

“당황하지 마세요!”는 어느 유명한 책 표지에 적힌 문구일 뿐 아니라, 모든 은행이 아무리 사소한 위기 상황에서도 고객에게 전해야 하는 메시지이기도 합니다. 고객이 동요하기 시작하면 그 은행은 끝장날 수 있습니다.

고객을 안심시키기 위해 은행과 정부는 걱정할 것이 전혀 없다는 여러 성명을 발표하기도 합니다. 사람들이 그 말을 믿게 하려면 이런 성명들이 서로 모순되지 않아야 합니다.

이제 은행이 제안한 성명과 정부가 내놓은 성명, 두 개의 성명이 있다고 합시다. 두 기관은 이 둘을 하나의 공동 성명으로 합쳐 함께 발표하기로 했습니다. (성명이 너무 많으면 오히려 문제가 있다고 여겨질 수 있으니까요.) 은행과 정부 모두 공동 성명이 자신들의 원래 성명 전체를 담고 있어야 한다고 주장합니다.

여러분의 임무는 오늘 밤 기자회견에서 발표할 공동 성명을 만드는 것입니다. 결과물은 두 원래 성명의 모든 단어를 원래 순서대로 포함해야 하며, 가능한 한 짧아야 합니다.

입력은 여러 개의 테스트 케이스로 이루어집니다. 각 테스트 케이스는 두 줄로 되어 있으며, 두 개의 원래 성명을 나타냅니다. 각 줄에는 공백으로 구분된 단어가 최소 $1$개, 최대 $2000$개 있습니다. 각 단어는 영어 소문자(a–z)로만 이루어지며, 길이는 최소 $1$자, 최대 $10$자입니다. 각 성명의 마지막 단어 뒤에는 하나의 마침표(.)가 있으며, 그 앞에는 공백이 하나 있습니다.

마지막 테스트 케이스 다음에는 마침표(.) 하나만 있는 줄이 옵니다.

각 테스트 케이스마다, 공백으로 구분된 단어들의 나열을 한 줄로 출력합니다. 이 나열은 다음 조건을 만족해야 합니다.

1. 두 입력 성명이 모두 출력의 부분 수열이어야 합니다. 즉, 각 원래 성명의 모든 단어가 원래 순서대로 결과에 나타나야 하며, 두 성명은 서로 섞여 있어도 됩니다.
2. 조건 1을 만족하는 모든 텍스트 중에서, 출력은 단어 수가 가장 적어야 합니다.
3. 그런 최소 길이의 텍스트가 여러 개라면, 사전순으로 가장 앞서는 것을 출력합니다.

마지막 단어 뒤에는 공백 하나와 마침표(.) 하나를 출력합니다.

텍스트 A가 텍스트 B보다 사전순으로 앞선다는 것은 사전에서 먼저 나온다는 뜻입니다. 더 정확히는, 두 텍스트가 처음으로 달라지는 위치에서 A의 단어가 B의 단어보다 사전순으로 앞선다는 것입니다.

마찬가지로 단어 C가 단어 D보다 사전순으로 앞선다는 것은, (a) 두 단어가 처음으로 달라지는 글자에서 C의 글자가 알파벳상 더 앞서거나, (b) C가 더 짧으면서 D의 접두사인 경우를 말합니다.