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

s = input()
q = int(input())
queries = []
for _ in range(0, q):
    query = input()
    if len(query) == 1:
        queries.append([int(query)])
    else:
        query = query.split(' ')
        query = [int(query[0]), int(query[1]), query[2]]
        queries.append(query)

for i in range(0, q):
    if queries[i][0] == 1:
        s = s[::-1]
    else:
        if queries[i][1] == 1:
            s = queries[i][2] + s
        else:
            s = s + queries[i][2]

print(s)

### FIXED CODE ###

#import sys
#input = sys.stdin.readline

def main():
    s = input()
    q = int(input())
    is_rev = False
    l = ''
    r = ''
    for _ in range(0, q):
        query = input()
        if len(query) == 1:
            is_rev = not is_rev
        else:
            query = query.split(' ')
            query = [int(query[0]), int(query[1]), query[2]]
            if (query[1] == 1 and is_rev) or (query[1] == 2 and not is_rev):
#                s = s + query[2]
                r += query[2]
            else:
#                s = query[2] + s
                l += query[2]
    if is_rev:
        print(r[::-1] + s[::-1] + l)
    else:
        print(l[::-1] + s + r)

main()
### BUGGY CODE ###

n,m=map(int,input().split())
x=list(map(int,input().split()))
xmod=[y%m for y in x]
from collections import Counter
cx=dict(Counter(xmod))
keys=list(cx.keys())
keys.sort()
ans1,ans2=0,0 # m倍になるペア、同数のペア
d2={}
for k in keys:
  if k==0:
    ans1+=cx[k]//2
    cx[k]-=2*(cx[k]//2)
  else:
    if k==m-k:
      ans1+=cx[k]//2
      cx[k]-=2*(cx[k]//2)
    elif m-k in keys:
      tmp=min(cx[k],cx[m-k])
      ans1+=tmp
      cx[k]-=tmp
      cx[m-k]-=tmp
    if cx[k]>=2:
      ans2+=cx[k]//2
      d2[k]=cx[k]//2
d1={}
for y in x:
  if y%m in d1:
    d1[y%m].append(y)
  else:
    d1[y%m]=[y]
d3={}
for k in d1:
  tmp={}
  d3[k]=0
  for i in d1[k]:
    if i in tmp:
      tmp[i]+=1
      if tmp[i]%2==0:
        d3[k]+=1
    else:
      tmp[i]=1

for k in d2:
  tmp=d3[k]
  if tmp>=d2[k]:
    pass
  else:
    ans2-=d2[k]
    ans2+=tmp
print(ans1+ans2)

### FIXED CODE ###

def main():
  n,m=map(int,input().split())
  x=list(map(int,input().split()))
  #xmod=[y%m for y in x]
  from collections import Counter
  cx=Counter(x)
  cxmod={}
  for k in cx:
    if k%m in cxmod:
      cxmod[k%m]+=cx[k]
    else:
      cxmod[k%m]=cx[k]
  keys=cxmod.keys()
  ans1,ans2=0,0 # ams1:m倍になるペア、ans2:同数のペア。ans1からもとめる
  for k in keys:
    if k==0:
      ans1+=cxmod[k]//2
      cxmod[k]-=2*(cxmod[k]//2)
    else:
      if k==m-k:
        ans1+=cxmod[k]//2
        cxmod[k]-=2*(cxmod[k]//2)
      elif m-k in keys:
        tmp=min(cxmod[k],cxmod[m-k])
        ans1+=tmp
        cxmod[k]-=tmp
        cxmod[m-k]-=tmp
  for k in cx:
    v=cx[k]
    if v>=2 and cxmod[k%m]>=2:
      tmp=min(v//2,cxmod[k%m]//2)
      ans2+=tmp
      cxmod[k%m]-=tmp*2

  print(ans1+ans2)
if __name__=='__main__':
  main()
### BUGGY CODE ###

def main():
    n,m = (int(x) for x in input().split())
    h = [int(x) for x in input().split()]
    route = [[False]*n for _ in range(n)]
    for i in range(m):
        a,b = (int(x)-1 for x in input().split())
        route[a][b], route[b][a] = True, True

    good = []
    for i in range(n):
        ch = h[i]
        for j in range(n):
            if route[i][j] and h[j] >= ch:
                break
        else:
            good.append(i)

    print(len(set(good)))

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    n,m = (int(x) for x in input().split())
    h = [int(x) for x in input().split()]
    r = [[h[i]] for i in range(n)]
    for i in range(m):
        a,b = (int(x)-1 for x in input().split())
        r[a].append(h[b])
        r[b].append(h[a])

    cnt = 0
    for i in range(n):
        if max(r[i]) == h[i] and r[i].count(h[i]) == 1:
            cnt += 1
    print(cnt)

if __name__ == '__main__':
    main()
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
dlt=0
already=[]
for i in a:
  if(i not in already):
    already.append(i)
    j=a.count(i)
    if(j>i):dlt+=j-i
    elif(i>j):dlt+=j

print(dlt)


### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
dlt=0
push=0
a.sort()
k=0
while(1):
  i=a[k+push]
  if(i>n):
    dlt+=1
    push+=1
  else:
    j=a.count(i)
    push+=j
    if(j>i):dlt+=j-i
    elif(i>j):dlt+=j
  if(k+push>=n):break
print(dlt)
### BUGGY CODE ###

N = int(input())
R = sorted([list(map(int, input().split())) for i in range(N)])
T = []
for i in range(N):
    T.append([R[i][0] + R[i][1], R[i][0] - R[i][1]])
T.sort()
while len(T) - 1 > 0:
    t = T.pop(0)
    i = 1
    while len(T) and t[0] > T[0][1]:
        N -= 1
        i += 1
        T.pop(0)
print(N)

### FIXED CODE ###

N = int(input())
X = [list(map(int, input().split())) for i in range(N)]
LR = [[x[0]-x[1], x[0] + x[1]] for x in X]
LR.sort(key=lambda x:x[1])

A = 1
right = LR[0][1]
for i in range(1, N):
    if right <= LR[i][0]:
        A += 1
        right = LR[i][1]
print(A)
### BUGGY CODE ###

N, M = map(int, input().split())
H = [int(i) for i in input().split()]

roads = [[int(i) for i in input().split()] for j in range(M)]
roads2 = [[] for i in range(N)]

for spots in roads:
    roads2[spots[0]-1].append(spots[1])
    roads2[spots[1]-1].append(spots[0])

memo = []
def search(i, memo):
    memo.append(i)
    for spot in roads2[i-1]:
        if H[i-1] <= H[spot-1]:
            return 0
        
        if spot not in memo:
            search(spot, memo)
            memo.pop()
    return 1

ans = 0
for i in range(1, N+1):
    ans += search(i, memo)

print(ans)

### FIXED CODE ###

N, M = map(int, input().split())
H = [int(i) for i in input().split()]

roads = [[int(i) for i in input().split()] for j in range(M)]
roads2 = [[] for i in range(N)]

for spots in roads:
    roads2[spots[0]-1].append(spots[1])
    roads2[spots[1]-1].append(spots[0])

ans = 0
for spot in range(1, N+1):
    good = True
    for i in roads2[spot-1]:
        if H[spot-1] <= H[i-1]:
            good = False
            break
    if good:
        ans += 1

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

N, K = map(int, input().split())
h = list(map(int, input().split()))
dp = [float("inf") for _ in range(N)]
dp[0] = 0
for i in range(N):
	for j in range(K):
		if i - K + j >= 0:
			dp[i] = min(dp[i], dp[i - K + j] + abs(h[i] - h[i - K + j]))
print(dp[N - 1])


### FIXED CODE ###

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

def main():
  import numpy as np
  inp1 = input()
  inp2 = input().split()

  a = int(inp1)
  b = np.array(inp2).astype(int)
  ansno = a

  for ii,i in enumerate(b):
    bslice = b[:ii+1]
    minb = np.min(bslice)
    if minb == i:
      pass
    else:
      ansno -=1

  print(ansno)
if __name__ == '__main__':
  main()

### FIXED CODE ###

n = int(input())
m = input().split()
ppp = list(map(int, m))
max = 2*10**5+1
ans = 0
for p in ppp:
    if p < max:
        ans += 1
        max = p
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
import heapq
INF = float("inf")


def solve(N: int, A: "List[int]", B: "List[int]"):

    lh = []
    for i in range(N):
        heapq.heappush(lh, [-B[i], i])

    count = 0
    while len(lh) > 0:
        b, i = heapq.heappop(lh)
        if B[i]-B[(i+1) % N]-B[i-1] >= 0 and B[i] > A[i]:
            d, m = divmod(B[i]-A[i], (B[(i+1) % N]+B[i-1]))
            count += d
            B[i] = A[i]+m
            if A[i] < B[i]:
                heapq.heappush(lh, [-B[i], i])
    # print(*A)
    # print(*B)
    for i in range(N):
        if A[i] != B[i]:
            print(-1)
            return

    print(count)
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    B = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A, B)


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
# import heapq


def solve(N: int, A: "List[int]", B: "List[int]"):

    count = 0
    flag = True
    while flag:
        flag = False
        for i in range(N):
            a, b, c = B[i-1], B[i], B[(i+1) % N]
            if b > A[i] and b > a+c:
                d, m = divmod(b-A[i], a+c)
                if m == 0:
                    B[i] = A[i]
                    count += d
                else:
                    d, m = divmod(b, a+c)
                    count += d
                    B[i] = m
                flag = True
    # print(*A)
    # print(*B)
    if A != B:
        count = -1

    print(count)
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    B = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A, B)


if __name__ == '__main__':
    main()
### BUGGY CODE ###

from itertools import product

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()]

a1 = []
for i, j in product(A, B):
    a1.append(i + j)
a1.sort(reverse=True)

ans_list = []
for i, j in product(a1[0:min(X*Y*Z, 3000)], C):
    ans_list.append(i + j)
ans_list.sort(reverse=True)

for i in range(K):
    print(ans_list[i])

### FIXED CODE ###

from itertools import product

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()]

A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)

