Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n,q= map(int,input().split())
A = list(map(int,input().split()))
C = [list(map(int,input().split())) for i in range(q)]

for i in range(q):
    print(len(set(A[C[i][0]-1:C[i][1]])))

### FIXED CODE ###

import sys
input = sys.stdin.readline
n,q= map(int,input().split())
A = list(map(int,input().split()))
C = [list(map(int,input().split())) + [i] for i in range(q)]
for i in range(q):
    C[i][0] -= 1
    C[i][1] -= 1
for i in range(n):
    A[i] -= 1

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
  
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
  
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

B = Bit(n+1)
ANS = [-1] * q
C.sort(key=lambda x:x[1])
G = [-1] * (max(A)+1)
ind = 0
for i in range(n):
    a = A[i]
    if G[a] != -1:
        # print("ADD", G[a]+1, -1)
        B.add(G[a]+1, -1)
    G[a] = i
    # print("ADD", G[a]+1, 1)
    B.add(G[a]+1, 1)
    while ind < q and C[ind][1] == i:
        # print("SUM", C[ind][1]+1, C[ind][0]+1-1)
        ANS[C[ind][2]] = B.sum(C[ind][1]+1) - B.sum(C[ind][0]+1-1)
        ind += 1

for i in range(q):
    print(ANS[i])
### BUGGY CODE ###

import sys
N,K = map(int,sys.stdin.readline().split())
h = list(map(int,input().split()))
dp = [0]+[float('inf')]*(N-1)

for i in range(1,N):
  
  
    dp[i] = min(abs(h[i]-h[j])+dp[j] for j in range(max(0,i-K),i))
    

print(dp[-1])

### FIXED CODE ###

def main():
    N,K = map(int,input().split())
    h = list(map(int,input().split()))
    dp = [0]*N
    for i in range(1,N):
        dp[i]= min(abs(h[i]-h[j])+dp[j] for j in range(max(0,i-K),i))
    print(dp[-1])
main()
### BUGGY CODE ###

import collections

N = int(input())
S_lis = []

for i in range(N):
  S_lis.append(input())

S_dic = collections.Counter(S_lis)
m = max(S_dic.values())
ans = []

for i in range(len(S_dic)):
  if S_dic.most_common()[i][1] == m:
    ans.append(S_dic.most_common()[i][0])

ans.sort()
for i in ans:
  print(i)

### FIXED CODE ###

from collections import defaultdict

N = int(input())
S_dic = defaultdict(int)

for i in range(N):
  S = input()
  S_dic[S] += 1

m = max(S_dic.values())
max_S = [i[0] for i in S_dic.items() if i[1] == m ]
max_S.sort()
print("\n".join(max_S))
### BUGGY CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

N,M = map(int,read().split())

def solve(N,M):
    if N > M:
        return solve(M,N).T
    H = np.array([[0]], np.int8)
    for i in range(M):
        H = np.tile(H, (2,2))
        H[1<<i:,1<<i:] ^= 1
    H = np.diff(H, axis=0)
    H = np.diff(H, axis=1)
    return (H % 2)[:(1<<N) - 1]

H = solve(N,M)
rows = (''.join(map(str, row)) for row in H)
print('\n'.join(rows))

### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

N,M = map(int,read().split())

def solve(N,M):
    if N > M:
        return solve(M,N).T
    H = np.array([[0]], np.int8)
    for i in range(M):
        H = np.tile(H, (2,2))
        H[1<<i:,1<<i:] ^= 1
    H = np.diff(H, axis=0)
    H = np.diff(H, axis=1)
    return (H % 2)[:(1<<N) - 1]

H = solve(N,M)
size = 0
for row in H:
    word = ''.join(row.astype(str))
    print(word)
### BUGGY CODE ###

N= int(input())
S=input()
r=[]
g=[]
b=[]
A=0
B=0
C=0
for i in range(N):
    if S[i]=="R":
        r.append(i)
        A+=1
    elif S[i]=="G":
        g.append(i)
        B+=1
    else:
        b.append(i)
        C+=1
k=0


for i in range(A):
    x = r[i]
    for j in range(B):

        y=g[j]
        if 2*x-y in b:
            k+=1
        if 2*y-x in b:
            k+=1
        if (x+y)/2 in b:
            k+=1


print(A*B*C-k)

### FIXED CODE ###

N= int(input())
S=input()
r=[]
g=[]
b=[]
A=0
B=0
C=0
for i in range(N):
    if S[i]=="R":
        r.append(i)
        A+=1
    elif S[i]=="G":
        g.append(i)
        B+=1
    else:
        b.append(i)
        C+=1
k=0
for i in range(N-2):
    for j in range(i+1,N-1):
        t=2*j-i
        if t<N:
            if S[i]!=S[j] and S[i]!=S[t] and S[t]!=S[j] :
                k+=1

print(A*B*C-k)
### BUGGY CODE ###

n,q=map(int,input().split())
p=[]
for _ in[0]*n:
 s,k=input().split()
 p+=[[s,int(k)]]
b=[1]*n
t=0
while sum(b):
 for i in range(n):
  a=p[i]
  if b[i]:
   if a[1]>q:a[1]-=q;t+=q
   else:b[i]=0;t+=a[1];print(a[0],t)


### FIXED CODE ###

import sys
from collections import deque
def m():
 s=sys.stdin.readlines()
 q=int(s[0].split()[1])
 f=lambda x,y:(x,int(y))
 d=deque(f(*e.split())for e in s[1:])
 t,a=0,[]
 while d:
  k,v=d.popleft()
  if v>q:v-=q;t+=q;d.append([k,v])
  else:t+=v;a+=[f'{k} {t}']
 print('\n'.join(a))
if'__main__'==__name__:m()
### BUGGY CODE ###

N, M, K = map(int,input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))

sumA = [0]
sumB = [0]
tmp = 0
answer = 0
st = 0

for i in range(N):
    tmp = tmp + A[i]
    sumA.append(tmp)

tmp = 0
for i in range(M):
    tmp = tmp + B[i]
    sumB.append(tmp)

for i in range(N, -1, -1):
    booktmp = 0

    for j in range(st, M + 1):

        if sumA[i] + sumB[j] <= K:
            booktmp = i + j
        else:
            st = j
            break
    answer = max(answer, booktmp)


print(answer)




### FIXED CODE ###

N, M, K = map(int,input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))

sumA = [0]
sumB = [0]
tmp = 0
answer = 0
st = 0

for i in range(N):
    tmp = tmp + A[i]
    sumA.append(tmp)

tmp = 0
for i in range(M):
    tmp = tmp + B[i]
    sumB.append(tmp)

for i in range(N, -1, -1):
    booktmp = 0

    for j in range(st, M + 1):

        if sumA[i] + sumB[j] <= K:
            booktmp = i + j
        else:
            st = j
            break
    answer = max(answer, booktmp)
    if j == M:
        break


print(answer)
### BUGGY CODE ###

import itertools as itr

n, wmax = list(map(int, input().split()))
w = [0]*(n+1)
v = [0]*(n+1)
for i in range(1, n+1):
    wi, vi = list(map(int, input().split()))
    w[i] = wi
    v[i] = vi
    
dp = [[0]*(wmax+1) for _ in range(n+1)]

for i, wi in itr.product(range(1, n+1), range(1, wmax+1)):
    if wi-w[i] >= 0:
        dp[i][wi] = max(dp[i-1][wi], dp[i-1][wi-w[i]]+v[i])
    else:
        dp[i][wi] = dp[i-1][wi]
            
print(dp[n][wmax])

### FIXED CODE ###

import itertools as itr

n, wmax = list(map(int, input().split()))
w = [0]*(n+1)
v = [0]*(n+1)
for i in range(1, n+1):
    wi, vi = list(map(int, input().split()))
    w[i] = wi
    v[i] = vi
    
dp = [[0]*(wmax+1) for _ in range(n+1)]

for i, wi in itr.product(range(1, n+1), range(1, wmax+1)):
    if wi-w[i] >= 0:
        dp[i][wi] = max(dp[i-1][wi], dp[i-1][wi-w[i]]+v[i])
    else:
        dp[i][wi] = dp[i-1][wi]
            
print(dp[n][wmax])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**9)

N = int(input())

L = [0]
l = 0
for i in range(1,10**6) :
    l += i
    L.append(l)
ans = []
while N > 0 :
    for i in range(len(L))  :
        #print(L[i],N,L[i+1])
        if (L[i]+1 <= N <= L[i+1]) :
            ans.append(i+1)
            N -= i+1
            break
    
print(*ans,sep="\n")


### FIXED CODE ###

import sys
import bisect

sys.setrecursionlimit(10**9)

N = int(input())

L = [0]
l = 0
for i in range(1,10**6) :
    l += i
    L.append(l+1)
ans = []
while N > 0 :
    tmp = bisect.bisect(L,N)
    
    ans.append(tmp)
    N -= tmp
    
print(*ans,sep="\n")
### BUGGY CODE ###

n = int(input())
s = list(input())
q = int(input())
for _ in range(q):
  a,b,c = input().split()
  if a=='1':
    s[int(b)-1]=c
  else:
    print(len(set(s[int(b)-1:int(c)])))

### FIXED CODE ###

n=int(input())
l=list(input())
q=int(input())
bit=[[0]*(n+1) for i in range(26)]
def bit_sum(o,i):
  s=0
  while i:
    s+=bit[o][i]
    i-=i&-i
  return s
def bit_add(o,i,x):
  while i<=n:
    bit[o][i] += x
    i+=i&-i
for i in range(n):
  bit_add(ord(l[i])-97,i+1,1)
for i in range(q):
  a,b,c=input().split()
  b=int(b)-1
  if a=='1':
    bit_add(ord(l[b])-97,b+1,-1)
    l[b]=c
    bit_add(ord(c)-97,b+1,1)
  else:
    c=int(c)
    print(sum(1 for o in range(26) if bit_sum(o,c)-bit_sum(o,b)))
### BUGGY CODE ###

n = list(map(int, input().split()))
N, M = n[0], n[1]

import numpy as np

def main():
    M_list = []
    y_array = np.array([[10000000000]*M]*N)
    for i in range(M):
        tmp = list(map(int, input().split()))
        M_list.append(tmp[0])
        y_array[tmp[0]-1,i] = tmp[1]

    num_array = np.zeros([N,M])
    ynum_array = np.ones([N,M])
    for k in range(N):
        #print(np.argsort(y_array[k]))
        #num_array[k,:] = np.argsort(y_array[k])
        #y_sorted = np.sort(y_array)
        a = np.argsort(y_array[k])
        tmp = 1
        for l in a:
            if int(ynum_array[k][l]) == 10000000000:
                break
            ynum_array[k][l] = tmp
            tmp += 1

    for j in range(M):
        ac = (str(M_list[j]).zfill(6)) + (str(int(ynum_array[M_list[j]-1][j])).zfill(6))
        print(ac)
        
    #print(y_array)

if __name__ == '__main__':
    main()




### FIXED CODE ###

n, m = map(int, input().split())

city_list = []
for i in range(m):
    p, y = map(int, input().split())
    city_list.append([p, y, i])

city_list.sort(key=lambda x: (x[0], x[1]))

#print(city_list)

tmp_list = [0]*m
tmp_num = 1
for num,j in enumerate(city_list):
    if num == 0:
        tmp_list[j[2]] = str(j[0]).zfill(6)+str(tmp_num).zfill(6)
        j_tmp = j[0]
        tmp_num += 1
    else:
        if j[0] != j_tmp:
            j_tmp = j[0]
            tmp_num = 1
            tmp_list[j[2]] = str(j[0]).zfill(6)+str(tmp_num).zfill(6)
            tmp_num += 1
        else:
            tmp_list[j[2]] = str(j[0]).zfill(6)+str(tmp_num).zfill(6)
            tmp_num += 1

for k in tmp_list:
    print(k)
### BUGGY CODE ###

from sys import stdout
printn = lambda x: stdout.write(str(x))
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True  and False
BIG = 999999999
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

n = inn()
aa = inl()
a = []
for i in range(n):
    x = []
    for j in range(20):
        x.append((aa[i]>>j)&1)
    a.append(x)
if DBG:
    for i,z in enumerate(a):
        printn(aa[i])
        printn(' ')
        printn(i)
        print(z)
    print("- a -")
cnt = n
c = [a[0][j] for j in range(20)]
s = 1
for i in range(1,n):
    ok = True
    for j in range(20):
        if c[j]==1 and a[i][j]==1:
            ok = False
            break
    ddprint("i {} ok {} c {} s {} cnt {}".format(i,ok,c,s,cnt))
    if ok:
        cnt += s
        s += 1
        for j in range(20):
            c[j] += a[i][j]
    else:
        for j in range(20):
            c[j] += a[i][j]
        #cnt += s*(s-1)//2
        s += 1
        ddprint("mid s {} c {}".format(s,c))
        while s>1:
            if max(c)<=1:
                break
            for j in range(20):
                c[j] -= a[i-s+1][j]
            s -= 1
            ddprint("mid2 s {} c {}".format(s,c))
        cnt += s-1
print(cnt)


### FIXED CODE ###

from sys import stdout
printn = lambda x: stdout.write(str(x))
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True  and False
BIG = 999999999
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

n = inn()
aa = inl()
a = []
for i in range(n):
    x = []
    for j in range(20):
        x.append((aa[i]>>j)&1)
    a.append(x)
if DBG:
    for i,z in enumerate(a):
        printn(aa[i])
        printn(' ')
        printn(i)
        print(z)
    print("- a -")
cnt = n
c = [a[0][j] for j in range(20)]
s = 1
for i in range(1,n):
    ok = True
    for j in range(20):
        if c[j]==1 and a[i][j]==1:
            ok = False
            break
    #ddprint("i {} ok {} c {} s {} cnt {}".format(i,ok,c,s,cnt))
    if ok:
        cnt += s
        s += 1
        for j in range(20):
            c[j] += a[i][j]
    else:
        for j in range(20):
            c[j] += a[i][j]
        #cnt += s*(s-1)//2
        s += 1
        #ddprint("mid s {} c {}".format(s,c))
        while s>1:
            if max(c)<=1:
                break
            for j in range(20):
                c[j] -= a[i-s+1][j]
            s -= 1
            #ddprint("mid2 s {} c {}".format(s,c))
        cnt += s-1
print(cnt)
### BUGGY CODE ###

n, q = map(int, input().split())
s = input()
for _ in range(q):
    l, r = map(int, input().split())
    ss = s[(l - 1):r]
    a = 0
    for i in range(len(ss) - 1):
        if ss[i:(i+2)] == "AC":
            a += 1
    print(a)

### FIXED CODE ###

n, q = map(int, input().split())
s = input()
ss = [0] * n
for i in range(n - 1):
    if s[i:(i+2)] == "AC":
        ss[i] = 1
sss = [0] * n
for i in range(n - 1):
    sss[i + 1] = sss[i] + ss[i]
for _ in range(q):
    l, r  = map(int, input().split())
    print(sss[r - 1] - sss[l - 1])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)

n, m = map(int, input().split())
readline = sys.stdin.readline
a = [int(i) for i in readline().split()]
bc = [[int(i) for i in readline().split()] for _ in range(m)]

import heapq

heapq.heapify(a)

for i in range(m):
    b = bc[i][0]; c = bc[i][1]
    for _ in range(b):
        if a[0] < c:
            _ = heapq.heappop(a)
            heapq.heappush(a, c)
        else:
            break
    
ans = sum(a)
print(ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)

n, m = map(int, input().split())
readline = sys.stdin.readline
A = [int(i) for i in readline().split()]

A.sort()

CB = []
for _ in range(m):
    b, c = [int(i) for i in readline().split()]
    CB.append([c, b])
    
CB.sort(reverse=True)

idx = 0
c = 0
for i in range(n):
    if A[i] < CB[idx][0]:
        A[i] = CB[idx][0]
        c += 1
    if CB[idx][1] <= c:
        idx += 1
        c = 0
    if idx >= m:
        break

print(sum(A))
### BUGGY CODE ###

import itertools,copy
T = input()
TC = list(copy.deepcopy(T))
N = T.count('?')
B = list(itertools.product(['P','D'], repeat=N))
point = []
strs = []
for b in B:
    count = 0
    TC = list(T)
    for j in range(len(T)):
        if TC[j] == '?':
            TC[j] = b[count]
            count += 1
    TC = ''.join(TC)
    strs.append(TC)
    point.append(TC.count('PD') + TC.count('D'))
maxin = max(point)

print(strs[point.index(maxin)])


### FIXED CODE ###

#BBBBBBBBBBB

import sys
import math
import itertools
import collections
import heapq
import numpy as np

rl = sys.stdin.readline

t = rl()
li = []
for i in range(len(t)):
    if t[i] == '?':
        li.append('D')
    else:
        li.append(t[i])
print(''.join(li))
### BUGGY CODE ###

from functools import reduce
from fractions import gcd

n = int(input())
a = [int(i) for i in input().split()]
ans = -1
for i in range(1,n+1):
    ans = max(ans,reduce(gcd,a[:i-1]+a[i:]))
print(ans)


### FIXED CODE ###

from fractions import gcd

n = int(input())
a = [int(i) for i in input().split()]

l = [0]
r = [0]
for i in range(n-1):
    l.append(gcd(l[i],a[i]))
    r.append(gcd(r[i],a[-1-i]))

m = 0
for i in range(n):
    m = max(m,gcd(l[i],r[-i-1]))

print(m)
### BUGGY CODE ###

