P7254 [BalticOI 2012] Melody (Day2)

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.

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.

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.

**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](http://www.boi2012.lv/data/day2/eng/melody.pdf). Translated by ChatGPT 5