R - The Tables -- Version 2

Problem under revision. Check back soon...

Mr. and Mrs. Tables hold the occasional party, and they are rather strict about the sitting arrangements. They decide to jump on the automation band-wagon and hire you to write a program to figure out their sitting arrangements. Your job is to read their requirements on the sitting arrangements and see if particular arrangements conform to their requirements or not.

In their simple parties, guests sit from left to right, on one side of a straight table. Requirements are of the format . Each > is a letter of alphabet, capitalized, starting with A being the first guest. is a single character, one of '< ', '^', '$', or '>'.

A<B  if B is not at the left edge of the table, A must sit immediately to the left of B
A>B  if B is not at the right edge of the table, A must sit immediately to the right of B
^A A must sit at the left end of the table
A$ A must sit at the right end of the table

Each particular sitting arrangement is specified simply by listing the guests from left to right, e.g. ACDEF You may assume that every guest shows up at the party

Input: Your input will consist of several cases. Each case starts with two numbers n <= 26 and m. n is the number of guests present at the party, and m is the number of requirements the Tables have on the arrangements. This will be followed by m lines each specifying a requirement. A case with 0 guests and 0 requirements finishes the input.
Output:For each case, outputALLpossible arrangements that conform to the requirements. Each arrangement is to be printed on one line, by its own. Output a blank line between test cases.