Description

There is a little-known musical instrument. It has $S$ holes, and by covering these holes in ten different ways $(0$ to $9)$, it can produce $N$ notes. You are not allowed to use any hole-covering pattern other than those for these $N$ notes.

Now you want to play a piece of music, but because this instrument requires that between any two consecutive notes, the hole-covering patterns differ in at most $G$ holes, you may have to play some notes incorrectly. You want to minimize the number of notes you play incorrectly.

Input Format

The first line contains three integers $N, S, G\ (0 \le G < S \le 100)$, as described above.

The next $N$ lines each contain a string of length $S$ (digits only), representing the hole-covering pattern when playing that note.

The next line contains an integer $L$, the number of notes in the piece.

The last line contains $L$ integers, representing the indices of the notes in the piece.

Output Format

The first line contains one integer, the minimum possible number of notes that you play incorrectly.

The next line contains $L$ integers, representing any one valid construction of your playing plan.

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

1
1 2 4 5 3 2 1

Hint

Sample Explanation

Note $1$ and note $5$ have different playing patterns on all four holes, so you cannot play note $5$ right after playing note $1$.

Constraints

• For $40\%$ of the testdata, $L \leq 100$.
• For $65\%$ of the testdata, $L \leq 5000$.
• For $100\%$ of the testdata, $1 \leq N \leq 100$, $1 \le L \le 10 ^ 5$.

Notes

Translated from BalticOI 2012 Day2 T2. Melody.

Translated by ChatGPT 5