Innokenty works at a flea market and sells some random stuff rare items. Recently he found an old rectangular blanket. It turned out that the blanket is split in $n \cdot m$ colored pieces that form a rectangle with $n$ rows and $m$ columns. 

The colored pieces attracted Innokenty's attention so he immediately came up with the following business plan. If he cuts out a subrectangle consisting of three colored stripes, he can sell it as a flag of some country. Innokenty decided that a subrectangle is similar enough to a flag of some country if it consists of three stripes of equal heights placed one above another, where each stripe consists of cells of equal color. Of course, the color of the top stripe must be different from the color of the middle stripe; and the color of the middle stripe must be different from the color of the bottom stripe.

Innokenty has not yet decided what part he will cut out, but he is sure that the flag's boundaries should go along grid lines. Also, Innokenty won't rotate the blanket. Please help Innokenty and count the number of different subrectangles Innokenty can cut out and sell as a flag. Two subrectangles located in different places but forming the same flag are still considered different. [Image] [Image] [Image]

These subrectangles are flags.  [Image] [Image] [Image] [Image] [Image] [Image]

These subrectangles are not flags. 


-----Input-----

The first line contains two integers $n$ and $m$ ($1 \le n, m \le 1\,000$) — the number of rows and the number of columns on the blanket.

Each of the next $n$ lines contains $m$ lowercase English letters from 'a' to 'z' and describes a row of the blanket. Equal letters correspond to equal colors, different letters correspond to different colors.


-----Output-----

In the only line print the number of subrectangles which form valid flags.


-----Examples-----
Input
4 3
aaa
bbb
ccb
ddd

Output
6

Input
6 1
a
a
b
b
c
c

Output
1



-----Note----- [Image] [Image]

The selected subrectangles are flags in the first example.

Difficulty: interview

Starter code:

Solutions:
from collections import defaultdict as dd
import math
import sys
#input=sys.stdin.readline
def nn():
	return int(input())

def li():
	return list(input())

def mi():
	return list(map(int, input().split()))

def lm():
	return list(map(int, input().split()))

n,m=mi()

quilt=[]
for i in range(n):
	quilt.append(li())
def getflags(column):
	flags=set()
	breaks=[0]
	for i in range(0,len(column)-1):
		if not column[i]==column[i+1]:
			breaks.append(i+1)
	breaks.append(len(column))	
	#print(breaks)
	for j in range(1,len(breaks)-2):
		midlength=breaks[j+1]-breaks[j]
		firstlength=breaks[j]-breaks[j-1]
		endlength=breaks[j+2]-breaks[j+1]
		if midlength<=firstlength and midlength<=endlength:
			flags.add(((breaks[j+1],breaks[j]), (column[breaks[j+1]], column[breaks[j]],column[breaks[j-1]])))
	return flags

flagdicts=[0]*m

for i in range(m):
	col=[row[i] for row in quilt]
	flagdicts[i]=getflags(col)
total=0
#print(flagdicts)
for i in range(m):
	for flag in flagdicts[i]:
		k=1
		
		while i+k<m and flag in flagdicts[i+k]:
			k+=1
			#print(flagdicts[i+k])
			#flagdicts[i+k].remove(flag)
		for j in range(1,k):
			flagdicts[i+j].remove(flag)
		total+=k*(k+1)//2		
print(total)
			












		

















































