#1807 Forgotten password

16  5 s   128 MB  

Description

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.

Input

Output

Sample Input

Sample Output

15 6
a??l?ban???????
apple
cow
farmer
banana
bananas
pies
applebananapies