Problem C
Garage Door Code
There have been an increasing number of laptop thefts in your area lately. After yours was recently stolen, too, you decided that you had enough and are going to do something about it! After asking around, you heard some rumors about where the stolen laptops have been hidden and you want to get your laptop back!
The rumors led you to a particular garage and you have decided to keep an eye on it to try to figure out how to get in. Over the course of the afternoon, you have seen a handful of people come, enter the garage, and then leave.
There’s a security keypad on the door. As you have watched carefully, you have observed different people putting in the code, but they enter different numbers of digits. You figure out that some, maybe all, of them are pretending to intersperse additional key presses just to confuse anyone who might be watching them. You look up the keypad manufacturer’s webpage and find that the keypad was designed to use codes with a predetermined length of $K$ digits. Given the set of observations you’ve made of different individuals “entering” elongated variations of the code (each does contain the correct code), can you determine what the correct code might be? It is guaranteed that there will always be at least one correct code that matches all observations. There may be multiple codes that match; you must find all matching codes.
Input
The first line of input contains two integers $K$ ($3 \leq K \leq 6$), the number of digits specified by the manufacturer for a correct code, and $N$ ($2 \leq N \leq 20$), the number of elongated entry code sequences that you observed.
Each of the next $N$ lines contains a string of at least $K$ and at most 12 digits (0-9). These are the elongated entry code sequences that you have observed.
Output
Determine all $K$-digit codes that match the full set of elongated observations.
On the first line, output $M$, the number of codes that match the set of elongated observations. Then output $M$ lines, each containing one of these matching codes, having sorted them in increasing lexicographic order.
| Sample Input 1 | Sample Output 1 |
|---|---|
4 3 21302749 5230248 21076724 |
1 2024 |
| Sample Input 2 | Sample Output 2 |
|---|---|
5 7 0812734225 162334559 7512334755 1002394561 9321423495 81237425 47126345119 |
1 12345 |
| Sample Input 3 | Sample Output 3 |
|---|---|
3 3 1234 012345 11223344 |
4 123 124 134 234 |
