0149 - 古い記憶

西暦4272年，プログラミング文学の巨匠，アイザック・コーネル・パンサーキャロル博士は
三度の世界コンピューターウイルス大戦を奇跡的に生き残り，
今年で丁度90歳になったところでノーベル文学賞を受賞した．
メディアは彼の一生を細大漏らさず報道したが，一つだけ報道できなかったことがあった——それは彼がまだ小学生の頃に書いた作文だった．
彼は作文を保管しておいたので，それを報道陣に見せることを快諾したのだが，
最大の問題は，第三次世界コンピューターウイルス大戦の際に保管していた媒体が
コンピューターウイルスに何回か感染していたので，文章が改ざんされているかもしれない点だ．

更に調査を進めたところ，保管していた作文はやはり改ざんされていることが分かった．なぜ分かったのか？
80年以上前に，彼のクラスメートは感染する前に元の作文を脳に転送していたのだ．
半導体脳の発明により，人は脳に転送した文章を何世紀にもわたって完全に保持することができる．
容量が限られているため，文章全体を覚えている人はいなかったが，
我々はなんとかして文章の一部をクラスメートの一人の脳から引き出した．悲しいことに，それは手元に保管していた作文と完全には一致していなかった．
これはウイルス感染が無ければありえないことだ．

現在，そのコンピューターウイルスについて分かっていることは，ウイルスが作文に感染するたびに以下のうちどれか一つを行うことである．

1. ウイルスはランダムな文字を文章中のランダムな位置に挿入する．（例："ABCD" → "ABCZD"）
2. ウイルスは文章中の文字を1文字ランダムに選び，その文字を別の文字に変換する．（例："ABCD" → "ABXD"）
3. ウイルスは文章中の文字を1文字ランダムに選び，その文字を文章中から取り除く．（例："ABCD" → "ACD"）

また，侵入ログの量から推定することでウイルス感染が起こりえた回数の最大値も貴方は知っている．
幸運なことに，彼のクラスメートのほとんどは彼の作文の少なくとも一部（以降ピースと呼ぶ）を覚えていてくれたようなのだ．
全ての証拠を総合すれば，元の作文を復元できるかもしれない．
貴方はジャーナリスト兼コンピュータ科学者として，元の作文に書かれていた文章としてどのようなものがあり得るのか，与えられたピースや改ざんされてしまった手元の文章を元に計算するコンピュータープログラムを書きたい．

入力は複数のデータセットからなる．データセット数は100以下である．
データセットは以下の形式をしている．

d n

改ざん文章

ピース₁

ピース₂

...

ピース_n

データセットの1行目は二つの正の整数 d (d ≤ 2) と n (n ≤ 30) からなり，
dは作文にウイルスが感染した回数の最大値を，nはピースの数を表している．

データセットの2行目は，手元にある改ざんされた文章である．以降これを「改ざん文章」と呼ぶ．
改ざん文章の長さは40文字以下である．

データセット中の残りの行はピースと呼ばれ，彼のクラスメートが覚えていた元の作文の一部である．
各々のピースは20文字以下で，最低13文字ある．ピースは全て同じ長さである．
改ざん文章やピースに現れる文字は，英語アルファベット大文字（`A'から`Z'）とピリオド（`.'）である．
彼が用いていた言語は分かち書きをしないので，ピースや改ざん文章中に空白文字は現れない．

二つのゼロのみを含む行が入力の終わりを表す．

クラスメートは充分にたくさんいたので，元の作文中にあるどの文字も必ず最低一つのピースでカバーされていると仮定してよい．
一つのピースが元の作文を2回以上カバーすることがある．元の作文には繰り返しがあるかもしれない．
また，彼のクラスメートは勘違いをして関係ないピースを提出したかもしれないので，幾つかのピースは元の作文中に現れないかもしれないことに注意せよ．

各データセットに対して何を出力すれば良いかを以下に説明する．
与えられたピースや改ざん文書と合う元の作文が c 種類有り得るとする．
最初に c を含む1行を出力せよ．
もしcが5以下の場合には，さらに辞書順で1行に一つずつそれらの可能性を表示せよ．
辞書順では '.' が他のどの文字よりも早いことに注意せよ．
cは0でないことを仮定して良い．
上記で指示されていないいかなる文字も出力してはならない．

1 4
AABBCCDDEEFFGGHHIJJKKLLMMNNOOPP
AABBCCDDEEFFGG
CCDDEEFFGGHHII
FFGGHHIIJJKKLL
JJKKLLMMNNOOPP
2 3
ABRACADABRA.ABBRACADABRA.
ABRACADABRA.A
.ABRACADABRA.
BRA.ABRACADAB
2 2
AAAAAAAAAAAAAAAA
AAAAAAAAAAAAA
AAAAAAAAAAAAA
2 3
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXAXXXXXX
XXXXXXBXXXXXX
XXXXXXXXXXXXX
0 0

1
AABBCCDDEEFFGGHHIIJJKKLLMMNNOOPP
5
.ABRACADABRA.ABRACADABRA.
ABRACADABRA.A.ABRACADABRA.
ABRACADABRA.AABRACADABRA.A
ABRACADABRA.ABRACADABRA.
ABRACADABRA.ABRACADABRA.A
5
AAAAAAAAAAAAAA
AAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAA
257