← 返回题目列表

Codeforces · 958/A2

A2. 死星(中)

中文机器翻译题面 查看原题

恒星日期是 1983 年,海蒂公主在探测死星方面越来越擅长。这次,两名叛军间谍再次给了海蒂两张地图,上面标有死星的可能位置。自从她上次除掉了所有双重间谍后,她知道两张地图都是正确的,并且确实显示了包含死星的太阳系地图。不过,这次帝国把死星隐藏得很好,海蒂需要找到两张地图上都出现的地方,才能探测到死星。

第一张地图是一个 N × M 网格,其中每个单元格显示存在于相应空间象限中的某种类型的宇宙物体。第二张地图是一个 M × N 网格。海蒂需要将这两张地图对齐,使其在某个 M × M 部分上重叠,其中所有宇宙物体都是相同的。帮助海蒂找出这样一个 M × M 部分在两张地图中的位置。

输入

输入的第一行包含两个空格分隔的整数 N 和 M (1 ≤ N ≤ 2000, 1 ≤ M ≤ 200, M ≤ N)。接下来的 N 行每行包含 M 个小写拉丁字符 (a-z),表示第一个地图。不同的人物对应不同的宇宙物体类型。接下来的 M 行每行包含 N 个字符,以相同的格式描述第二张地图。

输出

输出的唯一行应包含两个空格分隔的整数 i 和 j,表示第一个映射中从第 i 行开始的大小为 M × M 的部分等于第二个映射中从第 j 列开始的部分。行和列从 1 开始编号。

如果有多种可能的方式来对齐地图,海蒂会对其中任何一种感到满意。保证存在解。

示例

输入 #1

10 5
somer
andom
noise
mayth
eforc
ebewi
thyou
hctwo
again
noise
somermayth
andomeforc
noiseebewi
againthyou
noisehctwo

输出 #1

4 6

注意

第一个测试用例的 5×5 网格如下所示: