Computer vision: Slide a kernel over an image

Filtering starts with one operation: a weighted sum over a sliding window.

What to build

A program that applies a k × k kernel to an image at every position where it fits (valid correlation).

Requirements

  • The output at (r, c) is the sum of kernel[i][j] × img[r + i][c + j] over all i, j from 0 to k − 1. Do not flip the kernel.
  • Print H − k + 1 lines of W − k + 1 whole numbers, separated by spaces. Do not divide or clamp.

Input

Line 1: H and W. Then H rows of W whole numbers. Then k, then k rows of k whole-number weights.

Output

The valid output rows.

Constraints

1 ≤ k ≤ H, W ≤ 50.

Example

Input:

3 3
1 2 3
4 5 6
7 8 9
2
1 0
0 1

Output:

6 8
12 14

Why it works

The window's top-left corner moves over every position where the whole kernel fits, so each output pixel combines exactly the k × k pixels under the kernel.

Examples

Example 1 · Input
3 3
1 2 3
4 5 6
7 8 9
2
1 0
0 1
Expected output
6 8
12 14
Example 2 · Input
3 4
1 1 1 1
1 2 2 1
1 1 1 1
3
0 1 0
1 1 1
0 1 0
Expected output
7 7

Prompts inside input() are ignored when checking, so input("n: ") is fine.

Hints

Hint 1

There are H − k + 1 rows and W − k + 1 columns of positions where the kernel fits.

Hint 2

At position (r, c) add `kernel[i][j] * img[r + i][c + j]` for every i and j from 0 to k − 1.

Solution

Show one correct solution (try it yourself first)
h, w = map(int, input().split())
img = [list(map(int, input().split())) for _ in range(h)]
k = int(input())
ker = [list(map(int, input().split())) for _ in range(k)]
for r in range(h - k + 1):
    row = []
    for c in range(w - k + 1):
        row.append(sum(ker[i][j] * img[r + i][c + j] for i in range(k) for j in range(k)))
    print(" ".join(map(str, row)))

Lesson: Convolution and kernels →