Linas 喜欢弹奏某种乐器，没人知道它叫什么名字。该乐器有 $S$ 个按孔，Linas 可以通过用 10 种不同的方式（编号为 $0$ 到 $9$）按住每个孔来演奏 $N$ 种不同的音符（编号为 $1$ 到 $N$）。每个音符都对应唯一一种按孔方式，由一串表示各个按孔状态的数字序列描述。如果按孔方式不正确（即不对应任何音符），乐器就会发出非常难听的声音，因此 Linas 宁愿演奏一个错误的音符，也不愿错误地按孔。

Linas 在一个乐团中演奏，他需要非常快速地演奏复杂的曲调。Linas 写了一首曲子（即一个对应音符的数字序列），并希望与乐团一起演奏。不幸的是，Linas 的演奏并不完美。只有当演奏相邻的第二个音符时，改变按法（与前一个音符相比）的按孔数量不超过 $G$ 个，他才能连续演奏这两个音符。因此，他决定有时在曲子中演奏错误的音符。Linas 演奏的每个错误音符都被称为一次“失误”。

给定一首曲子，找出一首修改后的曲子，使得 Linas 能够演奏它，且失误次数尽可能少。

输入格式

输入的第一行包含三个整数：可选音符的数量 $N$（$1 \le N \le 100$）、按孔数量 $S$ 以及手指速度 $G$（$0 \le G < S \le 100$）。

接下来的 $N$ 行，每行包含 $S$ 个无空格的数字。第 $i+1$ 行的第 $j$ 个数字对应演奏第 $i$ 个音符时第 $j$ 个孔所需的按法（按孔方式有多种，用 $0$ 到 $9$ 的数字标记）。没有两个音符的按法是完全相同的。

第 $N+2$ 行包含曲子的长度 $L$（$1 \le L \le 10^5$）。

最后一行包含这首曲子：$L$ 个由空格隔开的整数，对应曲子中连续演奏的音符。

输出格式

第一行包含一个非负整数，表示最少的失误次数。

第二行包含一首满足要求的曲子，该曲子能达到最少的失误次数：$L$ 个由空格隔开的整数，对应 Linas 应该演奏的音符。如果有多首这样的曲子，输出其中任意一首即可。

样例

样例输入 1

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

样例输出 1

1
1 2 4 5 3 2 1

样例说明 1

Linas 无法在演奏音符 1 之后直接演奏音符 5。

子任务

• 对于 $L \le 100$ 的测试点，得 40 分。
• 对于 $L \le 5000$ 的测试点，得 65 分。