Problem Description

Translated from [CERC2018] Matrice

Agent Sue Thomas and her son are searching for trinities in a grid. A trinity, as indicated by the prefix "tri," refers to a triangle formed by cells in the grid.

Each trinity is a square cell area with either the upper or lower part of a diagonal removed (an isosceles right triangle with legs parallel to the sides of the grid). The diagonal can be the main diagonal (southeast-northwest direction) or the secondary diagonal (southwest-northeast direction). A valid trinity must contain at least three cells, and all cells must contain the same character.

Input Format

The first line of input contains two integers \( N \) and \( M \), representing the number of rows and columns of the grid, respectively.

The following \( N \) lines each contain a string of length \( M \), representing the grid.

Output Format

Output the number of all distinct valid trinities in the grid.

Sample Input and Output

Sample Input #1

2 2
AA
Ad

Sample Output #1

1

Sample Input #2

5 5
#####
####.
###..
##...
#....

Sample Output #2

60

Sample Input #3

5 4
hwwr
eahe
lroy
lswo
oaau

Sample Output #3

0

Sample Input #4

5 6
#girls
##areb
#.#est
#..#!!
#####!

Sample Output #4

7

Notes

\( 1 \leq N, M \leq 10^3 \). The ASCII values of the characters in the input are between 33 and 126.

见题面 Input 部分

见题面 Output 部分