Virtual Reality Playspace

Time limit4sMemory limit2048 MB

Summary

Count the maximal empty rectangles in an r by c grid with obstacles whose sides are at least s and t in length, where each side touches a wall or an obstacle.

Level: Medium7 of 10
Topics: Matrix, Stack, Two pointers, Prefix sum
Solved: No attempts yet

Problem

Yolanda just finished moving the furniture around her house. Her house is shaped like a rectangle with side lengths $r$ and $c$ . Yolanda wants to choose a place for her virtual reality (VR) playspace.

A VR playspace must meet these standards:

It takes the shape of a rectangle.
Its sides are parallel and perpendicular to the sides of the house.
It exactly covers every unit square it occupies.
It contains no obstacles.
It is at least $s$ units across along one side and at least $t$ units across along the other.
Each of its sides borders either the house's outer walls or an obstacle. In other words, a VR playspace is maximally sized.

Given a map of the house, count how many different places Yolanda can choose for her VR playspace.

Input

The first line contains four integers $r$ , $c$ , $s$ , and $t$ ( $1 \le r, c, s, t \le 3000$ ), the length and width of the house and the size of the VR playspace. The next $r$ lines each contain a string of $c$ characters describing the house. Each character is either a dot (.) for an empty unit square or a zero (0) for an obstacle.

Output

Output a single integer, the number of different places Yolanda can choose for her VR playspace.

Examples1

Example 1

Input

4 7 1 2
.....00
.0...0.
..00.0.
.0.0.00

Expected output