Problem A
References
Problem B
Sum of powers
Problem C
Game
Problem D
Crossword
Problem E
Magic of David Copperfield
Problem F
Puncher
Problem G
Flying Stars
Problem H
Divide et unita

Problem D
Crossword
Input file INPUT.TXT
Output file OUTPUT.TXT
Time-limit/Test 20 seconds
A double linear crossword of length L is a string of L lowercase alphabetic characters arranged in a line in such a way that there are at least two methods (so called decompositions) to split this string into the words from the given list. Look at the example for L=17:
   |       |       |       |
a n d a t a r e a l l a s t a s k
     |   |     |     |   |
The words were taken from the following list: all, an, and, are, area, as, ask, at, data, last, or, read, real, task.

The words from the first decomposition may not appear in the second one and vice versa. In addition, no word can be repeated in any decomposition.

No word in one decomposition can end in the same place of the string where a word in the other composition ends, except, naturally, for the end of the string (otherwise the crossword can be separated into two independent crosswords). One of the compositions may consist of a single word.

You should write a program to construct the first, in lexicographic order, double linear crossword of length L for a given list of words.

Strings are arranged in the lexicographic order with respect of the following rules:

Input

The first line of the input file consists of the single integer number L (4<=L<=50) denoting the desired crossword length. The second line consists of the single positive integer N (at most 1000) indicating the number of words in the list. Each of the followings N lines consists of a string of 20 or less (but at least 2) latin lowercase alphabetic characters. The words in the list are arranged in lexicographic order and no word is repeated.

Output

For the given input data set your program should write to the output file the first, in lexicographic order, double linear crossword with the given length. If it is impossible for the given input file to construct a double linear crossword with the given length, the program should write only the message "NO SOLUTION" (without the quotation marks).

Sample input

17
19
all
an
and
area
as
ask
at
data
do
for
last
of
or
ort
read
real
task
to
tor
Output for the sample input
andatareadofortor