def main():
    buf = input()
    buflist = buf.split()
    n = int(buflist[0])
    m = int(buflist[1])
    blanket = []
    for i in range(n):
        buf = input()
        blanket.append(buf)
    dp = [[]]
    for j in range(m+1):
        dp[0].append([0, (0, '0'), (0, '0'), (0, '0'), 0])
    for i in range(n):
        dp.append([[0, (0, '0'), (0, '0'), (0, '0'), 0]])
    #dp = [[[0, (0, None), (0, None), (0, None), 0]] * (m+1)] + [[[0, (0, None), (0, None), (0, None), 0]]] * n
    #dp = [[[0, [0, None], [0, None], [0, None], 0]] * (m+1)] * (n+1)
    for i in range(n):
        for j in range(m):
            dp[i+1].append([0, (0, None), (0, None), (0, None), 0])
            dp[i+1][j+1][0] = dp[i+1][j][0] + dp[i][j+1][0] - dp[i][j][0]
            if blanket[i][j] == dp[i][j+1][1][1]:
                dp[i+1][j+1][1] = (dp[i][j+1][1][0]+1, dp[i][j+1][1][1])
                dp[i+1][j+1][2] = dp[i][j+1][2]
                dp[i+1][j+1][3] = dp[i][j+1][3]
            else:
                dp[i+1][j+1][1] = (1, blanket[i][j])
                dp[i+1][j+1][2] = dp[i][j+1][1]
                dp[i+1][j+1][3] = dp[i][j+1][2]
            if dp[i+1][j+1][1][0] == dp[i+1][j+1][2][0] and dp[i+1][j+1][2][0] <= dp[i+1][j+1][3][0]:
                if dp[i+1][j+1][1] == dp[i+1][j][1] and dp[i+1][j+1][2] == dp[i+1][j][2] and dp[i+1][j+1][3][1] == dp[i+1][j][3][1]:
                    dp[i+1][j+1][4] = dp[i+1][j][4]
                dp[i+1][j+1][0] += dp[i+1][j+1][4] + 1
                dp[i+1][j+1][4] += 1
    #for i, x in enumerate(dp):
    #    for j, y in enumerate(x):
    #        print(i, j, y)
    print(dp[n][m][0])

def __starting_point():
    main()

__starting_point()

n,m = list(map(int,input().split()))
A = [input() for _ in range(n)]

Dx = [[0] for _ in range(n)]
Dy = [[0] for _ in range(m)]

for i in range(n):
    last = None
    k = 0
    for j in range(m):
        c = A[i][j]
        if c != last:
            k = 0
        k += 1
        last = c
        Dx[i].append(k)

for j in range(m):
    last = None
    k = 0
    for i in range(n):
        c = A[i][j]
        if c != last:
            k = 0
        k += 1
        last = c
        Dy[j].append(k)

count = 0
for j in reversed(list(range(m))):
    col = Dy[j]
    i = len(col) - 1
    strips = []
    while i != 0:
        strips.append((col[i],i-col[i]))
        i -= col[i]

    for k in range(1,len(strips)-1):
        if strips[k-1][0] >= strips[k][0] <= strips[k+1][0]:
            l = strips[k][1] - strips[k][0]
            r = strips[k-1][1] + strips[k][0]
            #print(strips)
            #print('interval',l,r)
            res = min(Dx[i][j+1] for i in range(l,r))
            #print([Dx[i][j+1] for i in range(l,r)])
            #print(res)
            count += res
    #for 
#print(Dx)
print(count)


H, W = map(int, input().split())
G = [[ord(s)-96 for s in input().strip()] for _ in range(H)]
G = list(map(list, zip(*G)))
A = [None]*W
B = [None]*W
Col = [None]*W
Dic = [None]*W
for j, Gi in enumerate(G):
    pre = -1
    D = [None]*H
    con = 0
    ctr = 0
    E = [None]*H
    F = []
    for i, g in enumerate(Gi):
        if pre != g:
            F.append(con)
            ctr += 1
            con = 0  
        con += 1
        D[i] = con
        pre = g
        E[i] = ctr
    F.append(con)
    Col[j] = E[:]
    Dic[j] = F[:]
    B[j] = D[:]
    pm = 0
    pre = -1
    for i, (g, d) in enumerate(zip(Gi[::-1], D[::-1])):
        if pre != g:
            pm = 0
        pm = max(pm, d)
        D[H-1-i] = pm
        pre = g
    A[j] = D[:]
C = [[0]*H for _ in range(W)]
for w in range(W):
    for h in range(H):
        c = Col[w][h]
        if c + 2 >= len(Dic[w]):
            continue
        leng = A[w][h] + 1 - B[w][h]
        if Dic[w][c+1] == leng and Dic[w][c+2] >= leng:
            C[w][h] = leng * 10**6 + 900 * G[w][h] + 30 * G[w][h+leng] + G[w][h+2*leng]
C = list(map(list, zip(*C)))
ans = 0
for Ci in C:
    ctr = 0
    pre = -1
    for c in Ci:
        if not c:
            pre = -1
            continue
        if c != pre:
            ans += ctr * (ctr + 1)//2
            ctr = 1
        else:
            ctr += 1
        pre = c
    ans += ctr * (ctr + 1)//2