a = []
count = 0
for i in range(X):
    for j in range(Y):
        if (i+1)*(j+1) > K:
            break
        for k in range(Z):
            if (i+1)*(j+1)*(k+1) > K:
                break
            a.append(A[i] + B[j] + C[k])

a.sort(reverse=True)

for i in range(K):
    print(a[i])
### BUGGY CODE ###

S=list(input())

c=0
cc=3
tmp=[]
while c!=cc:
    cc=c
    for i in range(len(S)-1):
        if S[i]!=S[i+1] and S[i]!='2':
            S[i]='2'
            S[i+1]='2'
            c+=2

    while S:
        e=S.pop()
        if e!='2':
            tmp.append(e)
    while tmp:
        S.append(tmp.pop())

print(c)

### FIXED CODE ###

S=input()

c0=0

for i in range(len(S)):
    if S[i]=='0':
        c0+=1

if len(S)>c0*2:
    print(2*c0)
else:
    print((len(S)-c0)*2)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def main():
  h, w, k = map(int, input().split())
  U = h*w
  G = [0]*U
  for _ in range(k):
    r, c, v = map(int, input().split())
    r -= 1
    c -= 1
    G[r*w+c] = v
  dp = [[0]*4 for _ in range(U)]
  dp[0][0] = 0
  dp[0][1] = G[0]
  for i in range(h):
    for j in range(w):
      if j:
        dp[i*w+j][0] = dp[i*w+j-1][0]
        for k in range(1, 4):
          dp[i*w+j][k] = max(dp[i*w+j][k], dp[i*w+j-1][k-1]+G[i*w+j], dp[i*w+j-1][k])
      if i:
        temp = max(dp[(i-1)*w+j])
        dp[i*w+j][0] = max(dp[i*w+j][0], temp)
        dp[i*w+j][1] = max(dp[i*w+j][1], temp+G[i*w+j])
  ans = max(dp[U-1])
  print(ans)
