Counting Beach Cells in a Satellite Image

You are given a satellite image representing a rectangular grid of n rows and m columns. Each cell in the grid is either land (denoted by a dot .) or water (denoted by a hash #). Although the satellite photo clearly distinguishes between land and water, it does not classify the type of land. It is known that for any water cell, every land cell that is reachable in at most k steps in the four cardinal directions (up, down, left, right) will become a beach cell. Formally, for each water cell at position \( (i,j) \), every land cell at position \( (x,y) \) such that \[ |x - i| + |y - j| \le k \] becomes a beach cell. Note that if a water cell is near the boundary of the photo, some reachable beach cells might lie outside the photographed area. You may assume that there is no water outside the photo.

Your task is to compute the number of beach cells within the photo (i.e. in the given grid). A cell that is originally water remains water and is not counted even if it falls within the distance criteria. Only land cells that are reachable by at least one water cell are considered beaches.

inputFormat

The first line contains three integers \( n \), \( m \) and \( k \) (the number of rows, columns, and the maximum number of steps respectively). The following \( n \) lines each contain a string of length \( m \) consisting only of the characters . (land) and # (water), representing the satellite photo.

outputFormat

Output a single integer, the number of beach cells (land cells that are reachable from at least one water cell within \( k \) steps in the four cardinal directions).

sample

3 3 1
...
.#.
...

4