print(ans)

import os
from io import BytesIO, StringIO
#input = BytesIO(os.read(0, os.fstat(0).st_size)).readline

DEBUG = True
debug_print = print if DEBUG else lambda *x,**y: None

def input_as_list():
    return list(map(int, input().split()))

def array_of(f, *dim):
    return [array_of(f, *dim[1:]) for _ in range(dim[0])] if dim else f()

def main():
    n, m = input_as_list()
    g = [input() for _ in range(n)]

    prev_flgs = dict()
    s = 0
    for j in range(m):
        lst = []
        prev = ''
        cnt = 0
        for i in range(n):
            e = g[i][j]
            if e == prev:
                cnt += 1
            else:
                if prev: lst.append((prev, cnt))
                prev = e
                cnt = 1
        lst.append((e, cnt))

        flgs = dict()
        idx = 0
        for i in range(len(lst) - 2):
            f1, f2, f3 = lst[i], lst[i+1], lst[i+2]
            if f1[1] == f2[1] == f3[1]:
                flgs[idx] = [f1[0]+f2[0]+f3[0], f1[1], 1]
            elif min(f1[1], f2[1], f3[1]) == f2[1]:
                flgs[idx+f1[1]-f2[1]] = [f1[0]+f2[0]+f3[0], f2[1], 1]
            idx += f1[1]

        if prev_flgs:
            for f in flgs:
                if f in prev_flgs:
                    fv = flgs[f]
                    pfv = prev_flgs[f]
                    if fv[0] == pfv[0] and fv[1] == pfv[1]:
                        s += pfv[2] + 1
                        flgs[f][2] = pfv[2] + 1
                    else:
                        s += 1
                else:
                    s += 1
        else:
            s += len(flgs)
        prev_flgs = flgs

    print(s)

main()

n,m = [int(i) for i in input().split()]
data = []
for i in range(n):
    data.append(list(input()))
#print(data)
f = []
for i in range(m):
    
    temp = []
    prev = 0
    cnt = 0 #-1?????
    for j in range(n):
        ch = ord(data[j][i]) - 95
        if ch == prev:
            cnt += 1
        else:
            temp.append((prev, cnt, j - cnt))
            prev = ch
            cnt = 1
    temp.append((prev, cnt, n - cnt))
    for t in range(1, len(temp)-1):
        td = temp[t-1]
        tf = temp[t+1]
        te = temp[t]
        if te[0] != td[0] and te[0] != tf[0] and td[1] >= te[1] and tf[1] >= te[1]:
            f.append((te[2],i, te[1], (td[0]<<10) + (te[0]<<5)+tf[0]))

tot = 0
f.sort()
#print(f)

le = len(f)
i = 0
while i < le:
    d = f[i]
    cnt = 1
    #print(d, f[i+1])
    while i < le -1  and d[1] + cnt == f[i+1][1] and d[0] == f[i+1][0] and  d[2] == f[i+1][2] and d[3] == f[i+1][3]:
        i+=1
        cnt+=1
    #print(cnt)
    tot += (cnt*(cnt+1))//2
    i += 1

print(tot)
    


#!/usr/bin/env python
n, m = list(map(int, input().split()))
board = [input() for _ in range(n)]
u = [[1 for _ in range(m)] for _ in range(n)]
l = [[1 for _ in range(m)] for _ in range(n)]
for i in range(1, n):
    for j in range(m):
        if board[i][j] == board[i - 1][j]:
            u[i][j] = u[i - 1][j] + 1
for j in range(1, m):
    for i in range(n):
        if board[i][j] == board[i][j - 1]:
            l[i][j] = l[i][j - 1] + 1
answer = 0
for i1 in range(n):
    for j in range(m):
        k = u[i1][j]
        i2 = i1 - k
        if i2 >= 0 and u[i2][j] == k:
            i3 = i2 - k
            if i3 >= 0 and u[i3][j] >= k:
                answer += min(l[i][j] for i in range(i3 - k + 1, i1 + 1))
print(answer)


import sys 
input = lambda: sys.stdin.readline().strip()

