Words with a, b and c (1) P87741

In this problem we consider words of size $n$ made up only of letters ‘a’, ‘b’ and ‘c’, and without two or more consecutive equal letters. Suppose that some positions of the word have fixed letters. Write a program to print all the words that meet these constraints.

Input

Input consists of several cases. Every case starts with $n$, followed by the number of fixed positions $f$, followed by $f$ pairs $p_i$ $c_i$, where $p_i$ is a position between 0 and $n - 1$ and $c_i$ is ‘a’, ‘b’ or ‘c’. Suppose $1 \le n \le 15$, $0 \le f \le n$, and that all $p_i$’s are different.

Output

For every case, print in alphabetical order all words that satisfy the constraints. Print a line with 20 dashes at the end of each case.