407978: GYM102956 F Border Similarity Undertaking

There is a large organization called Border Similarity Undertaking (BSU) which is located in Bytelandia. The head of the organization has a large map of this glorious country. The map is represented as a matrix $$$A$$$ with $$$n$$$ rows and $$$m$$$ columns. Each element of the matrix is a lowercase Latin letter.

BSU has decided to construct a new factory. The factory may be of any size, but it must be rectangular and its sides must be parallel to the sides of the map. Moreover, as you can deduce from the name of the organization, it is required that all the letters on the border of the rectangle are the same.

The head of BSU hasn't decided where to build a factory yet. So BSU has hired you to calculate the number of possible factory locations.

Formally speaking, you are to find the number of tuples of integers $$$(x_1, y_1, x_2, y_2)$$$ such that $$$1 \le x_1 < x_2 \le n$$$, $$$1 \le y_1 < y_2 \le m$$$, and $$$A_{i,y_1} = A_{x_1, j} = A_{x_2, j} = A_{i, y_2}$$$ for all $$$i \in [x_1, x_2]$$$, $$$j \in [y_1, y_2]$$$.

The first line contains two integers $$$n$$$ and $$$m$$$, denoting the number of rows and the number of columns of the map of Bytelandia ($$$1 \le n, m \le 2000$$$).

Each of the following $$$n$$$ lines contains $$$m$$$ lowercase Latin letters, describing the matrix $$$A$$$ row by row.

Print the number of possible locations where BSU can construct a new factory.

3 5
zzzzz
zxzxz
zzzzz

3

4 4
abbc
bcca
babc
acbb

0

12 12
abbabaaaaabb
ababaaaaaabb
aaabbbbbabbb
aabababaaaba
abbbaaabaaba
baaababbbaba
aaaaababbaaa
bbabbbbbabaa
bbbabbaabaaa
aabbbaaaabba
babaabababaa
bababaabaaba

25