def f(A, r, c, l):
  q, w, e = A[r][c][0], A[r][c-l][0], A[r][c-2*l][0]
  x, y, z = A[r][c][1], A[r][c-l][1], A[r][c-2*l][1]

  #print(r, c, x,y,z,l, q,w,e)
  if x != y and y != z and e >= l and  w == q == l:
    return (l, z, y, x)
  else:
    return 0
  
  



r, c = list(map(int, input().split()))
s = ""
for i in range(r):
  s += input()

arr = []
narr = [[0]*r for i in range(c)]
for i in range(c):
  arr.append(s[i:r*c:c])

r, c = c, r 

length_str = [ [0] * c for i in range(r) ]
for i in range(r):
  for j in range(c):
    if j == 0:
      length_str[i][j] = (1, arr[i][j])
    elif arr[i][j-1] == arr[i][j]:
      length_str[i][j] = (length_str[i][j-1][0] + 1, arr[i][j])
    else:
      length_str[i][j] = (1, arr[i][j])

for i in range(r):
  for j in range(c):
    l, _ = length_str[i][j] 
    if j - l*3 + 1 < 0:
      continue 
    else:
      narr[i][j] = f(length_str, i, j, l)
      




#for i in narr:
#  print(i)

dp =[ [0] * c for i in range(r) ]


for j in range(c):
  cnt = 1
  for i in range(r):
    if narr[i][j] == 0:
      cnt = 1
      continue 
    else:
      if i == 0:
        dp[i][j] = 1

      elif narr[i][j] == narr[i-1][j]:
        cnt += 1
        dp[i][j] = cnt
        dp[i-1][j] = 0

      else:
        cnt = 1
        dp[i][j] = 1 

ans = 0
for i in dp:
  for j in i:
    ans += ((j)*(j+1))//2

print(ans)


import sys


def __starting_point():
    n, m = list(map(int, input().split()))
    arr = sys.stdin.readlines()
    f = 0
    flgs = {}
    for c in range(m):
        cnts = [[arr[0][c], 1]]
        for r in range(1, n):
            if arr[r][c] == cnts[-1][0]:
                cnts[-1][1] += 1
            else:
                cnts.append([arr[r][c], 1])
        strt = 0
        for i in range(len(cnts) - 2):
            if cnts[i][1] >= cnts[i + 1][1] <= cnts[i + 2][1]:
                lng = cnts[i + 1][1]
                beg = strt + cnts[i][1] - cnts[i + 1][1]
                clr = (cnts[i][0], cnts[i + 1][0], cnts[i + 2][0], lng)
                k = (clr, beg)
                if k in flgs and flgs[k][-1][-1] == c - 1:
                    flgs[k][-1][-1] = c
                elif k in flgs:
                    flgs[k].append([c, c])
                else:
                    flgs[k] = [[c, c]]

            strt += cnts[i][1]

    for flg in list(flgs.values()):
        for fl in flg:
            lng = fl[1] - fl[0] + 1
            f += (lng * (lng + 1)) // 2

    print(f)

__starting_point()

a, b = list(map(int,input().split()))
c = [[0] * (b) for i in range(a)]
d = [input() for i in range(a)]
for j in range (b):
    n = []
    pred = d[0][j]
    cnt = 1
    for i in range(1, a):
        if d[i][j] == pred:
            cnt += 1
        else:
            n.append((cnt, pred))
            cnt = 1
        pred = d[i][j]
    n.append((cnt, pred))
    uk = 0
    for i in range(2, len(n)):
        if n[i - 2][0]>= n[i - 1][0] and n[i - 1][0] <= n[i][0]:
            c[uk + n[i - 2][0] - n[i - 1][0]][j] = [n[i - 2][1], n[i - 1][1], n[i][1], n[i - 1][0]]
        uk += n[i - 2][0]
summ = 0
cnt = 0
if b == 1:
    for i in range(a):
        for j in range(b):
            if c[i][j] != 0:
                summ += 1
    print(summ)
    return
for i in range(a):
    cnt = 0
    f = False
    for j in range(1, b):
        if cnt == 0 and c[i][j - 1] != 0:
            cnt = 1
        if c[i][j - 1] == c[i][j] and c[i][j] != 0:
            cnt += 1
        elif c[i][j] != 0:
            summ += cnt * (cnt + 1) // 2
            cnt = 1
        else:
            summ += cnt * (cnt + 1) // 2
            cnt = 0
    summ += cnt * (cnt + 1) // 2