N = int(input())
'''
data = np.array(input().split(), dtype=np.int64)
'''
def read(): return list(map(int, input().split()))
data = read()

for i in range(1,N+1):
  ans = data.count(i)
  print(ans)

### FIXED CODE ###

from collections import Counter

N = int(input())
data = list(map(int, input().split()))

count = Counter(data)

for i in range(1, N+1):
    ans = count[i]
    print(ans)
### BUGGY CODE ###

import numpy as np

n,k = [int(i) for i in input().split()]
w = []
v = []
for _ in range(n):
    a,b = [int(i) for i in input().split()]
    w.append(a)
    v.append(b)

dp = [[0 for _ in range(k+1)] for _ in range(n+1)]

for i in range(n):
    for j in range(k+1):
        if j >= w[i]:
            dp[i+1][j] = max(dp[i][j-w[i]]+v[i], dp[i][j])
        else:
            dp[i+1][j] = dp[i][j]
print(dp[-1][-1])


### FIXED CODE ###

n,k = [int(i) for i in input().split()]
w = []
v = []
for _ in range(n):
    a,b = [int(i) for i in input().split()]
    w.append(a)
    v.append(b)

dp = [[0 for _ in range(k+1)] for _ in range(n+1)]

for i in range(n):
    for j in range(k+1):
        if j >= w[i]:
            dp[i+1][j] = max(dp[i][j-w[i]]+v[i], dp[i][j])
        else:
            dp[i+1][j] = dp[i][j]
print(dp[-1][-1])
### BUGGY CODE ###

n, X = map(int, input().split())
x = list(map(int, input().split()))
x_sum = [0] # 1-indexed
for i in range(n):
	x_sum.append(x_sum[-1] + x[i])

ans = float("inf")
for i in range(1, n):
	res = X * (i + n)
	res += 5 * (x_sum[-1] - x_sum[-i - 1])
	cost = 5
	j = 1
	while (j * i) + i + 1 <= n:
		#print(-(j * i) - 1, -(j * i) - i - 1)
		res += cost * (x_sum[-(j * i) - 1] - x_sum[-(j * i) - i - 1])
		cost += 2
		j += 1
	res += cost * (x_sum[-(j * i) - 1])

	ans = min(res, ans)

print(ans)

### FIXED CODE ###

n, X = map(int, input().split())
x = list(map(int, input().split()))
x_sum = [0] # 1-indexed
for i in range(n):
	x_sum.append(x_sum[-1] + x[i])

ans = float("inf")
for i in range(1, n):
	res = X * (i + n)
	res += 5 * (x_sum[-1] - x_sum[-i - 1])
	cost = 5
	j = 1
	while (j * i) + i + 1 <= n:
		#print(-(j * i) - 1, -(j * i) - i - 1)
		res += cost * (x_sum[-(j * i) - 1] - x_sum[-(j * i) - i - 1])
		cost += 2
		j += 1
	res += cost * (x_sum[-(j * i) - 1])

	ans = min(res, ans)

print(ans)
### BUGGY CODE ###

n, m = map(int, input().split())

graph = [[0 for i in range(n)] for j in range(n)]

for i in range(m):
    a, b = map(int, input().split())
    graph[a-1][b-1] = 1
    graph[b-1][a-1] = 1

memo = [0 for i in range(n)]
color = [-1 for i in range(n)]
black = 0
white = 0
flag = 0


def search(v):
    for i in range(n):
        if graph[v][i] == 1:
            if memo[i] == 0:
                memo[i] = 1
                color[i] = (color[v]+1) % 2
                if color[i] == 0:
                    global black
                    black += 1
                else:
                    global white
                    white += 1
                search(i)
            else:
                if color[v] == color[i]:
                    global flag
                    flag = 1

memo[0] = 1
color[0] = 0
black += 1
search(0)

if flag == 1:
    print(n*(n-1)//2 - m)
else:
    print(black * white - m)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**8)
n, m = map(int, input().split())

graph = [[] for i in range(n)]

for i in range(m):
    a, b = map(int, input().split())
    graph[a-1].append(b-1)
    graph[b - 1].append(a - 1)

memo = [0 for i in range(n)]
color = [-1 for i in range(n)]
black = 0
white = 0
flag = 0


def search(v):
    for i in graph[v]:
        if memo[i] == 0:
            memo[i] = 1
            color[i] = (color[v] + 1) % 2
            if color[i] == 0:
                global black
                black += 1
            else:
                global white
                white += 1
            search(i)
        else:
            if color[v] == color[i]:
                global flag
                flag = 1

