In today's world, technology is developing rapidly, and AI can even create art! However, the task you need to solve in this problem is much simpler than painting. Given a picture, you are required to find how many "circles" it contains.
A picture can be abstracted as an $n \times m$ character array $a_{i,j}\ (1\le i\le n, 1\le j\le m)$, which contains only lowercase letters. A pair of positions $(x_1, y_1)$ and $(x_2, y_2)$ in the character array forms a "circle" if they satisfy:
- $1\le x_1 < x_2 \le n, 1\le y_1 < y_2 \le m$.
- $\forall i\in [x_1, x_2], j\in [y_1, y_2], a_{i,y_1}=a_{x_1,j}=a_{x_2,j}=a_{i,y_2}$.
We say there is a "circle" with its top-left corner at $(x_1, y_1)$ and its bottom-right corner at $(x_2, y_2)$. For example, all the bs in the figure below form a circle:
aaaaaaaaaaa
aabbbbbbbaa
aabaaaaabaa
aabaaaaabaa
aabbbbbbbaaPlease output the number of "circles" in the given character array.
Input
The first line contains two positive integers $n$ and $m$.
The next $n$ lines each contain $m$ lowercase letters, where the $j$-th letter of the $i$-th line is $a_{i,j}$.
Output
Output a non-negative integer representing the number of "circles" in the character array.
Examples
Input 1
3 5
zzzzz
zxzxz
zzzzzOutput 1
3Note 1
Below, we have marked the three "circles" in the original image with *:
***zz zz*** *****
*x*xz zx*x* *xzx*
***zz zz*** *****Input 2
See the provided files.
This sample satisfies the properties of Subtask 1.
Input 3
See the provided files.
This sample satisfies the properties of Subtask 1.
Input 4
See the provided files.
This sample satisfies the properties of Subtask 2.
Input 5
See the provided files.
This sample satisfies the properties of Subtask 2.
Input 6
See the provided files.
This sample satisfies the properties of Subtask 2.
Input 7
See the provided files.
This sample satisfies the properties of Subtask 4.
Input 8
See the provided files.
This sample satisfies the properties of Subtask 6.
Constraints
This problem uses bundled testing; you must pass all test cases in a subtask to receive the points for that subtask.
For all test cases, $1\le n, m\le 2000$. The detailed constraints are as follows:
| Subtask ID | $n, m \le$ | Special Property | Score |
|---|---|---|---|
| $1$ | $5$ | All letters in the matrix are randomly generated from ab |
$5$ |
| $2$ | $2000$ | $nm \le 40000$ | $10$ |
| $3$ | Only the letter a exists in the matrix |
$10$ | |
| $4$ | All letters in the matrix are randomly generated from ab |
$15$ | |
| $5$ | $400$ | None | $25$ |
| $6$ | $2000$ | $35$ |