006 - 禁断の数列

問題

縦 h [m], 横 w [m]のマスに1~9のいずれかの数字が表示されている。
マスの中の数字は、以下の動作を繰り返す。

1.禁断の数列(str)をマスの中からすべて探し出す。
2.禁断の数列が含まれているマスの数字をすべて一律の数字に変更する。
ここで言う一律の数字は、最初　n から始まり、一律の数字に変えた後1ずつ増えていく。
一律の数字が9になったら1に戻り、1からまた増え始める。

以上の動作を繰り返し、何回数字を変更すれば禁断の数列がマスから無くなるかを求めよ。
また、いくつ禁断の数列が現れたかも出力せよ。
禁断の数列の最初の数字から上下左右に辿り、数列の数字が順に発見できれば、禁断の数字があるということである。（日本語難しい）
ただし、マスの中に指定された数列が複数現れることがあり、マスの数字は複数の数列に含めてもよいものとする。

入力

h w n
s1
s2
.
.
.
sh
l
str

マスの縦と横の長さ 2 <= h,w <= 2000
最初に変更する数字 1 <= n <= 9
マスの数字の長さ 　　1 <= s_i <= w
禁断の数列の長さ 　　1 <= l <= 30
禁断の数列 　　　1 <= str <= l

循環するような禁断の数列は存在しない。

出力

数字を変更する最小回数とそのときの禁断の数列の総数を空白区切りで出力せよ。

入出力例

入力例1

5 5 9
12345
23451
34512
45123
51234
5
12345

出力例1

1 16

解説

12345
23451
34512
45123
51234
↓
99999
99991
99912
99123
91234

となり、禁断の数列はもう無い。
現れた数列は16個なので、これを出力する。

入力例2

5 5 1
12659
43598
52987
69296
78345
9
123456789

出力例2

2 6

解説

12659
43598
52987
69296
78345
↓
11659
11598
12987
11296
11345
↓
11652
11522
12222
12222
11222

入力例3

5 5 1
12345
11223
54544
33735
75211
5
12345

出力例

4 8

解説