print(summ)


n, m = [int(x) for x in input().split()]

a = [[] * (m+1) for i in range(n+1)]
cols = [[0] * (m+1) for i in range(n+1)]
rows = [[0] * (m+1) for i in range(n+1)]

a[0] = '*' * (m+1)
for i in range(1, n+1):
    a[i] = '*'+input()
    
for i in range(1, n+1):
    for j in range(1, m+1):
        if a[i][j] == a[i][j-1]: 
            rows[i][j] = rows[i][j-1] + 1
            
for i in range(1, n+1):
    for j in range(1, m+1):
        if a[i][j] == a[i-1][j]: 
            cols[i][j] = cols[i-1][j] + 1
            
ans = 0
           
for i in range(1, n+1):
    for j in range(1, m+1):
        x = cols[i][j] + 1
        if i < x*3: 
            continue
        y = cols[i-x][j] + 1
        if x != y:
            continue
        z = cols[i-x-y][j] + 1
        if z < y:
            continue
        minx = 2 * m
        for l in range(0, x*3):
            minx = min(minx, rows[i-l][j])
        #print(i, j, x, y, minx)
        ans += (minx+1)
    
print(ans)


def number_rectangle (h):
    l = [0 for i in range(len(h))]
    stack = []
    dp = [0 for i in range(len(h))]
    result = 0
    for i in range(len(h)):
        while (len(stack) > 0) and (stack[-1] >= h[i]):
            stack.pop()
        if (len(stack) == 0):
            dp[i] = i + 1
        else:
            dp[i] = dp[stack[-1]] + (i - stack[-1]) * h[i]

        result += dp[i]
    #print(h)
    #print(result)
    return result

def main():

    rows, cols = list(map(int, input().split()))
    rows += 1


    a = []
    a.append('-' * cols)
    #print(a)
    for i in range(1, rows):
        a.append(input())
    h = [[0 for j in range(cols)] for i in range(rows)]
    result = 0
    #print(a)
    #print(rows, cols)
    for i in range(1, rows):
        #print (f'i = {i}')
        #print(s)
        #print(a[i])
        last_state = (0, 0, 0, 0, 0, 0)
        same_state = 0
        sub = []
        for j in range(0, cols):
            if a[i][j] == a[i - 1][j]:
                h[i][j] = h[i - 1][j] + 1
            else:
                h[i][j] = 1
            i2 = i - h[i][j]
            i3 = i2 - h[i2][j]
            #print (i, i2, i3)
            curr_state = (h[i][j], h[i2][j], a[i][j], a[i2][j], a[i3][j])
            if (h[i][j] == h[i2][j]) and (h[i3][j] >= h[i][j]):

                if (curr_state == last_state):
                    sub.append(h[i3][j] - h[i][j])
                else:
                    result += number_rectangle(sub)
                    sub.clear()
                    sub.append(h[i3][j] - h[i][j])
            else:
                result += number_rectangle(sub)
                sub.clear()
            last_state = curr_state
            #print (f'same_state = {same_state} curr_state = {curr_state[0], curr_state[1], curr_state[2], curr_state[3], curr_state[4]}')
        result += number_rectangle(sub)
    result = int(result)
    #print(h)
    print(result)
main()




n, m = list(map(int, input().split()))
up = [[0 for j in range(m)] for i in range(n)]
ldw = [[0 for j in range(m)] for i in range(n)]
lup = [[0 for j in range(m)] for i in range(n)]

v = []

for i in range(n):
    v.append(input())

for i in range(n):
    for j in range(m):
        if not i or v[i][j] != v[i - 1][j]:
            up[i][j] = 1
            lup[i][j] = (1 if (not j or v[i][j] != v[i][j - 1]) else lup[i][j - 1] + 1)
        else:
            up[i][j] = up[i - 1][j] + 1
            lup[i][j] = min(lup[i - 1][j], (1 if (not j or v[i][j] != v[i][j - 1]) else lup[i][j - 1] + 1))

