Baltic Olympiad in Informatics: 2012 Day 2, Problem 2

Linas likes to play some musical instrument, and nobody knows what it is called. The instrument has ~S~ holes and Linas is able to play ~N~ different notes (numbered from ~1~ to ~N~) by covering each hole in one of ~10~ different ways (numbered from ~0~ to ~9~). Every note can be played by covering all holes in exactly one way, described by a sequence of digits corresponding to coverings of respective holes. If the holes are covered incorrectly (i.e., not corresponding to any note), the instrument starts to produce very unpleasant sounds, so Linas plays a wrong note rather than covers holes incorrectly.

Linas plays in a band where he has to play complicated tunes very quickly. Linas has written a tune (i.e., a sequence of numbers, corresponding to notes) and he wants to play it together with the band. Unfortunately, Linas doesn't play perfectly. He can only play two successive notes if by playing the second he has to cover no more than ~G~ holes differently than when playing the first one. Hence he decided to sometimes play a wrong note in the tune. Each incorrect note Linas plays is called mistake.

For a given tune find a modified tune that Linas can play making the least possible number of mistakes.

Constraints

~1 \le N \le 100~

~0 \le G < S \le 100~

~1 \le L \le 10^5~

In test cases worth ~40\%~ of points, ~1 \le L \le 100~.

In test cases worth ~65\%~ of points, ~1 \le L \le 5\,000~.

Input Specification

First line of input contains three space-separated integers: the number of possible notes ~N~, number of holes ~S~, and Linas' finger speed ~G~.

Next ~N~ lines contain the list of possible notes. There are ~S~ digits without spaces on each of them. The ~j^\text{th}~ digit in the ~i+1^\text{th}~ line corresponds to covering of the ~j^\text{th}~ hole required to play the ~i^\text{th}~ note (the hole can be covered in various ways, labelled by digits from ~0~ to ~9~). No two notes are played in the same way.

The ~N+2^\text{th}~ line contains the length of the tune ~L~.

The last line contains the tune: ~L~ space-separated integers, corresponding to the notes played successively in the tune.

Output Specification

The first line of output must contain one non-negative integer – the minimum number of mistakes.

The second line must contain a valid tune which obtains the minimum number of mistakes: ~L~ space-separated integers, corresponding to the notes that Linas should play. If there are multiple such tunes, output any of them.

Sample Input

5 4 2
1111
2101
2000
0100
0000
7
1 5 4 5 3 2 1

Sample Output

1
1 2 4 5 3 2 1

Sample Explanation

Linas can't play note ~5~ directly after note ~1~.