Old Memories

In 4272 A.D., Dr. Isaac Cornell Panther-Carol, a master of programming literature who miraculously survived the three World Computer Virus Wars and turned 90 this year, won the Nobel Prize in Literature. The media reported every detail of his life. There was, however, one thing they could not report: an essay he wrote as an elementary-school boy. He kept a copy and was happy to share it, but there was a catch — his copy had been infected by computer viruses several times during World Computer Virus War III, so the viruses may have altered its text.

Further investigation confirmed that the copy had indeed been altered. How could we tell? More than 80 years ago, before the infections, his classmates transferred the original essay into their brains. With the advent of the Solid State Brain, a text transferred into a brain is now preserved perfectly for centuries. No one could recall the entire text because of capacity limits, but we managed to recover a portion of it from one classmate's brain — and, sadly, it did not match the copy at hand. That could not have happened without the virus infections.

What we currently know about the virus is that each time it infects an essay it performs exactly one of the following:

1. It inserts one random character at a random position. (e.g., "ABCD" → "ABCZD")
2. It picks one random character and changes it into another character. (e.g., "ABCD" → "ABXD")
3. It picks one random character and removes it. (e.g., "ABCD" → "ACD")

You also know the maximum number of times the virus infected the copy, deduced from the amount of the intrusion log. Fortunately, most classmates remembered at least one part of the essay (called a piece hereafter). Taking all the evidence together, the original essay might be reconstructable. As a journalist and computer scientist, you want to reconstruct it by writing a program that computes every possible original text consistent with the given pieces and the altered copy at hand.

The input consists of several datasets. The number of datasets is at most 100. Each dataset has the following format:

• The first line contains two integers $d$ and $n$ ($1 \le d \le 2$, $1 \le n \le 30$), where $d$ is the maximum number of times the virus infected the copy and $n$ is the number of pieces.
• The second line is the text of the altered copy at hand (the altered text). Its length is at most 40 characters.
• Each of the following $n$ lines is a piece: a part of the original essay remembered by one classmate. Every piece has at least 13 and at most 20 characters, and all pieces have the same length.

Every character in the altered text and in the pieces is an uppercase letter ('A'–'Z') or a period ('.'). The language he used leaves no space between words, so no spaces appear.

A line containing 0 0 terminates the input.

Because he had so many classmates, you may assume that every character appearing in the original essay is covered by at least one piece. A piece may cover the original essay more than once, and the original essay may contain repetitions. Note that some pieces may not appear in the original essay at all, because some classmates might have mistakenly supplied irrelevant pieces.

For each dataset, output the following.

Let $c$ be the number of candidate original essays. A string $S$ is a candidate if and only if it satisfies both conditions below:

• The altered text can be produced from $S$ by applying at most $d$ infections (insertion, substitution, deletion); equivalently, the edit distance between $S$ and the altered text is at most $d$.
• Every position of $S$ is covered by at least one piece, where a position is covered when some piece occurs as a contiguous substring of $S$ that includes that position.

First print $c$ on its own line. If $c \le 5$, then print the candidates in lexicographical order, one per line, over $c$ lines. In lexicographical order the period ('.') precedes every other character. It is guaranteed that $c \ge 1$. The output must not contain any character other than those mentioned above.