P3025 [USACO11OPEN] Forgotten Password S

As often happens to us, Bessie has once again forgotten her barn manager password. She can only remember part of it. First, she remembers that the password $P$ is a string of length $L$ ($1 \le L \le 1000$), and that the password is formed by concatenating one or more words, each of which is recorded in her dictionary of $NW$ ($1 \le NW \le 1000$) words. Every dictionary word $W_i$ consists of $1$ to $20$ lowercase Latin letters. She only remembers some letters in the password and their positions. For example, Bessie remembers her password as `a??l?ban???????`, where `?` stands for a letter she forgot. Her dictionary contains these words: `apple cow farmer banana bananas pies`. Therefore, two possible passwords for Bessie are `applebananapies` and `applebananascow`. Now, given the letters Bessie still remembers and her dictionary, find a possible password. If there are multiple answers, output the lexicographically smallest one.

The first line contains the length $L$ of her password and the number of words $NW$ in the dictionary, separated by a space. The second line contains the string $P$ of length $L$. Then follow $NW$ lines, each containing a string $W_i$.

Output exactly one line: Bessie’s password.

Translated by ChatGPT 5