有一種新的樂器，它總共有 S 個音孔，而且每一個音孔都恰好有十種不同的調整方式，不妨標記為 '0', '1', ..., '9'。吹奏出某一個音符的方法，就是透過變換所有音孔的調整方式，使得該樂器能夠吹奏出特定的音符。總共有 N 種音符。
除了這 N 種音符的音孔調整組合以外，其他音孔的調整方式都會導致樂器發出非常可怕的聲音，因此我們應極力避免調整出其它的組合。
現在我們想要吹奏出一首很困難的歌曲，它依序包含了 L 個音符。因為手指在調整的時候沒辦法動作這麼快，吹奏出相鄰的兩個音之間僅能有至多 G 個音孔的調整方式不同。
為了避免發出噪音，而手指的速度又沒辦法跟上的時候，有時候我們必須被迫彈奏出其他音符，這時候被稱為一次「誤彈」。
請問在最佳情形下，至少得「誤彈」幾次，才能夠將整首歌曲吹奏完畢呢？請你也順便找出一組吹奏的方式吧。
Warn: 本題有 specialjudge
一個輸入檔可能包含多筆測試資料，以EOF結束。
對於每一筆測試資料，第一行有三個整數 N(1<=N<=100), S, G (0<=G<S<=100)。接下來的 N 行依序有一個長度為 S 的數字字串，用以表示每一種音符的吹奏方式。
接下來有一個正整數 L，然後有 L 個介於 1 到 N 之間(包含)的正整數，依序表示這首曲子的旋律。
至少有 40% 的測試資料滿足 L<=100。
至少有 65% 的測試資料滿足 L<=5000。
對於所有測試資料都有 L<=105
輸出請包含兩行，第一行有一個非負整數表示至少得誤彈的次數。第二行請輸出恰好 L 個音符編號，滿足吹奏的條件。
5 4 2 1111 2101 2000 0100 0000 7 1 5 4 5 3 2 1 5 4 2 1111 2101 2000 0100 0000 7 1 5 4 5 3 2 1
1 1 2 4 5 3 2 1 1 1 2 4 5 3 2 1
Migrated from old NTUJ.
BOI2012 Day2
| No. | Testdata Range | Score |
|---|