if __name__ == "__main__":
  main()

### FIXED CODE ###

import sys
input = sys.stdin.readline

h, w, k = map(int, input().split())
G = [[0]*w for _ in range(h)]
for _ in range(k):
  r, c, v = map(int, input().split())
  r -= 1
  c -= 1
  G[r][c] = v
dp = [[[0]*w for i in range(h)] for j in range(4)]
dp[0][0][0] = 0
dp[1][0][0] = G[0][0]
for i in range(h):
  for j in range(w):
    if j:
      dp[0][i][j] = dp[0][i][j-1]
      for k in range(1, 4):
        dp[k][i][j] = max(dp[k][i][j], dp[k-1][i][j-1]+G[i][j], dp[k][i][j-1])
    if i:
      dp[0][i][j] = max(dp[0][i][j], max(dp[0][i-1][j],dp[1][i-1][j],dp[2][i-1][j],dp[3][i-1][j]))
      dp[1][i][j] = max(dp[1][i][j], max(dp[0][i-1][j],dp[1][i-1][j],dp[2][i-1][j],dp[3][i-1][j])+G[i][j])
ans = max(dp[0][h-1][w-1],dp[1][h-1][w-1],dp[2][h-1][w-1],dp[3][h-1][w-1])
print(ans)
### BUGGY CODE ###

