/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 200 点
問題文
N \times N のグリッド S と M\times M のグリッド T が与えられます。上から i 行目、左から j 列目のマス目をマス (i,j) と表します。
S,T の各マスの色はそれぞれ N^2個の文字 S_{i,j} \; (1\leq i,j\leq N) および M^2 個の文字 T_{i,j} \; (1\leq i,j\leq M) によって表されます。
S_{i,j} が . のとき S のマス (i,j) は白色、S_{i,j} が # のとき S のマス (i,j) は黒色で塗られています。T についても同様です。
S の中から T を探してください。具体的には、以下の条件を満たす a,b \; (1 \leq a,b \leq N-M+1) を出力してください。
- すべての i,j \; (1\leq i,j \leq M) について、S_{a+i-1,b+j-1} = T_{i,j}
制約
- 1 \leq M \leq N \leq 50
- N,M は整数
- S_{i,j},T_{i,j} は
.または# - 条件を満たす a,b はちょうど 1 組存在する。
入力
入力は以下の形式で標準入力から与えられる。
N M
S_{1,1}S_{1,2}\dots S_{1,N}
S_{2,1}S_{2,2}\dots S_{2,N}
\vdots
S_{N,1}S_{N,2}\dots S_{N,N}
T_{1,1}T_{1,2}\dots T_{1,M}
T_{2,1}T_{2,2}\dots T_{2,M}
\vdots
T_{M,1}T_{M,2}\dots T_{M,M}
出力
a,b をこの順に空白区切りで 1 行に出力せよ。
入力例 1
3 2 #.# ..# ##. .# #.
出力例 1
2 2
S の 2 行目から 3 行目、2 列目から 3 列目の 2 \times 2 マスが T と一致します。
入力例 2
2 1 #. ## .
出力例 2
1 2
Score : 200 points
Problem Statement
You are given an N \times N grid S and an M \times M grid T. The cell at the i-th row from the top and the j-th column from the left is denoted by (i,j).
The colors of the cells in S and T are represented by N^2 characters S_{i,j} (1\leq i,j\leq N) and M^2 characters T_{i,j} (1\leq i,j\leq M), respectively. In grid S, cell (i,j) is white if S_{i,j} is ., and black if S_{i,j} is #. The same applies for grid T.
Find T within S. More precisely, output integers a and b (1 \leq a,b \leq N-M+1) that satisfy the following condition:
- S_{a+i-1,b+j-1} = T_{i,j} for every i,j (1\leq i,j \leq M).
Constraints
- 1 \leq M \leq N \leq 50
- N and M are integers.
- Each of S_{i,j} and T_{i,j} is
.or#. - There is exactly one pair (a,b) satisfying the condition.
Input
The input is given from Standard Input in the following format:
N M
S_{1,1}S_{1,2}\dots S_{1,N}
S_{2,1}S_{2,2}\dots S_{2,N}
\vdots
S_{N,1}S_{N,2}\dots S_{N,N}
T_{1,1}T_{1,2}\dots T_{1,M}
T_{2,1}T_{2,2}\dots T_{2,M}
\vdots
T_{M,1}T_{M,2}\dots T_{M,M}
Output
Print a and b in this order, separated by a space on one line.
Sample Input 1
3 2 #.# ..# ##. .# #.
Sample Output 1
2 2
The 2 \times 2 subgrid of S from the 2nd to the 3rd row and from the 2nd to the 3rd column matches T.
Sample Input 2
2 1 #. ## .
Sample Output 2
1 2