for i in range(n - 1, -1, -1):
    for j in range(m):
        if i == n - 1 or v[i][j] != v[i + 1][j]:
            ldw[i][j] = (1 if (not j or v[i][j] != v[i][j - 1]) else ldw[i][j - 1] + 1)
        else:
            ldw[i][j] = min(ldw[i + 1][j], (1 if (not j or v[i][j] != v[i][j - 1]) else ldw[i][j - 1] + 1))

ans = 0

for i in range(1, n - 1):
    for j in range(m):
        if v[i][j] == v[i + 1][j]:
            continue
        h = up[i][j]
        up_st = i - h
        if up_st < 0 or up[up_st][j] < h:
            continue
        dw_st = i + h
        if dw_st >= n or up[dw_st][j] != h:
            continue
        w = min(lup[i][j], ldw[up_st - h + 1][j], lup[dw_st][j])
        ans += w

print(ans)


n, m = list(map(int, input().split()))
a = []
flagTable = [[0] * m] * n
totalFlagNum = 0

def countFlagNum(x):
  y = 0
  flagNum = 0
  while y < m:
    curColor = a[x][y]
    colorCountByX = 1
    isItFlag = True
    while x + colorCountByX < n and a[x + colorCountByX][y] == curColor:
      colorCountByX += 1
    if not(x + colorCountByX * 3 > n):
      color2 = a[x + colorCountByX][y]
      color3 = a[x + colorCountByX * 2][y]
      if color3 != color2 and color2 != curColor:
        offY = 0
        while y + offY < m and isItFlag:
          i = 0
          while i < colorCountByX and isItFlag:
            if (a[x + i][y + offY] != curColor or a[x + colorCountByX + i][y + offY] != color2 or a[x + colorCountByX * 2 + i][y + offY] != color3):
              isItFlag = False
              if offY == 0:
                offY = 1
            i += 1
          if isItFlag:
            flagNum = flagNum + 1 + offY
            offY += 1
        y += offY - 1
    y += 1
  return flagNum

def markFlag():
  return 0

for i in range(n):
  row = input()
  a.append(row)

for i in range(n - 2):
    totalFlagNum += countFlagNum(i)

print(totalFlagNum)



def countFlagNum(x):
  y = 0
  flagNum = 0
  while y < m:
    curColor = a[x][y]
    colorCountByX = 1
    isItFlag = True
    while x + colorCountByX < n and a[x + colorCountByX][y] == curColor:
      colorCountByX += 1
    if not(x + colorCountByX * 3 > n):
      color2 = a[x + colorCountByX][y]
      color3 = a[x + colorCountByX * 2][y]
      if color3 != color2 and color2 != curColor:
        offY = 0
        while y + offY < m and isItFlag:
          i = 0
          while i < colorCountByX and isItFlag:
            if (a[x + i][y + offY] != curColor or a[x + colorCountByX + i][y + offY] != color2 or a[x + colorCountByX * 2 + i][y + offY] != color3):
              isItFlag = False
              if offY == 0:
                offY = 1
            i += 1
          if isItFlag:
            flagNum = flagNum + 1 + offY
            offY += 1
        y += offY - 1
    y += 1
  return flagNum

n, m = list(map(int, input().split()))
a = []
totalFlagNum = 0

for i in range(n):
  row = input()
  a.append(row)

for i in range(n - 2):
    totalFlagNum += countFlagNum(i)

print(totalFlagNum)


n, m = list(map(int, input().split()))
grid = []
d = {}
flags = 0
for i in range(n):
    grid.append(input())
for j in range(m):
    b = 0
    while b < n - 1:
        i = b
        k = i
        while k < n and grid[k][j] == grid[i][j]:
            k += 1
        c1 = k - i
        clr1 = grid[k - 1][j]
        i = k
        if 2 * c1 <= n - k:
            while k < n and grid[k][j] == grid[i][j]:
                k += 1
            c2 = k - i
            clr2 = grid[k - 1][j]
            i = k
            if c1 == c2 and c2 <= n - k:
                while k < n and grid[k][j] == grid[i][j]:
                    k += 1
                    if k - i == c2:
                        break
                c3 = k - i
                clr3 = grid[k - 1][j]
                if c3 == c2:
                    flags += 1
                    if (c3, clr1, clr2, clr3, k - 2 * c3 - 1, k - 1) in d and \
                            d[(c3, clr1, clr2, clr3, k - 2 * c3 - 1, k - 1)][1] == (j - 1):
                        flags += d[(c3, clr1, clr2, clr3, k - 2 * c3 - 1, k - 1)][0]
                        d[(c3, clr1, clr2, clr3, k - 2 * c3 - 1, k - 1)][1] = j
                        d[(c3, clr1, clr2, clr3, k - 2 * c3 - 1, k - 1)][0] += 1
                    else:
                        d[(c3, clr1, clr2, clr3, k - 2 * c3 - 1, k - 1)] = [1, j]
        b += 1
