As has happened to so many of us, Bessie has forgotten her cowtube password. She does, however, remember some handy bits of information about it.
First, she remembers that her password (denoted as variable P) has length L (1 <= L <= 1,000) roman characters and can be split into one or more words (not necessarily unique) from a dictionary composed of NW (1 <= NW <= 1,000) unique words.
A word W_i is defined as a sequence of 1..20 lowercase letters of the Roman alphabet ('a'..'z'). She also remembers certain letters from her password along with their positions.
Consider the following example.
Bessie knows that her password looks like "a??l?ban???????" ('?' represents a letter she cannot remember), and her dictionary has the following words:
The two possible passwords for Bessie to have are "applebananapies" and "applebananascow". Given the dictionary, and the letters that Bessie remembers, please find her password. If more than one password is valid, find the lexicographically least string that works.
15 6 a??l?ban??????? apple cow farmer banana bananas pies