Description

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.

Input Format

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 Format

Output exactly one line: Bessie’s password.

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

applebananapies 

Hint

Translated by ChatGPT 5