시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 512 MB64555288.136%

문제

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 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 the number of different valid trinities in the input grid.

예제 입력 1

2 2
AA
Ad

예제 출력 1

1

예제 입력 2

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

예제 출력 2

60

예제 입력 3

5 4
hwwr
eahe
lroy
lswo
oaau

예제 출력 3

0

예제 입력 4

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

예제 출력 4

7