Surveillance

A crime has been committed in the city of <insert name here>! All of the donuts in the bakery next to the police station has mysteriously disappeared. Since this is the favourite bakery of the police, every resource available will be used to find the thief.

The police has made a list of suspected donut thieves, but there is no evidence against anyone yet. Luckily, there is security footage from the scene of the crime. Unfortunately it takes way too long time to watch all of the footage to be done before the expiry date of the donuts has passed.

Therefore, you have been tasked with writing a program to find the cookie thieves in the images. Your program will be given a $W \times W$ image of a suspected cookie thief, and a $B \times B$ image from the security footage. An image consists of a rectangular array of pixels, which we represent as integers.

Your program should count the number of occurances of the cookie thief image inside the security footage image. We say that a $W \times W$ subrectangle of the security footage contains the cookie thief image if there exists some constant $C$ such that every pixel in the subrectangle equals the corresponding pixel in the cookie thief image plus $C$. This is because the images may have been taken using different exposure settings, meaning one of the images can be lighter than the other.

Example

Let the security footage be

and the cookie thief image is

Then there are five matches in the security footage: those areas with upper left corners in $(0, 0), (0, 1), (0, 2), (1, 2), (2, 2)$ (denoted by $(row, column)$). The constants $C$ are $1, 2, 3, 3, 3$ respectively.

Task

Your task is to compute how many times the cookie theif image appears in the security footage image. You should implement a function surveillance(B, W, S, T).

• surveillance(B, W, S, T) - this function will be called exactly once by the judge.

  • B: an integer - the size of the security footage image.

  • W: an integer - the size of the cookie thief image.

  • $W \le B$

  • S: a two-dimensional array with $B \times B$ integers. S[i][j] ($0 \le i, j < B$) contains the value of the pixel on row $i$ and column $j$ in the security footage image.

  • T: a two-dimensional array with $W \times W$ integers. T[i][j] ($0 \le i, j < W$) contains the value of the pixel on row $i$ and column $j$ in the cookie thief.

  • $0 \le S[i][j], T[i][j] \le 10^9$

  • The function should return an integer, the number of matches in the image.

A code skeleton containing the function to be implemented, together with a sample grader, can be found at http://progolymp.se/uploads/kattis-attachments/surveillance.zip.

Subtasks

The problem consists of a number of subtasks. Each subtask gives some amount of points, and to pass the subtask you must pass all the test cases in the subtask.

Input format

The sample judge reads input in the following format:

• line $1$: B W

• line $i = 2$ to $2 + B - 1$: B[i][0] B[i][1] ... B[i][B - 1]

• line $i = 2 + B$ to $2 + B + W - 1$: W[i][0] W[i][1] ... W[i][B - 1]

Output format

The judge writes a single line containing the return value of surveillance(B, W, S, T).

4 2
1 2 3 4
1 2 3 4
4 3 3 4
4 3 3 4
0 1
0 1

5