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 ≤ *n* ≤ 15,
0 ≤ *f* ≤ *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.

Public test cases

**Input**

2 0 3 1 2 b 1 1 0 a 2 2 0 b 1 b 4 2 3 a 0 a

**Output**

ab ac ba bc ca cb -------------------- acb bab bcb cab -------------------- a -------------------- -------------------- abca acba --------------------

Information

- Author
- Salvador Roura
- Language
- English
- Translator
- Salvador Roura
- Original language
- Catalan
- Other languages
- Catalan
- Official solutions
- C++
- User solutions
- C++