Hide

Problem F
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

Please log in to submit a solution to this problem

Log in