← 返回题目列表

Codeforces · 228/B

B. 两张桌子

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

您有两个矩形表格,单元格大小分别为 na × ma 和 nb × mb。这些表由零和一组成。我们将考虑从1开始索引的两个表的行和列。然后我们将位于第i行和第j列交集的第一个表的元素定义为ai,j;我们将位于第 i 行和第 j 列交叉点的第二个表的元素定义为 bi, j。

我们将整数对 (x, y) 称为第二个表相对于第一个表的移位。我们将调用偏移 (x, y) 值的重叠因子:

$$\sum_{i,j}a_{i,j}\cdot b_{i+x,j+y}$$

其中变量i,j仅取这样的值,其中表达式ai,j·bi + x,j + y有意义。更正式地说,不等式 1 ≤ i ≤ na、1 ≤ j ≤ ma、1 ≤ i + x ≤ nb、1 ≤ j + y ≤ mb 必须成立。如果没有满足给定不等式的变量 i、j 的值,则总和的值被视为等于 0。

您的任务是在所有可能的班次中找到重叠系数最大的班次。

输入

第一行包含两个空格分隔的整数 na, ma (1 ≤ na, ma ≤ 50) — 第一个表中的行数和列数。然后 na 行每行包含 ma 个字符——第一个表的元素。每个字符要么是“0”,要么是“1”。

下一行包含两个空格分隔的整数 nb, mb (1 ≤ nb, mb ≤ 50) — 第二个表中的行数和列数。然后遵循格式中第二个表的元素,与第一个表类似。

保证第一个表至少有一个数字“1”。保证第二表至少有一个数字“1”。

输出

打印两个空格分隔的整数 x, y (|x|, |y| ≤ 109) — 具有最大重叠系数的移位。如果有多个解决方案,请打印其中任何一个。

示例

输入 #1

3 2
01
10
00
2 3
001
111

输出 #1

0 1

输入 #2

3 3
000
010
000
1 1
1

输出 #2

-1 -1