Matrice#9756
Agent Sue Thomas and her son are looking for trinities in a grid. The word trinity is a neologism referring to a particular triangular (as the morpheme "tri" suggests) shape composed of cells in the grid.
Each trinity is a result of taking a square-shaped area of the cells and removing all cells that lie either above or below one of the two diagonals of the area. The diagonal may be either the main diagonal (southeast-northwest direction) or the main antidiagonal (southwest-northeast direction). A valid trinity consists of at least three grid cells and all its cells contain the same character.
The first line contains two numbers and m~(1 \le n, m \le 1000), describing the number of rows and columns in the grid, respectively. Each of next lines contains characters, whose ASCII codes are between and , inclusively.
Output the number of different valid trinities in the input grid.
Example 1
Example 2
Example 3
Example 4