def f(a,n,ans1,p1,p2,flag):
    if p1>p2:
        return 0
   
    return max(a[p1]+min(f(a,n,ans1,p1+2,p2,flag+1),f(a,n,ans1,p1+1,p2-1,flag+1))
                      ,a[p2]+min(f(a,n,ans1,p1+1,p2-1,flag+1),f(a,n,ans1,p1,p2-2,flag+1)))
n=int(input())
a=list(map(int,input().split()))
s=sum(a)
p1=0
p2=n-1
first=f(a,n,0,p1,p2,2)
print(first-(s-first))
                             


### FIXED CODE ###

def f(a,i,j,dp):
    if dp[i][j]==-1:
        if i>j:
            return 0

        dp[i][j]=max(a[i]+min(f(a,i+2,j,dp),f(a,i+1,j-1,dp)),
                                a[j]+min(f(a,i+1,j-1,dp),f(a,i,j-2,dp)))
    return dp[i][j]
        
n=int(input())
dp=[[-1 for i in range(n)] for j in range(n)]
a=list(map(int,input().split()))
for i in range(n):
    dp[i][i]=a[i]

for i in range(n-1):
    dp[i][i+1]=max(a[i],a[i+1])

s1=f(a,0,n-1,dp)

print(s1-sum(a)+s1)
### BUGGY CODE ###

S = input()[::-1]
length = len(S)
T = []

if S[0] == "?":
    T.append("D")
else:
    T.append(S[0])

for i in range(1, length):
    if S[i] == "?":           
        if T[-1] == "D":
            T.append("P")
        else:
            T.append("D")
    else:
        T.append(S[i])

ans = ""
T = T[::-1]
for i in range(length):
    ans += T[i]
print(ans)

### FIXED CODE ###

S = input()
S = S.replace("?", "D")
print(S)
### BUGGY CODE ###

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors

N = int(input())
A = list(map(int, input().split()))
ANS = [0]*len(A)
sum=0
ansList = []
for i in range(len(A),0,-1):
    if(ANS[i-1]%2!=A[i-1]):
        tList = make_divisors(i)
        for j in tList:
            ANS[j-1]+=1
        ansList.append(i)
print(len(ansList))

for i in ansList:
    print(i, end=" ")


### FIXED CODE ###

import math as math

N = int(input())
A = list(map(int, input().split()))
ANS = [0]*len(A)
for i in range(math.floor(N/2)+1,N):
    ANS[i] = A[i]

fnum=math.floor(N/2)
for i in range(fnum,-1,-1):
    j = i + 1
    tsum=A[i]
    for k in range(j,N+1,j):
        tsum+=ANS[k-1]
    ANS[i]=tsum%2

#print(ANS)
anslist=[]
for i in range(N):
    if ANS[i]==1:
        anslist.append(i+1)
 
print(len(anslist))
for s in anslist:
    print(s, end =" ")
### BUGGY CODE ###

import sys
input=sys.stdin.readline

