| Codeforces Round 141 (Div. 2) |
|---|
| Закончено |
Вам заданы две прямоугольные таблицы размерами na × ma и nb × mb клеток, состоящие из нулей и единиц. Будем считать, что строки и столбцы обеих таблиц нумеруются, начиная с 1. Тогда элемент первой таблицы, стоящий на пересечении i-ой строки и j-ого столбца, обозначим за ai, j; элемент второй таблицы, стоящий на пересечении i-ой строки и j-ого столбца, обозначим за bi, j.
Пару целых чисел (x, y) назовем сдвигом второй таблицы, относительно первой. Коэффициентом совпадения сдвига (x, 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) — количество строк и столбцов во второй таблице. Далее записаны элементы второй таблицы в формате аналогичном первой таблице.
Гарантируется, что в первой таблице есть хотя бы одна единица. Гарантируется, что во второй таблице есть хотя бы одна единица.
Выведите через пробел два целых числа x, y (|x|, |y| ≤ 109) — сдвиг с максимальным коэффициентом совпадения. Если существует несколько решений, выведите любое.
3 2
01
10
00
2 3
001
111
0 1
3 3
000
010
000
1 1
1
-1 -1
