5. Свертка туда и обратно

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

Свертка - одна из важных операций в обработке данных. В этом задании требуется реализовать простую версию свертки в 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}.

Известны матрицы AA и CC, найдите подходящую матрицу BB.

Формат ввода

В первой строке даны три целых числа nn, mm и kk (5n,m205 \le n, m \le 20, 1k31 \le k \le 3).

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

Далее в каждой из (nk+1)(n-k+1) строк записано по (mk+1)(m-k+1) целых чисел: ci,1c_{i,1} \ldots ci,mk+1c_{i,m-k+1}.

Гарантируется, что все элементы матрицы BB можно восстановить однозначно. Все элементы матриц AA и BB по модулю не превосходят 100.

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

Выведите kk строк по kk целых чисел -- элементы матрицы BB. Числа в строках разделите пробелами.

Ограничения

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

1 с

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

256 МБ

Пример 1

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

Пример 2

Ввод
5 5 2
-48 -47 -5 58 -93
35 -26 42 -58 -59
-37 30 20 100 -83
43 -99 -9 19 -48
93 37 -84 -99 84
-2688 10345 -6343 -9836
1671 3474 1850 -13016
-8449 5224 4502 -18620
-11835 -2233 -1057 12591
Вывод
-93 38
-82 96

Пример 3

Ввод
6 5 3
-17 -37 61 -19 90
94 6 22 86 -82
10 65 -56 52 -80
-52 -53 -27 -81 39
4 22 58 -53 -63
-98 62 -100 66 -34
-375 16185 -6904
-9850 -11424 5127
2151 -14707 1641
-1387 10203 -15056
Вывод
-92 70 -15
-3 97 32
50 38 43

Теги

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