memo[0] = 1
color[0] = 0
black += 1
search(0)

if flag == 1:
    print(n*(n-1)//2 - m)
else:
    print(black * white - m)
### BUGGY CODE ###

x, y, z, k = map(int, input().split())
a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]
c = [int(i) for i in input().split()]
ll = []
if x >= k:
    a = a[k-1:]
if y >= k:
    b = b[k-1:]
if z >= k:
    c = c[k-1:]
for aa in a:
    for bb in b:
        for cc in c:
            ll.append(aa+bb+cc)
ll.sort()
ll = list(reversed(ll))
for i in range(k):
    print(ll[i])

### FIXED CODE ###

x, y, z, k = map(int, input().split())
a = sorted(list(map(int, input().split())), reverse=True)
b = sorted(list(map(int, input().split())), reverse=True)
c = sorted(list(map(int, input().split())), reverse=True)

ans = []
for i in range(x):
    for j in range(y):
        for l in range(z):
            if (i+1) * (j+1) * (l+1) <= k:
                ans.append(a[i] + b[j] + c[l])
            else:
                break

ans.sort(reverse=True)
for i in range(k):
    print(ans[i])
### BUGGY CODE ###

from sys import exit, setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import defaultdict, Counter
from bisect import bisect

def read():
  return int(input())

def reads():
  return [int(x) for x in input().split()]

H, W = reads()
S = []
for _ in range(H):
  S.append(input())

N = H + W
field = [[0] * N for _ in range(N)]
for i in range(H):
  for j in range(W):
    field[i+j][i-j+W] = int(S[i][j] == '#')

accRow = [None] * N
for i in range(N):
  accRow[i] = [0] + list(accumulate(field[i][j] for j in range(N)))

accCol = [None] * N
for i in range(N):
  accCol[i] = [0] + list(accumulate(field[j][i] for j in range(N)))

# for f in field:
#   print(f)

ans = 0
for i in range(N):
  for j in range((i+W)%2, N, 2):
    for k in range(j+2, N, 2):
      d = k - j
      if field[i][j] == field[i][k] == 1:
        if i - d >= 0:
          ans += accRow[i-d][k+1] - accRow[i-d][j]
        if i + d < N:
          ans += accRow[i+d][k+1] - accRow[i+d][j]
      if field[j][i] == field[k][i] == 1:
        if i - d >= 0:
          ans += accCol[i-d][k+1] - accCol[i-d][j]
        if i + d < N:
          ans += accCol[i+d][k+1] - accCol[i+d][j]

for i in range(N):
  for j in range((i+W)%2, N, 2):
    if field[i][j] != 1:
      continue
    for d in range(2, N, 2):
      if i + d < N and j + d < N and field[i][j+d] == field[i+d][j] == 1:
        ans -= 1
      if i + d < N and j - d >= 0 and field[i][j-d] == field[i+d][j] == 1:
        ans -= 1
      if i - d >= 0 and j - d >= 0 and field[i][j-d] == field[i-d][j] == 1:
        ans -= 1
      if i - d >= 0 and j + d < N and field[i][j+d] == field[i-d][j] == 1:
        ans -= 1

print(ans)

### FIXED CODE ###

from sys import exit, setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import defaultdict, Counter
from bisect import bisect

def read():
  return int(input())

def reads():
  return [int(x) for x in input().split()]

H, W = reads()
S = []
for _ in range(H):
  S.append(input())

N = H + W
field = [[0] * N for _ in range(N)]
for i in range(H):
  for j in range(W):
    field[i+j][i-j+W] = int(S[i][j] == '#')

accRow = [None] * N
for i in range(N):
  accRow[i] = [0] + list(accumulate(field[i][j] for j in range(N)))

accCol = [None] * N
for i in range(N):
  accCol[i] = [0] + list(accumulate(field[j][i] for j in range(N)))

# for f in field:
#   print(f)

ans = 0
for i in range(N):
  for j in range((i+W)%2, N, 2):
    for k in range(j+2, N, 2):
      d = k - j
      if field[i][j] == field[i][k] == 1:
        if i - d >= 0:
          ans += accRow[i-d][k+1] - accRow[i-d][j]
        if i + d < N:
          ans += accRow[i+d][k+1] - accRow[i+d][j]
      if field[j][i] == field[k][i] == 1:
        if i - d >= 0:
          ans += accCol[i-d][k] - accCol[i-d][j+1]
        if i + d < N:
          ans += accCol[i+d][k] - accCol[i+d][j+1]

print(ans)