A locked spinner puzzle is a puzzle where you can only change wheels in groups. It is a common puzzle to achieve some value on the spinners by only changing them in the allowed groups.
Assume a row of D numbered wheels, such as what is found on a combination lock on a briefcase.
Each wheel will be labeled sequentially with the digits 0 through 9. And there are a series of buttons with labels that are D digits long. For example, D may be 4 and the labels are 1000 1200 1002 0111 and 0100. Pressing the button labeled 1000 moves the first wheel once, but leaves the others alone, while pressing the button labeled 1002 moves the first wheel once and the fourth wheel twice, leaving the center buttons unchanged. Given the initial state and final state of the wheels, you are to provide a combination of pressing to transform from the initial state to the final state with minimum number of pressing to open the lock.
Input
The input to your program will be several spinner puzzles. Each puzzle begins with a line containing two integers D (1 <= D <= 6) the number of wheels, and N (1 <= N <= min(100, 10^D) ) the number of buttons. The next N lines will each gives a button with D digits label. Last line contains two labels which are the initial state and the final state, respectively.
Output
For each puzzle, print the minimum number of pressing to open the lock in the first line. Then print the labels pressed in lexicographic order, each in one line. If there are several ways to do with the minimum number of pressing, make the concatenation of the labels pressed lexicographic minimum (see hint for detail). Print "-1" in a line if can't open the lock.
Sample Input
3 3
100
010
001
000 111
4 3
0200
0300
0400
0400 0000
2 1
99
00 01
Sample Output
3
001
010
100
2
0200
0400
-1
