407978: GYM102956 F Border Similarity Undertaking

Memory Limit:0 MB Time Limit:6 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

F. Border Similarity Undertakingtime limit per test6 secondsmemory limit per test512 mebibytesinputstandard inputoutputstandard output

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]$$$.

Input

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.

Output

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

ExamplesInput
3 5
zzzzz
zxzxz
zzzzz
Output
3
Input
4 4
abbc
bcca
babc
acbb
Output
0
Input
12 12
abbabaaaaabb
ababaaaaaabb
aaabbbbbabbb
aabababaaaba
abbbaaabaaba
baaababbbaba
aaaaababbaaa
bbabbbbbabaa
bbbabbaabaaa
aabbbaaaabba
babaabababaa
bababaabaaba
Output
25

加入题单

上一题 下一题 算法标签: