554. Свертка на пальцах

Не решаласьЛёгкая

Свертка - одна из важных операций в обработке данных. В этом задании требуется реализовать простую версию свертки в 2D.

Даны матрица AA размера n×mn \times m и матрица BB размера k×kk \times k. Результатом операции будем называть матрицу CC размера (nk+1)×(mk+1)(n - k + 1) \times (m - k + 1), элементы которой определяются следующим образом:

ci,j=t=1kl=1kai+t1,j+l1bt,l. c_{i,j}=\sum_{t=1}^{k}\sum_{l=1}^{k} a_{i+t-1,j+l-1} \cdot b_{t,l}.

Формат ввода

В первой строке даны два целых числа nn и mm (2n,m202 \le n, m \le 20).

Далее в каждой из nn строк записано по mm целых чисел: ai,1a_{i,1} \ldots ai,ma_{i,m}.

В следующей строке записано одно целое число kk (1kmin(n,m)1 \le k \le min(n,m)).

Далее в каждой из kk строк записано по kk целых чисел: bi,1b_{i,1} \ldots bi,kb_{i,k}.

Все числа по модулю не превосходят 100.

Формат вывода

Выведите (nk+1)(n-k+1) строк по (mk+1)(m-k+1) целому числу - результат выполнения свертки. Числа в строках разделите пробелами.

Ограничения

Ограничение времени

1 с

Ограничение памяти

256 МБ

Пример 1

Ввод
2 3
1 2 3
2 3 4
2
1 0
1 1
Вывод
6 9

Пример 2

Ввод
2 2
1 2
2 1
1
3
Вывод
3 6
6 3

Пример 3

Ввод
3 5
1 0 1 0 1
0 1 0 1 0
2 0 2 0 2
2
-1 1
1 -1
Вывод
-2 2 -2 2
3 -3 3 -3

Теги

Нужно войти, чтобы отправить решение.Войти