Talnalás

자전거 자물쇠, Photorama, Pixabay 제공

어린 Anna는 오늘 아침 자전거를 타고 학교에 갔다. Anna는 자전거 보관소에서 숫자 자물쇠로 자전거를 잠근 뒤 자물쇠의 숫자들을 뒤섞었다. 숫자 자물쇠는 각각 $0$부터 $9$까지의 숫자가 적힌 $n$개의 숫자판으로 이루어져 있으며, 숫자판은 양방향으로 돌릴 수 있다. 따라서 한 번 돌리면 숫자판을 이전 숫자보다 하나 작거나 하나 큰 숫자로 옮길 수 있다. 숫자판은 원형이므로 숫자 $9$을 증가시키면 다시 숫자 $0$로 돌아가고, 숫자 $0$을 감소시키면 다시 숫자 $9$로 돌아간다.

Anna는 이제 집에 가려 하므로 숫자 자물쇠를 열어야 한다. 이를 위해 매번 원하는 숫자판 하나를 한 번씩 돌려, 숫자판의 숫자들이 마침내 특정 숫자열을 이루게 한다. 하지만 Anna는 미신을 매우 잘 믿으며, 지금까지 $m$개의 행운의 숫자를 정해 두었다. Anna는 자신이 숫자판을 한 번 돌릴 때마다 숫자판들이 이루는 숫자열이 반드시 자신의 행운의 숫자 중 하나이기를 바란다. 그렇지 않으면 불운을 예고하기 때문이다.

자물쇠의 최초 숫자열, 자물쇠를 여는 데 필요한 숫자열, Anna의 모든 행운의 숫자 목록이 주어질 때, 숫자판을 한 번 돌릴 때마다 숫자판의 숫자들이 행운의 숫자를 이루도록 하면서 자물쇠를 여는 숫자열을 만들기 위해 숫자판들을 어떤 순서로 돌려야 하는지 찾아라. Anna는 서둘러 집에 가고 싶으므로 가능한 한 적은 횟수로 숫자판을 돌리려 한다.

채점

그룹 | 점수 | 제한

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$

첫째 줄에는 숫자 자물쇠의 숫자판 개수와 행운의 숫자 개수를 나타내는 두 정수 $n$와 $m$가 주어진다. ($1 \leq n$, $1 \leq m$) 둘째 줄에는 $n$자리 수가 주어지며, $i$번째 자릿수는 숫자 자물쇠의 최초 숫자열에서 $i$번째 숫자판의 숫자를 나타낸다. 셋째 줄에는 $n$자리 수가 주어지며, $i$번째 자릿수는 자물쇠를 여는 데 필요한 숫자열에서 $i$번째 숫자판의 숫자를 나타낸다. 마지막으로 $m$개의 줄이 이어지며, 각 줄에는 Anna의 행운의 숫자를 나타내는 $n$자리 수가 주어진다. 또한 최초 숫자열과 자물쇠를 여는 숫자열도 행운의 숫자이다.

최초 숫자열과 자물쇠를 여는 숫자열은 서로 다르다고 가정해도 된다.

첫째 줄에 Anna가 매번 움직인 뒤 자물쇠의 숫자열이 행운의 숫자를 이루도록 하면서 자물쇠를 여는 데 필요한 최소 움직임 횟수인 정수 $k$을 출력한다. 이어서 $k+1$개의 줄에 각각 $n$자리 수를 출력한다. 그중 첫 번째 수는 자물쇠의 최초 숫자열이며, 뒤따르는 $k$개의 수는 Anna가 숫자판을 한 번씩 돌린 뒤 자물쇠에 나타나는 숫자열을 순서대로 보여 준다. 따라서 마지막 숫자열은 Anna가 자물쇠를 여는 데 필요한 숫자열이어야 한다.

가능한 해가 여러 개라면 그중 어느 것을 출력해도 상관없다. 해가 존재하지 않으면 ```Neibb`''만 포함하는 한 줄을 출력한다.