22857_CowSigns

Farmer John decided to make the most out of his highwayside farm and sell advertising.  He found a client and hiked to his fence which runs along the highway and painted the message on the sides of the cows grazing along the fence.  He painted exactly K letters (2 ≤ K ≤ 4) on each of C (2 ≤ C ≤ 20) cows and ignored spaces.

Although cows are fairly lazy creatures, they are not immobile.  After milking the next morning, FJ noticed that the message he was being paid to display was now in pieces in his barn.  Worse still, FJ also forgot the original message.

Help FJ reconstruct the original message.  Given K, the cows' letter groupings (which all happen to be unique), and a dictionary that contains all the possible words, figure out all the possible messages (note that the message ABCD EF is different from AB CDEF).  Each dictionary word is unique and can be used more than once in any given message.  All C cows are used exactly once.  Being advertising, it is important to ignore grammar and any possible meaning of the message.

It is guaranteed that the number of possible original messages will not exceed 2,000,000,000.  Furthermore, all data in this problem is supplied in upper-case.

* Line 1: Three integers, K, C, and D (1 ≤ D ≤ 150, the number of words in the dictionary)

* Lines 2..C+1: Each line contains K letters of the scrambled message

* Lines C+2..C+D+1: Each line contains a single word from a dictionary; no word is longer than ten characters

* Line 1: The first (in alphabetical order) possible message.  Note that "A B" preces "AB" alphabetically.

* Line 2: A single integer which is the number of possible messages

If no solutions exist, print a single line containing the word "NOSOLUTIONS".

3 5 7
TEN
ATT
NAT
BAR
ACK
AT
ATTACK
BARN
CHICKENS
CHOPPERS
COWS
TEN

ATTACK BARN AT TEN
6

in case you were wondering, here are the six:  TEN ATTACK BARN AT, TEN BARN AT ATTACK, ATTACK TEN BARN AT, ATTACK BARN AT TEN, BARN AT TEN ATTACK, and BARN AT ATTACK TEN