Andy is very bad at chess, and his friend bullies him by making him play Chinese chess. Andy has never played Chinese chess before and is very confused about how the Cannon Pieces work. The Cannon Piece can take a piece only if there is exactly one other piece between the Cannon Piece and that piece on the same row or column. For example, let
c denote the Cannon Piece,
. denotes blank space, and
* represent any other pieces:
The Cannon Piece can take the piece at the end of the row. (It's worth noting that it also works for columns.)
The Chess board is an ~N \times M~ grid. Can you help Andy determine the total number of positions he can place the Cannon Piece such that the Cannon Piece can take a piece on the next turn? It is important to note that a valid position cannot already have a piece on it.
For all subtasks:
~1 \le N, M \le 3 \times 10^3~
Every character in the grid is either
Subtask 1 [30%]
~1 \le N, M \le 100~
Subtask 2 [70%]
No additional constraints.
The first line contains two integers ~N~ and ~M~, the number of rows and columns.
The following ~N~ lines describe the grid, with ~M~ characters in each line.
Output the number of positions such that if the Cannon Piece is placed there, it can take a piece on the next move.
5 5 ..*.. ..... .*.** *..*. .*.*.
Valid points are denoted with the symbol
.c*c. .c.c. c*c** *..*c c*.*c