Forgotten Password

Bessie has forgotten her password, but she still remembers a few useful facts about it.

Her password $P$ is a string of $L$ lowercase Roman letters ($1 \le L \le 1000$). It can be split into one or more words (not necessarily distinct) taken from a dictionary of $NW$ distinct words ($1 \le NW \le 1000$); the same word may be used more than once. Each dictionary word is a sequence of $1$ to $20$ lowercase letters ('a'..'z').

Bessie also remembers some of the letters of her password together with their positions. This partial knowledge is given as a string of length $L$: each position holds either the exact letter she remembers, or the character ? if she cannot remember it.

Given the dictionary and Bessie's partial memory, reconstruct a password that

• has exactly the remembered letters at their positions (a ? may be any lowercase letter), and
• is a concatenation of one or more dictionary words.

If more than one password satisfies both conditions, output the lexicographically smallest one. It is guaranteed that at least one valid password exists.

• Line 1: two space-separated integers $L$ and $NW$.
• Line 2: a string of length $L$ describing Bessie's partial memory: lowercase letters for remembered positions and ? for forgotten ones.
• Lines 3 to $NW+2$: line $i+2$ contains the $i$-th dictionary word $W_i$.

• A single line: the lexicographically smallest password that matches the partial memory and is a concatenation of dictionary words.