Problem Statement

There is a grid with $H$ rows and $W$ columns. Each cell is an empty cell or a bomb cell. Let $(i,j)$ denote the cell at the $i$-th row from the top and the $j$-th column from the left. The grid is given by $H$ length-$W$ strings $S_1, S_2 , \dots ,S_H$: if the $j$-th character of $S_i$ is ., $(i,j)$ is an empty cell, and if the $j$-th character of $S_i$ is #, $(i,j)$ is a bomb cell.

For an empty cell $(i,j)$, if there is no bomb cell in the $i$-th row nor in the $j$-th column, that cell is called a safe empty cell.

In one move, you can move from the current cell to an adjacent empty cell in the up, down, left, or right direction (you cannot move to a bomb cell). Find the number of empty cells $(i, j)$ satisfying the following condition:

• A safe empty cell can be reached from $(i,j)$ in at most $K$ moves.

Constraints

• $1 \le H,W \le 5\times 10^5$
• $H\times W \le 5\times 10^5$
• $0 \le K \le H\times W-1$
• $S_i$ is a string of length $W$ consisting of . and #.
• $H$, $W$, and $K$ are integers.

Input

The input is given from Standard Input in the following format:

• $H$ $W$ $K$
• $S_1$
• $S_2$
• $\vdots$
• $S_H$

Output

Output the number of empty cells satisfying the condition.

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

5

The only safe empty cell is $(2,2)$. There are five empty cells from which you can reach $(2,2)$ in at most one move: $(1,2),(2,1),(2,2),(2,3),(3,2)$, so the answer is $5$.

2 3 0
...
...

6

Since there is no bomb cell, all six cells are safe empty cells. Therefore, every empty cell satisfies the condition with zero moves.

5 7 2
..#....
..#....
.......
...#...
...#...

29

• Source: AtCoder ABC 472 D