def main():
    r,c,k=map(int,input().split())
    dp=[[[0 for jj in range(c+1)] for ii in range(r+1)] for kk in range(4)]

    g=[[0 for j in range(c)] for i in range(r)]
    for i in range(k):
        rr,cc,v=map(int,input().split())
        rr-=1
        cc-=1
        g[rr][cc]=v
    for i in range(1,r+1):
        for j in range(1,c+1):
            for k in range(4):
                dp[k][i][j]=max(dp[k][i][j],dp[k][i][j-1])#,dp[i][j-1][k])
                dp[0][i][j]=max(dp[0][i][j],dp[k][i-1][j])
                if g[i-1][j-1]>0:
                    if k>0:
                        if dp[k][i][j]<dp[k-1][i][j-1]+g[i-1][j-1]:
                            dp[k][i][j]=dp[k-1][i][j-1]+g[i-1][j-1]
                    if dp[1][i][j]<dp[k][i-1][j]+g[i-1][j-1]:
                        dp[1][i][j]=dp[k][i-1][j]+g[i-1][j-1]
    print(max(dp[0][r][c],dp[1][r][c],dp[2][r][c],dp[3][r][c]))
if __name__=='__main__':
    main()



### FIXED CODE ###

import sys
input=sys.stdin.readline

def main():
    r,c,k=map(int,input().split())
    dp=[[[0 for jj in range(c+1)] for ii in range(r+1)] for kk in range(4)]

    g=[[0 for j in range(c)] for i in range(r)]
    for i in range(k):
        rr,cc,v=map(int,input().split())
        rr-=1
        cc-=1
        g[rr][cc]=v
    for i in range(1,r+1):
        for j in range(1,c+1):
            for k in range(4):
                dp[k][i][j]=max(dp[k][i][j],dp[k][i][j-1])#,dp[i][j-1][k])
                dp[0][i][j]=max(dp[0][i][j],dp[k][i-1][j])
                if g[i-1][j-1]>0:
                    if k>0:
                        if dp[k][i][j]<dp[k-1][i][j-1]+g[i-1][j-1]:
                            dp[k][i][j]=dp[k-1][i][j-1]+g[i-1][j-1]
                    if dp[1][i][j]<dp[k][i-1][j]+g[i-1][j-1]:
                        dp[1][i][j]=dp[k][i-1][j]+g[i-1][j-1]
    print(max(dp[0][r][c],dp[1][r][c],dp[2][r][c],dp[3][r][c]))
if __name__=='__main__':
    main()
### BUGGY CODE ###

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
p = list(map(int, input().split()))

d = [None] * (n**2)
for i in range(n):
    for j in range(n):
        d[i*n+j] = min(i, n-1-i, j, n-1-j)
vacant = [False] * (n**2)

ans = 0
for pos in p:
    pos -= 1
    ans += d[pos]
    vacant[pos] = True
    q = [pos]
    while q:
        pos = q.pop()
        tmp = not vacant[pos]
        for diff in (-1, 1, -n, n):
            ppos = diff+pos
            if ppos<0 or ppos>=n*n:
                continue
            if d[ppos]>d[pos]+tmp:
                d[ppos] = d[pos] + tmp
                q.append(ppos)
#         if pos+n<n*n:
#             ppos = pos + n
#             if d[ppos]>v:
#                 d[ppos] = v
#                 nv = v+1 if not vacant[ppos] else v
#                 q.append((nv, ppos))
#         if pos-n>=0:
#             ppos = pos - n
#             if d[ppos]>v:
#                 d[ppos] = v
#                 nv = v+1 if not vacant[ppos] else v
#                 q.append((nv, ppos))
#         if pos+1<n*n:
#             ppos = pos + 1
#             if d[ppos]>v:
#                 d[ppos] = v
#                 nv = v+1 if not vacant[ppos] else v
#                 q.append((nv, ppos))
#         if pos-1>=0:
#             ppos = pos - 1
#             if d[ppos]>v:
#                 d[ppos] = v
#                 nv = v+1 if not vacant[ppos] else v
#                 q.append((nv, ppos))
print(ans)

### FIXED CODE ###

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
p = list(map(int, input().split()))

d = [None] * (n**2)
for i in range(n):
    for j in range(n):
        d[i*n+j] = min(i, n-1-i, j, n-1-j)
vacant = [False] * (n**2)

ans = 0
for pos in p:
    pos -= 1
    ans += d[pos]
    vacant[pos] = True
    q = [pos]
    while q:
        pos = q.pop()
        tmp = not vacant[pos]
