Time Limit: 6000/6000 MS (Java/Others)

Memory Limit: 32768/32768 K (Java/Others)

The starry sky in the summer night is one of the most beautiful things on this planet. People imagine that some groups of stars in the sky form so-called constellations. Formally a constellation is a group of stars that are connected together to form a figure or picture. Some well-known constellations contain striking and familiar patterns of bright stars. Examples are Orion (containing a figure of a hunter), Leo (containing bright stars outlining the form of a lion), Scorpius (a scorpion), and Crux (a cross).

In this problem, you are to find occurrences of given constellations in a starry sky. For the sake of simplicity, the starry sky is given as a N × M matrix, each cell of which is a '*' or '0' indicating a star in the corresponding position or no star, respectively. Several constellations are given as a group of T P × Q matrices. You are to report how many constellations appear in the starry sky.

Note that a constellation appears in the sky if and only the corresponding P × Q matrix exactly matches some P × Q sub-matrix in the N × M matrix.

In this problem, you are to find occurrences of given constellations in a starry sky. For the sake of simplicity, the starry sky is given as a N × M matrix, each cell of which is a '*' or '0' indicating a star in the corresponding position or no star, respectively. Several constellations are given as a group of T P × Q matrices. You are to report how many constellations appear in the starry sky.

Note that a constellation appears in the sky if and only the corresponding P × Q matrix exactly matches some P × Q sub-matrix in the N × M matrix.

The input consists of multiple test cases. Each test case starts with a line containing five integers N, M, T, P and Q(1 ≤ N, M ≤ 1000, 1 ≤ T ≤ 100, 1 ≤ P, Q ≤ 50).

The following N lines describe the N × M matrix, each of which contains M characters '*' or '0'.

The last part of the test case describe T constellations, each of which takes P lines in the same format as the matrix describing the sky. There is a blank line preceding each constellation.

The last test case is followed by a line containing five zeros.

The following N lines describe the N × M matrix, each of which contains M characters '*' or '0'.

The last part of the test case describe T constellations, each of which takes P lines in the same format as the matrix describing the sky. There is a blank line preceding each constellation.

The last test case is followed by a line containing five zeros.

提交代码