Missing Letters

In the land of Bnicetotrees a serious effort is under way to minimize paper usage. All new documents are created and managed electronically. For convenience, old documents are scanned and passed through automatic character recognition (ACR) to convert them into proper electronic form; the paper is then recycled. Unfortunately the scanning process is not reliable. In particular, it cannot recognize some characters from old printing fonts. One day the result is even worse: besides dropping characters, the system also fails to notice the spaces between words. Before the failure was noticed, many documents had already been sent for recycling and pulped. Your task is to write a program that tries to recover the text of a document from the faulty ACR output.

Fortunately, samples of correctly recognized text using the same vocabulary are available, so the set of words that might appear in each document is known. The set of characters that may be missing is also known.

For example, suppose a correctly recognized sample text is here and there we find this or maybe that. An attempt is made to scan the sentence this and that, but the recognizer fails to see the word spaces and fails to see any of the letters a, b, c, or t. The surviving letters of the three words then run together into one corrupted string. Each of the three words of this and that appears in the sample text, and the goal is to reconstruct the original sentence from that corrupted string.

Sometimes there are not enough surviving letters to identify a word uniquely. For example, if a, i, and e are missing, then ship and shape both look like shp. Sometimes it is hard to decide where one word ends and the next begins. For example, if e and t are missing, the string applsar could be reconstructed as apple start or as applets are.

You are to write a program that finds a reconstruction for such misrecognized sentences. Ambiguity is resolved as follows. Every surviving letter must be used in the reconstruction. A reconstruction is scored like this: each word's score is the number of its surviving (non-missing) letters multiplied by the number of times that word appears in the sample text; the score of the whole reconstruction is the sum of its words' scores. Your program should find the reconstruction with the highest score. If more than one reconstruction achieves the same highest score, choose the one that comes first in alphabetical order. This scoring is meant to favor commonly used words. (Note that a space comes before any letter in alphabetical order.)

For example, suppose that in the sample text apple appears twice, start and applets each appear once, and are appears three times, and that the letters e and t are missing. Then apple start scores $4 \times 2 + 3 \times 1 = 11$ and applets are scores $5 \times 1 + 2 \times 3 = 11$. The tie is broken by alphabetical order, so apple start is the chosen reconstruction.

The input contains several reconstruction problems.

Each problem begins with one or more lines of sample text — the correctly recognized text for that problem. The sample text contains at most 10000 words in total. All words consist of lowercase letters only, and no word is longer than 14 characters. There is no punctuation, and words are separated by one or more spaces.

Next comes a line containing only the character #.

After that comes a line listing the omitted (missing) characters, followed by one or more lines containing the corrupted string to be reconstructed. Ignore the line breaks in the corrupted string and treat it as one continuous string; its total length is at most 10000 characters. Each problem ends with a line containing ##.

Some test problems use abstract strings rather than real English words, to test the algorithm thoroughly.

The whole input ends with one more line containing ##.

For each problem, output a line Problem #n, where n is the problem number starting from 1. Then output a line beginning with Reconstruction:, followed by the reconstructed text with a single space before each reconstructed word.