타협

몇 달 뒤면 유럽 통화 동맹(European Currency Union)이 현실이 됩니다. 하지만 이 동맹에 가입하려면 마스트리흐트 기준을 충족해야 하는데, 이는 여러 나라에게 (아마 룩셈부르크를 제외하면) 결코 간단한 일이 아닙니다. 독일이 이 기준을 반드시 충족하도록 만들기 위해 정부에게는 (세금 인상, 주식 매각, 금 보유고 재평가 등) 선택지가 너무 많아서, 무엇을 해야 할지 정하기가 정말 어렵습니다.

그래서 독일 정부는 다음 작업을 수행하는 프로그램을 필요로 합니다.

두 정치인이 각자 자신의 제안을 입력합니다. 그러면 컴퓨터는 두 제안 모두에 등장하는 단어들의 가장 긴 공통 부분 수열(longest common subsequence)을 출력합니다. 보다시피 이것은 완전히 공정한 타협입니다. 공통된 단어의 나열이란 결국 두 사람이 함께 염두에 둔 내용이기 때문입니다.

이 프로그램을 작성하세요.

입력은 여러 개의 테스트 케이스로 이루어집니다.

각 테스트 케이스는 두 개의 텍스트로 구성됩니다. 각 텍스트는 소문자 단어들의 나열이며, 단어는 공백(스페이스나 줄바꿈)으로 구분되고 문장 부호는 없습니다. 각 단어의 길이는 30자 미만입니다. 각 텍스트는 100개 미만의 단어를 포함하며, # 하나만 있는 줄로 끝납니다.

입력은 파일의 끝(EOF)에서 종료됩니다.

각 테스트 케이스마다 두 텍스트에 공통으로 나타나는 가장 긴 공통 부분 수열을 출력합니다. 그러한 수열이 여러 개이면, 사전순으로 가장 앞서는 것(단어를 앞에서부터 하나씩 비교했을 때 가장 작은 것)을 출력합니다. 단어들은 하나의 공백으로 구분하고, 마지막 단어 뒤에 줄바꿈 문자를 출력합니다. 공통 부분 수열이 비어 있으면 빈 줄을 출력합니다.