#         for diff in (-1, 1, -n, n):
#             ppos = diff+pos
#             if ppos<0 or ppos>=n*n:
#                 continue
#             if d[ppos]>d[pos]+tmp:
#                 d[ppos] = d[pos] + tmp
#                 q.append(ppos)
        if pos+n<n*n:
            ppos = pos + n
            if d[ppos]>d[pos]+tmp:
                d[ppos] = d[pos] + tmp
                q.append(ppos)
        if pos-n>=0:
            ppos = pos - n
            if d[ppos]>d[pos]+tmp:
                d[ppos] = d[pos] + tmp
                q.append(ppos)
        if pos+1<n*n:
            ppos = pos + 1
            if d[ppos]>d[pos]+tmp:
                d[ppos] = d[pos] + tmp
                q.append(ppos)
        if pos-1>=0:
            ppos = pos - 1
            if d[ppos]>d[pos]+tmp:
                d[ppos] = d[pos] + tmp
                q.append(ppos)
print(ans)
### BUGGY CODE ###

def bfs(q_list):
    cnt = -1
    while q_list:
        cnt += 1
        new_q_list = []
        for h, w in q_list:
            if not m_list[h][w+1]:
                m_list[h][w+1] = True
                new_q_list.append((h, w+1))
            if not m_list[h+1][w]:
                m_list[h+1][w] = True
                new_q_list.append((h+1, w))
            if not m_list[h][w-1]:
                m_list[h][w-1] = True
                new_q_list.append((h, w-1))
            if not m_list[h-1][w]:
                m_list[h-1][w] = True
                new_q_list.append((h-1, w))
        q_list = new_q_list
    print(cnt)


if __name__ == "__main__":
    h_len, w_len = map(int, input().split())
    m_list = [[True for _ in range(w_len+2)]]
    for _ in range(h_len):
        m_list.append([True] + [s=='#' for s in input()] + [True])
    m_list.append([True for _ in range(w_len+2)])
    q_list = []
    for h, w_list in enumerate(m_list[1:-1]):
        for w, a in enumerate(w_list[1:-1]):
            if a:
                q_list.append((h+1, w+1))
    bfs(q_list)
	

### FIXED CODE ###

def bfs(q_list):
    cnt = -1
    while q_list:
        cnt += 1
        new_q_list = []
        for h, w in q_list:
            if not m_list[h][w+1]:
                m_list[h][w+1] = True
                new_q_list.append((h, w+1))
            if not m_list[h+1][w]:
                m_list[h+1][w] = True
                new_q_list.append((h+1, w))
            if not m_list[h][w-1]:
                m_list[h][w-1] = True
                new_q_list.append((h, w-1))
            if not m_list[h-1][w]:
                m_list[h-1][w] = True
                new_q_list.append((h-1, w))
        q_list = new_q_list
    print(cnt)


if __name__ == "__main__":
    h_len, w_len = map(int, input().split())
    m_list = [[True for _ in range(w_len+2)]]
    for _ in range(h_len):
        m_list.append([True] + [s=='#' for s in input()] + [True])
    m_list.append([True for _ in range(w_len+2)])
    q_list = []
    for h in range(1, h_len+1):
        for w in range(1, w_len+1):
            if m_list[h][w]:
                q_list.append((h, w))
    bfs(q_list)
### BUGGY CODE ###

from collections import defaultdict

s = input()
n = len(s)
mod = 2019
DP = [0 for i in range(n+2)]
DP[n+1] = 0

for i in reversed(range(n)):
    DP[i] = (DP[i+1] + int(s[i])*(10**(n-i-1)))%mod
DP.pop(-1)

arr = defaultdict(int)
for dp in DP:
    arr[dp]+=1

ans = 0
for i in arr.values():
    ans += i*(i-1)//2
print(ans)


### FIXED CODE ###

from collections import defaultdict

s = input()
n = len(s)
mod = 2019
DP = [0 for i in range(n+2)]
DP[n+1] = 0

for i in reversed(range(n)):
    DP[i] = (DP[i+1] + int(s[i])*(pow(10,n-i-1,mod)))%mod
DP.pop(-1)

arr = defaultdict(int)
for dp in DP:
    arr[dp]+=1

ans = 0
for i in arr.values():
    ans += i*(i-1)//2
print(ans)