SWERC14J - The Big Painting

Galerie de Vues de la Rome Moderne, Panini (1759). What
S.W.E.R.C. had in mind when he tried to merge his paintings.

Samuel W. E. R. Craft is an artist with a growing reputation. Unfortunately, the paintings he sells do not provide him enough money for his daily expenses plus the new supplies he needs. He had a brilliant idea yesterday when he ran out of blank canvas: "Why don't I create a gigantic new painting, made of all the unsellable paintings I have, stitched together?". After a full day of work, his masterpiece was complete.

That's when he received an unexpected phone call: a client saw a photograph of one of his paintings and is willing to buy it now! He had forgotten to tell the art gallery to remove his old works from the catalog! He would usually welcome a call like this, but how is he going to find his old work in the huge figure in front of him?

 

Task

Given a black-and-white representation of his original painting and a black-and-white representation of his masterpiece, can you help S.W.E.R.C. identify in how many locations his painting might be?

Input

The first line consists of 4 space-separated integers: hp wp hm wm, the height and width of the painting he needs to find, and the height and width of his masterpiece, respectively.

The next hp lines have wp lower-case characters representing his painting. After that, the next hm lines have wm lower-case characters representing his masterpiece. Each character will be either 'x' or 'o'.

Constraints

1 ≤ hp, wp ≤ 2 000
1 ≤ hm, wm ≤ 2 000
hp ≤ hm
wp ≤ wm

Output

A single integer representing the number of possible locations where his painting might be.

Sample Input

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

Sample Output

4

Sample Output Explanation

The painting could be in four locations as shown in the following picture. Two of the locations overlap.

Image sample_output_explanation

 


Authors: Miguel Araújo and Miguel Oliveira

Added by:Miguel Oliveira
Date:2014-12-01
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:SWERC 2014

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.