누락된 글자

Bnicetotrees 나라에서는 종이 사용을 줄이려는 노력이 한창이다. 모든 새 문서는 전자적으로 작성하고 관리한다. 오래된 문서는 편의를 위해 스캔한 뒤 자동 문자 인식(ACR)을 거쳐 올바른 전자 형식으로 변환하고, 종이는 재활용한다. 그런데 스캔 과정이 그다지 믿을 만하지 못하다. 특히 옛 인쇄 글꼴의 일부 글자를 인식하지 못한다. 어느 날은 결과가 더 나빠졌다. 글자를 빠뜨리는 것도 모자라 단어 사이의 공백까지 인식하지 못한 것이다. 문제를 알아차렸을 때는 이미 많은 문서가 재활용으로 넘어가 펄프가 된 뒤였다. 잘못된 ACR 출력으로부터 원래 문서의 텍스트를 복원하는 프로그램을 작성하라.

다행히 같은 어휘로 이루어진, 올바르게 인식된 예시 텍스트를 구할 수 있다. 따라서 각 문서에 나올 수 있는 단어의 집합은 알고 있다. 또한 빠질 수 있는 글자의 집합도 알고 있다.

예를 들어 올바르게 인식된 예시 텍스트가 here and there we find this or maybe that라고 하자. 문장 this and that을 스캔했는데 인식기가 단어 사이 공백을 보지 못하고 글자 a, b, c, t도 전혀 인식하지 못했다. 그러면 세 단어에서 살아남은 글자들이 하나의 손상된 문자열로 이어진다. this and that의 세 단어는 모두 예시 텍스트에 등장하며, 이 손상된 문자열로부터 원래 문장을 복원하는 것이 목표다.

살아남은 글자가 부족해서 단어를 유일하게 특정할 수 없을 때도 있다. 예를 들어 a, i, e가 빠지면 ship과 shape는 둘 다 shp로 보인다. 또 한 단어가 어디서 끝나고 다음 단어가 어디서 시작하는지 판단하기 어려울 때도 있다. 예를 들어 e와 t가 빠지면 문자열 applsar은 apple start로도, applets are로도 복원될 수 있다.

이렇게 잘못 인식된 문장의 복원을 찾는 프로그램을 작성하라. 모호함은 다음 규칙으로 해결한다. 살아남은 모든 글자는 복원 결과에 반드시 사용되어야 한다. 복원 결과의 점수는 다음과 같이 매긴다. 각 단어의 점수는 그 단어에서 살아남은(빠지지 않은) 글자 수에 그 단어가 예시 텍스트에 등장한 횟수를 곱한 값이다. 복원 결과 전체의 점수는 각 단어 점수의 합이다. 프로그램은 점수가 가장 높은 복원 결과를 찾아야 한다. 최고 점수가 같은 복원 결과가 여럿이면 사전순으로 가장 앞선 것을 고른다. 이 점수 방식은 자주 쓰이는 단어를 선호하기 위한 것이다. (사전순에서 공백은 어떤 글자보다도 앞선다는 점에 유의하라.)

예를 들어 예시 텍스트에서 apple이 두 번, start와 applets가 각각 한 번, are가 세 번 등장하고 글자 e와 t가 빠졌다고 하자. 그러면 apple start의 점수는 $4 \times 2 + 3 \times 1 = 11$ 이고 applets are의 점수는 $5 \times 1 + 2 \times 3 = 11$ 이다. 동점은 사전순으로 해결하므로 선택되는 복원 결과는 apple start이다.

입력에는 여러 개의 복원 문제가 들어 있다.

각 문제는 한 줄 이상의 예시 텍스트로 시작한다. 이는 해당 문제에서 올바르게 인식된 텍스트이다. 예시 텍스트에는 단어가 모두 합쳐 최대 10000개 들어 있다. 모든 단어는 소문자로만 이루어지며, 길이가 14를 넘는 단어는 없다. 문장 부호는 없고, 단어는 하나 이상의 공백으로 구분된다.

그다음 줄에는 문자 # 하나만 있다.

이어서 빠진(누락된) 글자들을 나열한 줄이 오고, 그 뒤에 복원할 손상된 문자열이 한 줄 이상 온다. 손상된 문자열의 줄바꿈은 무시하고 하나의 연속된 문자열로 취급한다. 그 전체 길이는 최대 10000자이다. 각 문제는 ##만 있는 줄로 끝난다.

일부 테스트 문제는 알고리즘을 철저히 검증하기 위해 실제 영어 단어가 아닌 추상적인 문자열을 사용한다.

입력 전체는 ##만 있는 줄 하나로 한 번 더 끝맺는다.