CSG-CPC Online Judge

1181 : 矩阵字符串

         Time Limit: 1 Sec     Memory Limit: 128 Mb     Submitted: 228     Solved: 33    

Description

在二维字符阵列中寻找指定的字符串。

字符串出现的形式可能是水平、竖直、向前、向后和斜向。输出的位置顺序应该与输入中的字符串出现顺序一致。区分字符的大小写。

如果某个字符串在字符阵列中出现多次,则输出描述起点、终点坐标四个数字依次最小的一个。

Input

多组测试数据,每组数据:

前两行分别指示字符矩阵的宽 w 和高 h1<=w<=80, 1<=h<=80)。

接下来的 h 行每行 w 个字符便是字符矩阵的内容,再下面的 1 行为要寻找的字符串的数目 nn<10),其后的 n 行便是要寻找的字符串,每个字符串不会超过 20 个字符。

Output

n 行,每行输出对应字符串的位置。位置的格式形如(1,2)->(2,6),意为该字符串首字母在字符矩阵中的位置是第 12 行,尾字母在字符矩阵中的位置是第 26 行。

Sample Input

7
7
E Y B E Y B D
K D I C J E N
A K E W N Q A
O A Y T U E L
E N A M A J R
Z Z C A D W O
E K S I A P B
3
AAAAA
BYEBYE
BORLAND

Sample Output

(1,3)->(5,7)
(6,1)->(1,1)
(7,7)->(7,1)

Hint