Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
北京大学《ACM-ICPC竞赛训练》暑期课面向全球招生。容量有限,报名从速!
Language:
Crossword
Time Limit: 5000MSMemory Limit: 10000K
Total Submissions: 914Accepted: 282

Description

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:

  • If the first letter of a string appears in latin alphabet before the first letter of another string, then the former string precedes in lexicographic order.
  • If the first letters of some strings match, then the corresponding letters of these strings are compared until they stop matching.
  • If a mismatching is not found, the shorter string goes first.

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

Sample Output

andatareadofortor

Source

[Submit]   [Go Back]   [Status]   [Discuss]

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator