prithivMLmods/Coder-Stat

1 2 3 4<h1><font color="#000000">Problem F:</font> Old Memories</h1>5<!-- end en only -->6 7 8<!-- begin en only -->9<p>10In 4272 A.D., Master of Programming Literature, Dr. Isaac Cornell Panther-Carol,11who has miraculously survived through the three World Computer Virus Wars and reached 90 years old this year,12won a Nobel Prize for Literature.13Media reported every detail of his life.14However, there was one thing they could not report &mdash; that is, an essay written by him when he was an elementary school boy.15Although he had a copy and was happy to let them see it, 16the biggest problem was that his copy of the essay was infected by a computer virus several times during the World Computer Virus War III17and therefore the computer virus could have altered the text.18</p>19<!-- end en only -->20 21<!-- begin en only -->22<p>23Further investigation showed that his copy was altered indeed. Why could we know that?24More than 80 years ago his classmates transferred the original essay to their brain before infection.25With the advent of Solid State Brain, one can now retain a text perfectly over centuries once it is transferred to his or her brain.26No one could remember the entire text due to the limited capacity,27but we managed to retrieve a part of the text from the brain of one of his classmates; sadly, it did not match perfectly to the copy at hand.28It would not have happened without virus infection.29</p>30<!-- end en only -->31 32<!-- begin en only -->33<p>34At the moment, what we know about the computer virus is that each time the virus infects an essay it does one of the following:35</p>36<ol>37 <li>the virus inserts one random character to a random position in the text. (e.g., "ABCD" &rarr; "ABCZD")</li>38 <li>the virus picks up one character in the text randomly, and then changes it into another character. (e.g., "ABCD" &rarr; "ABXD")</li>39 <li>the virus picks up one character in the text randomly, and then removes it from the text. (e.g., "ABCD" &rarr; "ACD")</li>40</ol>41<p>42You also know the maximum number of times the computer virus infected the copy, because you could deduce it from the amount of the intrusion log.43Fortunately, most of his classmates seemed to remember at least one part of the essay (we call it a <i>piece</i> hereafter).44Considering all evidences together, the original essay might be reconstructed.45You, as a journalist and computer scientist, would like to reconstruct the original essay by writing a computer program to calculate the possible original text(s) that fits to the given pieces and the altered copy at hand.46 47</p>48<!-- end en only -->49 50 51 52<h3>Input</h3>53 54 55<!-- begin en only -->56<p>57The input consists of multiple datasets. The number of datasets is no more than 100.58Each dataset is formatted as follows:59</p>60<blockquote>61<i>d n</i><br>62<i>the altered text</i><br>63<i>piece<sub>1</sub></i><br>64<i>piece<sub>2</sub></i><br>65<i>...</i><br>66<i>piece<sub>n</sub></i><br>67</blockquote>68<p>69The first line of a dataset contains two positive integers <i>d</i> (<i>d</i> &le; 2) and <i>n</i> (<i>n</i> &le; 30),70where <i>d</i> is the maximum number of times the virus infected the copy and <i>n</i> is the number of <i>pieces</i>.71</p><p>72The second line is the text of the altered copy at hand. We call it <i>the altered text</i> hereafter.73The length of the altered text is less than or equal to 40 characters.74</p><p>75The following <i>n</i> lines are <i>pieces</i>, each of which is a part of the original essay remembered by one of his classmates.76Each <i>piece</i> has at least 13 characters but no more than 20 characters. All pieces are of the same length.77Characters in the altered text and <i>pieces</i> are uppercase letters (`A' to `Z') and a period (`.').78Since the language he used does not leave a space between words, no spaces appear in the text.79</p><p>80A line containing two zeros terminates the input.81</p>82<!-- end en only -->83<!-- begin en only -->84<p>85His classmates were so many that you can assume that any character that appears in the original essay is covered by at least one <i>piece</i>.86A <i>piece</i> might cover the original essay more than once; the original essay may contain repetitions.87Please note that some pieces may not appear in the original essay because some of his classmates might have mistaken to provide irrelevant pieces.88 89</p>90<!-- end en only -->91 92 93 94<h3>Output</h3>95 96<!-- begin en only -->97<p>98Below we explain what you should output for each dataset.99Suppose if there are <i>c</i> possibilities for the original essay that fit to the given pieces and the given altered text.100First, print a line containing <i>c</i>.101If <i>c</i> is less than or equal to 5, then print in lexicographical order <i>c</i> lines, each of which contains an individual possibility.102Note that, in lexicographical order, '.' comes before any other characters.103You can assume that <i>c</i> is always non-zero.104The output should not include any characters other than those mentioned above.105</p>106<!-- end en only -->107 108 109 110<h3>Sample Input</h3>111 112<pre>1131 4114AABBCCDDEEFFGGHHIJJKKLLMMNNOOPP115AABBCCDDEEFFGG116CCDDEEFFGGHHII117FFGGHHIIJJKKLL118JJKKLLMMNNOOPP1192 3120ABRACADABRA.ABBRACADABRA.121ABRACADABRA.A122.ABRACADABRA.123BRA.ABRACADAB1242 2125AAAAAAAAAAAAAAAA126AAAAAAAAAAAAA127AAAAAAAAAAAAA1282 3129XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX130XXXXXXAXXXXXX131XXXXXXBXXXXXX132XXXXXXXXXXXXX1330 0134</pre>135 136 137<h3>Output for the Sample Input</h3>138 139<pre>1401141AABBCCDDEEFFGGHHIIJJKKLLMMNNOOPP1425143.ABRACADABRA.ABRACADABRA.144ABRACADABRA.A.ABRACADABRA.145ABRACADABRA.AABRACADABRA.A146ABRACADABRA.ABRACADABRA.147ABRACADABRA.ABRACADABRA.A1485149AAAAAAAAAAAAAA150AAAAAAAAAAAAAAA151AAAAAAAAAAAAAAAA152AAAAAAAAAAAAAAAAA153AAAAAAAAAAAAAAAAAA154257155</pre>156 157 158 159 160