Matrice

Time limit1sMemory limit512 MB

Summary

Count all triangular regions cut from squares by one diagonal whose cells all hold the same character.

Level: Medium6 of 10
Topics: Dynamic programming, Matrix, Implementation
Solved: No attempts yet

Problem

Agent Sue Thomas and her son are looking for trinities in a grid. The word trinity is a neologism referring to a particular triangular shape (as the morpheme "tri" suggests) 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.

Input

The first input line contains two numbers N and M (1 ≤ N, M ≤ 1000), describing the number of rows and columns in the grid, respectively. Each of next N lines contains M characters, whose ASCII codes are between 33 and 126, inclusively.

Output

Output the number of different valid trinities in the input grid.

Examples4

Example 1
Input
```
2 2
AA
Ad
```
Expected output
```
1
```
Example 2
Input
```
5 5
#####
####.
###..
##...
#....
```
Expected output
```
60
```
Example 3
Input
```
5 4
hwwr
eahe
lroy
lswo
oaau
```
Expected output
```
0
```

Example 4

Input

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

Expected output