Welcome to ZOJ
Select Problem
ZOJ Problem Set - 2130
5 Spots

Time Limit: 2 Seconds      Memory Limit: 65536 KB

5 Spots is one of my favourite games of Fantasy Games series. In the game you should find out the 5 spots hidden in each picture within a limited time. And if you make a mistake you will lose some time available. The game ends when you find out all the five spots or the available time is used up. There is so many pictures in the game that it is almost impossible to remember the locations of the spots on all the pictures.

Let's consider a simplified game mode. You are given a rectangular monochrome picture in which several spots are hidden. The shapes of every spots are the same. A shape of spot is also a rectangular monochrome picture but some area may be transparent. Your task is to find out all the hidden spots and answer how many spots are hidden in the picture.


Input contains multiple test cases. Each test case starts with four positive numbers H, W, h, w (1 <= h <= H <= 60, 1 <= w <= W <= 60), which is the height and width of the picture and the height and width of the shape of spots respectively. Then the following H lines show the figure of the picture, each line has W characters. The character may be 'O' or 'X' which specifies the color. Then the following h lines show the figure of the shape of the spots, each line has w characters. The character may be 'O', 'X' or '.' which specifies the color or a transparent area (which can match either color 'O' or 'X').


There is one line for each test case, which is the number of spots you find out on the picture. If you find out no spots hidden in the picture, just output 0.

Sample Input

4 4 2 2
4 4 3 3

Sample Output


Homepage: http://fairyair.yeah.net/

Time is just a mirage. The history and future branch off infinitely at every slice of time. All possible or impossible-like histories and futures exist individually and intersect at the current time space which make all relative existence related to each other.

Author: CHEN, Shixi
Source: Online Contest of Fantastic Game
Submit    Status