The Big Picture

Time limit2sMemory limit512 MB

Summary

Count the top-left positions where the given black-and-white painting matches the masterpiece exactly without rotation.

Level: Medium7 of 10
Topics: String matching
Solved: No attempts yet

Problem

Jaehyuk is a painter with no money, not even a board to paint on. So he decided to sew his unsold paintings together into one large picture, and after a full day of work he finished a masterpiece.

One day a buyer called and asked for one of the paintings that had not been sold. Jaehyuk never wrote down which paintings went into the masterpiece, so he has to find where that painting ended up.

You are given one painting and the masterpiece, both drawn in black and white. Count how many positions of the masterpiece the painting appears at. The painting was glued in exactly as it is, so it is never rotated or flipped, and one position is one top left coordinate at which every cell of the painting equals the cell of the masterpiece under it. Positions that overlap are counted separately.

Input

The first line contains the integers $h_p$ , $w_p$ , $h_m$ , $w_m$ , separated by spaces. They are the height and the width of the painting, then the height and the width of the masterpiece.

The next $h_p$ lines contain the painting, $w_p$ characters per line. The following $h_m$ lines contain the masterpiece, $w_m$ characters per line. Both pictures consist only of the characters 'o' and 'x'.

$1 \le h_p \le h_m \le 2000$ and $1 \le w_p \le w_m \le 2000$ .

Output

Print the number of positions where the painting appears in the masterpiece, on one line.

Examples3

Example 1

Input

4 4 10 10
oxxo
xoox
xoox
oxxo
xxxxxxoxxo
oxxoooxoox
xooxxxxoox
xooxxxoxxo
oxxoxxxxxx
ooooxxxxxx
xxxoxxoxxo
oooxooxoox
oooxooxoox
xxxoxxoxxo

Expected output

Example 2
Input
```
1 1 1 1
o
o
```
Expected output
```
1
```
Example 3
Input
```
2 2 3 3
oo
oo
oxo
xox
oxo
```
Expected output
```
0
```