Description

Translated from [CERC2018] Matrice.

Agent Sue Thomas and her son are looking for trinity in a grid. Trinity is a new word which, as the morpheme tri suggests, refers to a triangle made up of cells in the grid.

Each trinity is obtained by taking a square region of cells and removing the part above or below one of its diagonals (an isosceles right triangle, with its two legs parallel to the two sides of the grid). The diagonal can be the main diagonal (southeast–northwest direction) or the anti-diagonal (southwest–northeast direction). A valid trinity contains at least three cells, and the characters in all its cells are the same.

Input Format

The first line contains two integers $N, M$, representing the number of rows and columns of the grid.

The next $N$ lines each contain a string of length $M$, representing the grid.

Output Format

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

2 2
AA
Ad

1

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

60

5 4
hwwr
eahe
lroy
lswo
oaau

0

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

7

Hint

$1 \le N, M \le 10^3$, and the characters appearing in the input have ASCII codes between $33$ and $126$ inclusive.

Translated by ChatGPT 5