#581. [ABC391B] Seek Grid

[ABC391B] Seek Grid

题目描述

给定一个 N×NN \times N 的网格 SS 和一个 M×MM \times M 的网格 TT。我们用 (i,j)(i,j) 表示从上数第 ii 行、从左数第 jj 列的格子。
SSTT 中格子的颜色由 N2N^2 个字符 Si,jS_{i,j}1i,jN1 \le i,j \le N)和 M2M^2 个字符 Ti,jT_{i,j}1i,jM1 \le i,j \le M)表示。在网格 SS 中,如果 Si,jS_{i,j}. 则格子 (i,j)(i,j) 为白色,若为 # 则为黑色。网格 TT 同理。

请找出 TTSS 中的位置。具体地,输出满足以下条件的整数 aabb1a,bNM+11 \le a,b \le N-M+1):
对于所有 i,ji,j1i,jM1 \le i,j \le M),有 Sa+i1, b+j1=Ti,jS_{a+i-1,\ b+j-1} = T_{i,j}

题目保证恰好存在一对 (a,b)(a,b) 满足条件。

输入格式

输入从标准输入按以下格式给出:

N M
S_{1,1}S_{1,2}...S_{1,N}
S_{2,1}S_{2,2}...S_{2,N}
...
S_{N,1}S_{N,2}...S_{N,N}
T_{1,1}T_{1,2}...T_{1,M}
T_{2,1}T_{2,2}...T_{2,M}
...
T_{M,1}T_{M,2}...T_{M,M}

输出格式

在一行内输出 aabb,中间用空格分隔。

样例

3 2
#.#
..#
##.
.#
#.
2 2
2 1
#.
##
.
1 2

数据范围

  • 1MN501 \le M \le N \le 50
  • N,MN, M 均为整数
  • Si,j,Ti,jS_{i,j}, T_{i,j} 只可能为 .#
  • 确保恰好存在一组 (a,b)(a,b) 满足条件