Carousel Boutique is busy again! Rarity has decided to visit the pony ball and she surely needs a new dress, because going out in the same dress several times is a sign of bad manners. First of all, she needs a dress pattern, which she is going to cut out from the rectangular piece of the multicolored fabric.

The piece of the multicolored fabric consists of $n \times m$ separate square scraps. Since Rarity likes dresses in style, a dress pattern must only include scraps sharing the same color. A dress pattern must be the square, and since Rarity is fond of rhombuses, the sides of a pattern must form a $45^{\circ}$ angle with sides of a piece of fabric (that way it will be resembling the traditional picture of a rhombus).

Examples of proper dress patterns: [Image] Examples of improper dress patterns: [Image] The first one consists of multi-colored scraps, the second one goes beyond the bounds of the piece of fabric, the third one is not a square with sides forming a $45^{\circ}$ angle with sides of the piece of fabric.

Rarity wonders how many ways to cut out a dress pattern that satisfies all the conditions that do exist. Please help her and satisfy her curiosity so she can continue working on her new masterpiece!


-----Input-----

The first line contains two integers $n$ and $m$ ($1 \le n, m \le 2000$). Each of the next $n$ lines contains $m$ characters: lowercase English letters, the $j$-th of which corresponds to scrap in the current line and in the $j$-th column. Scraps having the same letter share the same color, scraps having different letters have different colors.


-----Output-----

Print a single integer: the number of ways to cut out a dress pattern to satisfy all of Rarity's conditions.


-----Examples-----
Input
3 3
aaa
aaa
aaa

Output
10

Input
3 4
abab
baba
abab

Output
12

Input
5 5
zbacg
baaac
aaaaa
eaaad
weadd

Output
31



-----Note-----

In the first example, all the dress patterns of size $1$ and one of size $2$ are satisfactory.

In the second example, only the dress patterns of size $1$ are satisfactory.

Difficulty: interview

Starter code:

Solutions:
n,m=map(int,input().split())
L=[]
for i in ' '*n:L.append(input())
dp=[[0]*m for i in range(n)]
for i in range(n+m-1):
    rightmin=max(0,i-(n-1))
    leftmin=max(0,i-(m-1))
    left=i-rightmin
    jstart = max(0, i - (n - 1))
    for j in range(abs(left-leftmin)+1):
        jj=jstart+j
        ii=i-jj
        if jj<2 or ii<1 or ii==n-1:
            dp[ii][jj]=1
            continue
        if L[ii+1][jj-1]==L[ii][jj-1]==L[ii][jj-2]==L[ii-1][jj-1]==L[ii][jj]:
            dp[ii][jj]=min(dp[ii+1][jj-1],dp[ii][jj-1],dp[ii][jj-2],dp[ii-1][jj-1])+1
        else:dp[ii][jj]=1
ct=0
for i in dp:
    for j in i:
        ct+=j
print(ct)

import sys
input = sys.stdin.readline

n,m=list(map(int,input().split()))
MAP=[input().strip() for i in range(n)]

COUNT0=[[1]*m for i in range(n)]
COUNT1=[[1]*m for i in range(n)]
COUNT2=[[1]*m for i in range(n)]
COUNT3=[[1]*m for i in range(n)]

for i in range(1,n-1):
    for j in range(1,m-1):
        if MAP[i][j]==MAP[i-1][j]==MAP[i][j-1]:
            COUNT0[i][j]=min(COUNT0[i-1][j],COUNT0[i][j-1])+1

for i in range(n-2,0,-1):
    for j in range(m-2,0,-1):
        if MAP[i][j]==MAP[i+1][j]==MAP[i][j+1]:
            COUNT1[i][j]=min(COUNT1[i+1][j],COUNT1[i][j+1])+1

for i in range(1,n-1):
    for j in range(m-2,0,-1):
        if MAP[i][j]==MAP[i-1][j]==MAP[i][j+1]:
            COUNT2[i][j]=min(COUNT2[i-1][j],COUNT2[i][j+1])+1

for i in range(n-2,0,-1):
    for j in range(1,m-1):
        if MAP[i][j]==MAP[i+1][j]==MAP[i][j-1]:
            COUNT3[i][j]=min(COUNT3[i+1][j],COUNT3[i][j-1])+1

ANS=0
for i in range(n):
    for j in range(m):
        ANS+=min(COUNT0[i][j],COUNT1[i][j],COUNT2[i][j],COUNT3[i][j])

print(ANS)




def tc():
    n, m = list(map(int, input().split()))
    mat = [input() for _ in range(n)]
    alpha = 'abcdefghijklmnopqrstuvwxyz'

    dp = [[0] * m for _ in range(n)]
    ans = 0
    for i in range(n):
        for j in range(m):

            if j == 0 or j == m - 1 or i < 2:
                dp[i][j] = 1
            elif mat[i][j] == mat[i - 1][j] and mat[i][j] == mat[i - 1][j - 1] and mat[i][j] == mat[i - 1][j + 1] and mat[i][j] == mat[i - 2][j]:
                dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - 1], dp[i - 1][j + 1], dp[i - 2][j]) + 1
            else:
                dp[i][j] = 1
            ans += dp[i][j]

    print(ans)


#################
tc()