Hide

Problem H
Talnalás

/problems/talnalas/file/statement/en/img-0001.jpg
Bicycle lock by Photorama, Pixabay
Anna biked to school this morning. She locked her bike in the bike storage using a combination lock and then scrambled the digits on the lock. The lock is made up of $n$ disks that have the digits $0$ through $9$ written on them. The disks can be rotated in either direction. With one move, a disk can be rotated such that the selected number on it increases or decreases by one. The disk is cyclical so if you increase $9$ you get $0$ and if you decrease $0$ you get $9$.

Anna is now heading home and has to open the combination lock. She does this by rotating the disks, each one step at a time, such that the selected digits end up being a specific passcode. But Anna is very superstitious and has $m$ lucky numbers. After each step she wants to make sure the currently selected number is a lucky number, because otherwise it brings bad luck.

Given the currently selected digits, the passcode for the lock and the list of Anna’s lucky numbers, help her find in what order she should rotate the disks to open the lock, making sure that the digits displayed are always a lucky number after each step. Since Anna is in a rush, she wants to do this in the minimum number of steps possible.

Input

The first line of the input contains two integers $n$ and $m$ ($1 \leq n, m$), the number of disks on the lock and the number of lucky numbers. The second line of the input contains an $n$-digit number, where the $i$-th digit denotes the currently selected digit on the $i$-th disk of the combination lock. The third line of the input contains an $n$-digit number where the $i$-th digit is the digit that needs to be selected on the $i$-th disk to open the lock. Finally there are $m$ lines, each with an $n$-digit number which are Anna’s lucky numbers. The initial state and the passcode are both guaranteed to be lucky numbers.

You can assume that the initial state and the passcode are different.

Output

Print a single line containing the integer $k$, the minimum number of steps Anna needs to open the lock given the constraints above. Then print $k+1$ lines, each with an $n$-digit numbers, where the first contains the initial state of the lock and the following $k$ lines show the selected digits on the lock after each step in your solution. The final number must then be the passcode of the lock.

If there are multiple solutions, you can print any one of them. If there is no solution just print a single line containing “Neibb”.

Scoring

Group

Points

Constraints

1

9

$n = 1$, $m \leq 10$

2

14

$n = 2$, $m \leq 100$

3

17

$n = 3$, $m \leq 10^3$

4

20

$n = 5$, $m \leq 10^5$

5

12

$n = 50$, $m \leq 10$

6

10

$n = 50$, $m \leq 20$

7

18

$n = 50$, $n\cdot m \leq 10^5$

Sample Input 1 Sample Output 1
4 5
1234
1337
1236
2234
1336
1235
0234
4
1234
1235
1236
1336
1337
Sample Input 2 Sample Output 2
1 8
2
8
1
9
6
4
5
3
0
7
4
2
1
0
9
8
Sample Input 3 Sample Output 3
8 4
85362837
63812736
13248765
89816432
85362838
81234876
Neibb

Please log in to submit a solution to this problem

Log in