print(flags)



n, m = list(map(int, input().split()))
board = [input() for _ in range(n)]

u = [[1 for _ in range(m)] for _ in range(n)]
l = [[1 for _ in range(m)] for _ in range(n)]

for i in range(1, n):
    for j in range(m):
        if board[i][j] == board[i - 1][j]:
            u[i][j] = u[i - 1][j] + 1

for j in range(1, m):
    for i in range(n):
        if board[i][j] == board[i][j - 1]:
            l[i][j] = l[i][j - 1] + 1

output = 0
for i1 in range(n):
    for j in range(m):
        k = u[i1][j]
        
        i2 = i1 - k
        
        if i2 >= 0 and u[i2][j] == k:
            i3 = i2 - k
            if i3 >= 0 and u[i3][j] >= k:
                output += min(l[i][j] for i in range(i3 - k + 1, i1 + 1))
                
                
print(output)
        
        




def test_c(n, m, G):
    #n, m = [int(x) for x in input().split()]
    #G = []
    #for i in range(n):
    #    G.append(list(input()))
    mid = [[False for i in range(m)] for j in range(n)]
    vis = [[False for i in range(m)] for j in range(n)]
    L = [[1 for i in range(m)] for j in range(n)]

    for i in range(1, n):
        for j in range(m):
            if G[i][j] != G[i-1][j]:
                mid[i][j] = True

    for j in range(m):
        for i in range(n):
                if i >= 1 and G[i][j] == G[i-1][j]:
                    L[i][j] = L[i-1][j] - 1
                    continue

                k = 0
                while i+k < n and G[i][j] == G[i+k][j]:
                    k += 1
                L[i][j] = k

    cnt = 0
    for i in range(n):
        for j in range(m):
            if mid[i][j] == True and vis[i][j] == False:
                if i - L[i][j] >= 0 and i + L[i][j] < n:
                    if L[i-L[i][j]][j] == L[i][j] and L[i+L[i][j]][j] >= L[i][j]: #单条L*1的flag
                        #cnt += 1
                        k = 1
                        vis[i][j] = True
                        while j+k < m and G[i][j] == G[i][j+k] and L[i][j] == L[i][j+k] and mid[i][j+k] == True:
                            if L[i - L[i][j]][j+k] == L[i][j] and G[i - L[i][j]][j+k] == G[i - L[i][j]][j] and\
                               L[i + L[i][j]][j+k] >= L[i][j] and G[i + L[i][j]][j+k] == G[i + L[i][j]][j]:
                                vis[i][j + k] = True
                                k += 1
                                #cnt += 1
                            else:
                                break
                        cnt += int(((k+1)*k) // 2)

    print(cnt)


def __starting_point():

    n, m = [int(x) for x in input().split()]
    G = []
    for i in range(n):
        G.append(list(input()))
    mid = [[False for i in range(m)] for j in range(n)]
    vis = [[False for i in range(m)] for j in range(n)]
    L = [[1 for i in range(m)] for j in range(n)]

    for i in range(1, n):
        for j in range(m):
            if G[i][j] != G[i-1][j]:
                mid[i][j] = True

    for j in range(m):
        for i in range(n):
                if i >= 1 and G[i][j] == G[i-1][j]:
                    L[i][j] = L[i-1][j] - 1
                    continue

                k = 0
                while i+k < n and G[i][j] == G[i+k][j]:
                    k += 1
                L[i][j] = k

    cnt = 0
    for i in range(n):
        for j in range(m):
            if mid[i][j] == True and vis[i][j] == False:
                if i - L[i][j] >= 0 and i + L[i][j] < n:
                    if L[i-L[i][j]][j] == L[i][j] and L[i+L[i][j]][j] >= L[i][j]: #单条L*1的flag
                        #cnt += 1
                        k = 1
                        vis[i][j] = True
                        while j+k < m and G[i][j] == G[i][j+k] and L[i][j] == L[i][j+k] and mid[i][j+k] == True:
                            if L[i - L[i][j]][j+k] == L[i][j] and G[i - L[i][j]][j+k] == G[i - L[i][j]][j] and\
                               L[i + L[i][j]][j+k] >= L[i][j] and G[i + L[i][j]][j+k] == G[i + L[i][j]][j]:
                                vis[i][j + k] = True
                                k += 1
                                #cnt += 1
                            else:
                                break
                        cnt += int(((k+1)*k) // 2)

    print(cnt)
__starting_point()

from sys import stdin, stdout

n,m = list(map(int, stdin.readline().split()))
t = [[0 for i in range(m)] for j in range(n)]

for i in range(n):
    s = stdin.readline().strip()
    for j,c in enumerate(s):
        t[i][j] = c

begins = [[False for i in range(m)] for j in range(n)]
lens = [[0 for i in range(m)] for j in range(n)]

for j in range(m):
    cur_len = 1
    run_start = 0
    for i in range(1,n):
        if t[i-1][j] != t[i][j]:
            begins[run_start][j] = True
            for z in range(run_start, i):
                lens[z][j] = cur_len - (z-run_start)
            cur_len = 0
            run_start = i
        cur_len += 1
    begins[run_start][j] = True
    for z in range(run_start, n):
        lens[z][j] = cur_len - (z-run_start)

#print(begins)
#print(lens)
done = [[False for i in range(m)] for j in range(n)]
ans = 0
for j in range(m):
    for i in range(n):
        if done[i][j]:
            continue
        l = lens[i][j]
        if i+2*l >= n:
            continue
        if not begins[i+l][j] or lens[i+l][j] != l or not begins[i+2*l][j] or lens[i+2*l][j] < l:
            continue
        num_cols = 1
        cur_j = j
        while cur_j < m and lens[i][cur_j] == l and begins[i+l][cur_j] and lens[i+l][cur_j] == l and begins[i+2*l][cur_j]and lens[i+2*l][cur_j] >= l and t[i][cur_j] == t[i][j] and t[i+l][cur_j] == t[i+l][j] and t[i+2*l][cur_j] == t[i+2*l][j]:
            done[i][cur_j] = True 
            cur_j += 1
        num_cols = cur_j - j

        ans += num_cols*(num_cols+1) // 2

print(ans)        



import sys
import math
from collections import defaultdict,deque
import heapq
n,m=list(map(int,sys.stdin.readline().split()))
grid=[]
for i in range(n):
	s=sys.stdin.readline()[:-1]
	grid.append(s)
right=[[0 for _ in range(m)] for x in range(n)]
for i in range(n):
	l,r,cnt=0,0,0
	while r<m:
		cnt=0
		while r<m and grid[i][l]==grid[i][r]:
			cnt+=1
			r+=1
		while l<r:
			right[i][l]=cnt
			cnt-=1
			l+=1
'''for i in range(n):
	print(right[i])'''
down=[[0 for _ in range(m)] for x in range(n)]
for i in range(m):
	l,r,cnt=0,0,0
	while r<n:
		cnt=0
		while r<n and grid[l][i]==grid[r][i]:
			cnt+=1
			r+=1
		while l<r:
			down[l][i]=cnt
			cnt-=1
			l+=1
'''for i in range(n):
	print(down[i],'down')'''
ans=0
for i in range(n):
	for j in range(m):
		x=down[i][j]
		y=0
		if i+x<n:
			y=down[i+x][j]
		z=0
		if i+x+y<n:
			z=down[i+x+y][j]
		if x==y and z>=y:
			#print(x,'x',y,'y',z,'z',i,'i',j,'j')
			minn=right[i][j]
			for k in range(i,i+3*x):
				minn=min(minn,right[k][j])
			#print(minn,'minn')
			#print(i,'i',j,'j')
			ans+=minn
print(ans)