分离单词

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

一个长度为L的双重线形的纵横字串是指由L个小写英文字母排列而成的字串。它至少有两种划分的方法(称为分离法)分解成一组单词的排列,这些单词应该与从给定的单词表中选出来相同。看图1所示的例子(L=17): 



 这些单词是从以下列表选出的:all,an,and,are,area,as,ask,at,data,last,or,read,real,task。

出现在第一种分离法的单词不能在第二种分离法中出现,反之亦然。并且,任何一个单词在任何一个分离法中不能重复出现。一个单词在一种分离法中结束的位置不能和某一个单词在另一种分离法中结束的位置相同(字串结尾的单词除外)。其中一种分离法可以只包含一个单词。

请你编写一个程序构造一个满足以上规则的长度为L的双重线形纵横字串,其组成的单词从一个给定的单词列表中选出。单词列表中的单词已按字典顺序排列好。

Input

输入数据的第一行是一个整数L(4<=L<=50),表示所求字串的长度。第二行是一个正整数N(N<=1000),表示列表中的单词个数。以下是N行长度从2到20的字串单词(由小写英文字母构成)。这些单词已按字典顺序排列好,且没有重复。

Output

对于输入的数据集,你的程序须输出任意一个给定长度的双重线形字串。若这种字串不存在,程序须输出一行信息“NO SOLUTION”。

Sample Input

17
14
all
an
and
are
area
as
ask
at
data
last
or
read
real
task

Sample Output

andatareallastask

Hint

Source