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

from collections import deque
import copy
 
def main():
  H, W = map(int, input().split())
  M = [['#' == x for x in input()] for _ in range(H)]
  que = deque([(i, j) for i in range(H) for j in range(W) if M[i][j]])
  ans = 0
  while True:
    ans += 1
    qq = deque()
    while que:
      nh, nw = que.popleft()
      if nw<W-1 and not M[nh][nw+1]:
        qq.append((nh,nw+1))
        M[nh][nw+1] = True
      if nw>0 and not M[nh][nw-1]:
        qq.append((nh,nw-1))
        M[nh][nw-1] = True
      if nh<H-1 and not M[nh+1][nw]:
        qq.append((nh+1,nw))
        M[nh+1][nw] = True
      if 0<nh and not M[nh-1][nw]:
        qq.append((nh-1,nw))
        M[nh-1][nw] = True
    if qq:
      que = copy.copy(qq)
    else:
      break
  print(ans-1)
  
if __name__ == "__main__":
  main()

### FIXED CODE ###

import copy
from collections import deque
def main():
  H, W = map(int, input().split())
  G = [['#' == x for x in input()] for _ in range(H)]
 
  black = deque([(i, j) for i in range(H) for j in range(W) if G[i][j]])
 
  ans = 0
  while True:
    ans += 1
    next_black = deque()
    while black:
      bi, bj = black.popleft()
      if bi > 0 and not G[bi - 1][bj]:
        G[bi - 1][bj] = True
        next_black.append((bi - 1, bj))
      if bj > 0 and not G[bi][bj - 1]:
        G[bi][bj - 1] = True
        next_black.append((bi, bj - 1))
      if bi < H - 1 and not G[bi + 1][bj]:
        G[bi + 1][bj] = True
        next_black.append((bi + 1, bj))
      if bj < W - 1 and not G[bi][bj + 1]:
        G[bi][bj + 1] = True
        next_black.append((bi, bj + 1))
    if next_black:
       black = copy.copy(next_black)
    else:
       break
  print(ans - 1)
  
if __name__ == "__main__":
  main()
### BUGGY CODE ###

# TLE

import numpy as np
import sys
sys.setrecursionlimit(2000)

H, W = [int(x) for x in input().split()]
s = [list(input()) for i in range(H)]
M = np.array([[ (0 if s[i][j] == '.' else 1) for j in range(W) ] for i in range(H)])

def solve(M):

    Mr = np.copy(M)
    Mc = np.copy(M)


    H = M.shape[0]
    W = M.shape[1]

    ret = 0

    if M.sum() == 0:
        return ret
    elif H == W == 1:
        return M[0][0]


    del_row = 100000
    del_col = 100000
    retr = 0
    retc = 0
    if H > 1:
        if Mr[0][0] == 1:
            h = 1
            w = 1
            # while h < H and M[:h + 1, :w].sum() == (h + 1) * w:
            while h < H and Mr[h][0] == 1:
                h += 1
            # while w < W and Mr[:h, :w + 1].sum() == h * (w + 1):
            while w < W and Mr[:h, w:w + 1].sum() == h:
                w += 1

            for i in range(h):
                for j in range(w):
                    Mr[i][j] = 0
            retr += 1

        del_row = solve(Mr[1:, :])


    if W > 1:

        if Mc[0][0] == 1:

            h = 1
            w = 1

            # while w < W and Mc[:h, :w + 1].sum() == h * (w + 1):
            while w < W and Mc[0][w] == 1:
                w += 1
            # while h < H and Mc[:h + 1, :w].sum() == (h + 1) * w:
            while h < H and Mc[h:h + 1, :w].sum() == w:
                h += 1


            for i in range(h):
                for j in range(w):
                    Mc[i][j] = 0
            retc += 1

        del_col = solve(Mc[:, 1:])

    return min(retr + del_row, retc + del_col)


print(solve(M))


### FIXED CODE ###

import numpy as np

H, W = [int(x) for x in input().split()]
s = [list(input()) for i in range(H)]

M = np.array([[ (0 if s[i][j] == '.' else 1) for j in range(W) ] for i in range(H)])
INF = 10 ** 9
dp = np.array([[INF for j in range(W)] for i in range(H)])

for i in range(H - 1, -1, -1):
    for j in range(W - 1, -1, -1):
        ans_r = INF
        ans_d = INF
        if i == H - 1 and j == W - 1:
            dp[i][j] = M[i][j]
            continue
        if j < W - 1:  # 右に動ける
            if M[i][j] == 1 and M[i][j + 1] == 0:
                ans_r = dp[i][j + 1] + 1
            else:
                ans_r = dp[i][j + 1]
        if i < H - 1:  # 下に動ける
            if M[i][j] == 1 and M[i + 1][j] == 0:
                ans_d = dp[i + 1][j] + 1
            else:
                ans_d = dp[i + 1][j]
        dp[i][j] = min(ans_r, ans_d)

print(dp[0][0])
### BUGGY CODE ###

s=input()
t=input()

#print(t[0])

condition=0
for i in range(len(t)):
 if s.count(t[i])==0:
   condition=1
   break

if condition==1:
  print(-1)
else:
  j=0
  count=0
  while j <=len(t)-1 and count<len(s)*(10**100):   
    for k in range(len(s)):
      count=count+1
      if t[j]==s[k]:
        j=j+1
        #print(j,k)
        if j==len(t):
          print(count)
          break
    if j==len(t):
      break
    if count == len(s)*(10**100):
      print(-1)
      break
        
        

### FIXED CODE ###

import bisect

s=input()
t=input()

#index=list()
#for a in range(len(t)):
# index.append([i for i, x in enumerate(s) if x == t[a]])

char_appear = {ch: [] for ch in 'abcdefghijklmnopqrstuvwxyz'}
for i, ch in enumerate(s):
    char_appear[ch].append(i)
#print(char_appear['a'])
      
b=0
loop=0
condition=0

for j in range(len(t)):
  if len(char_appear[t[j]])<1:
    print(-1)
    condition=1
    break
  c=bisect.bisect(char_appear[t[j]],b)
 # print(j,char_appear[t[j]],b,c,loop)
  if j<1:
    b=char_appear[t[0]][0]    
  elif c == len(char_appear[t[j]]): #or c==char_appear[t[j]][len(char_appear[t[j]])-1]: 
     loop +=1
     b=char_appear[t[j]][0]
     if loop==10**100:
        print(-1)
        condition=1
        break
  else:
     b=char_appear[t[j]][c]
     #print(j,b,loop)


if condition==0:
 print(b+loop*len(s)+1)
### BUGGY CODE ###

N = int(input())
for h in range(1,3501):
    for n in range(1,3501):
        if (4 * h * n - N * n - N * h) != 0 and (N * h * n) % (4 * h * n - N * n - N * h) == 0:
            if (N * h * n) // (4 * h * n - N * n - N * h) > 0:
                print("{} {} {}".format(h,n,(N * h * n) // (4 * h * n - N * n - N * h)))
                exit()

### FIXED CODE ###

N = int(input())
for h in range(1,3501):
    for n in range(1,3501):
        if (4 * h * n - N * n - N * h) != 0 and (N * h * n) % (4 * h * n - N * n - N * h) == 0:
            if (N * h * n) // (4 * h * n - N * n - N * h) > 0:
                print("{} {} {}".format(h,n,(N * h * n) // (4 * h * n - N * n - N * h)))
                exit()
### BUGGY CODE ###

import numpy as np
*s, a, b = map(int, input().split())
p = np.ones(s, dtype=np.int)
p[:b,:a] = 0
p[b:,a:] = 0
for i in p:
    print(*i, sep="")

### FIXED CODE ###

import numpy as np
*s, a, b = map(int, input().split())
p = np.ones(s, dtype=np.int)
p[:b,:a] = 0
p[b:,a:] = 0
print('\n'.join(''.join(q) for q in p.astype(str)))
### BUGGY CODE ###

# ABC073C - Write and Erase
import sys
input = sys.stdin.readline

n = int(input())
arr = list(map(int, [input().rstrip() for _ in range(n)]))
st = set(arr)
cnt = 0
for i in st:
    if arr.count(i) % 2 == 1:
        cnt += 1
print(cnt)

### FIXED CODE ###

# ABC073C - Write and Erase
import sys
input = sys.stdin.readline

n = int(input())
arr = set()
for _ in range(n):
    m = int(input())
    if m in arr:
        arr.remove(m)
    else:
        arr.add(m)
print(len(arr))
### BUGGY CODE ###

N=int(input())
S=set({})
for _ in range(N):
  S = S | {input()}
  
x=list(S)
print(len(x))
  

### FIXED CODE ###

N=int(input())
hash = {}
count=0
for _ in range(N):
    s=input()
    if s in hash:
      continue
    else:
      hash[s]=1
      count+=1
print(count)
### BUGGY CODE ###

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

ship_list1 = []
ship_list2 = []
count = 0

for i in range(m):
    if ab[i][0] == 1:
        ship_list1.append(ab[i])
    if ab[i][1] == n:
        ship_list2.append(ab[i])

for ship1 in ship_list1:
    for ship2 in ship_list2:
        if ship1[1] == ship2[0]:
            print('POSSIBLE')
            count += 1
            break
        else:
            continue

if count == 0:
    print('IMPOSSIBLE')

### FIXED CODE ###

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

ship_list1 = []
ship_list2 = []
count = 0
loop = False

for i in range(m):
    if ab[i][0] == 1:
        ship_list1.append(ab[i][1])
    if ab[i][1] == n:
        ship_list2.append(ab[i][0])

if len(set(ship_list1) & set(ship_list2)) >= 1:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')
### BUGGY CODE ###

N,Q=map(int,input().split())
s=input()
for i in range(Q):
    l,r=map(int,input().split())
    print(s[l-1:r].count("AC"))

### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
LR = [list(map(int, input().split())) for _ in range(Q)]
dp = [0] * (N)
for i in range(N-1):
    if S[i] == 'A' and S[i+1] == 'C':
        dp[i+1] = dp[i] + 1
    else:
        dp[i+1] = dp[i]

for l, r in LR:
    print(dp[r-1] - dp[l-1])
### BUGGY CODE ###

s=input()
n=len(s)
k=int(input())
ans=set()
for i in range(n):
    for j in range(i+1,n+1):
        ans.add(s[i:j])
ans=sorted(list(ans))
print(ans[k-1])

### FIXED CODE ###

s=input()
n=len(s)
k=int(input())
ans=set()
for i in range(n):
    for j in range(i+1,min(i+k+1,n+1)):
        ans.add(s[i:j])
ans=sorted(list(ans))
print(ans[k-1])
### BUGGY CODE ###

I=lambda:map(int,input().split());n,m=I();d=[0]+[9**9]*2**n
while m:
 m-=1;a,_=I();s=sum(1<<c-1for c in I())
 for j in range(2**n):d[s|j]=min(d[s|j],d[j]+a)
print(d[-2]%9**9or-1)

### FIXED CODE ###

import sys
input=sys.stdin.readline
n,m=map(int,input().split())
e=[(int(input().split()[0]),list(map(int,input().split())))for _ in range(m)]
INF=10**18
dp=[INF]*2**n
dp[0]=0
for i in range(2**n):
    if dp[i]>=INF:continue
    for a,c in e:
        bit=i
        for j in c:
            bit|=2**(n-j)
        dp[bit]=min(dp[bit],dp[i]+a)
a=dp[-1]
if a>=INF:
    print(-1)
else:
    print(dp[-1])
### BUGGY CODE ###

import sys
input=lambda: sys.stdin.readline().rstrip()
sys.setrecursionlimit(200000)
mod=10**9+7
n=int(input())
edge=[[] for i in range(n)]
for i in range(n-1):
  a,b=map(int,input().split())
  edge[a-1].append(b-1)
  edge[b-1].append(a-1)
inf=float("inf")
Par=[inf]*n
Par[0]=-1
Chk=[0]
while Chk:
  c=Chk.pop()
  for next in edge[c]:
    if Par[next]==inf:
      Par[next]=c
      Chk.append(next)

C=[-1]*n
def ch(x):
  ret=0
  if x!=0 and len(edge[x])==1:
    C[x]=0
    return C[x]
  else:
    for e in edge[x]:
      if e==Par[x]:
        continue
      else:
        ret+=ch(e)+1
    C[x]=ret
    return C[x]
ch(0)

H=[0]*n
H[0]=1
H[1]=pow(2,mod-2,mod)
for i in range(2,n):
  H[i]=(H[i-1]*H[1])%mod

ans=0
for i in range(n):
  if len(edge[i])==1:
    continue
  else:
    A=[]
    for e in edge[i]:
      if e==Par[i]:
        A.append(n-1-C[i])
      else:
        A.append(C[e]+1)
    cur=1+(len(edge[i])-1)*H[-1]
    for a in A:
      cur-=H[n-1-a]
    ans=(ans+cur)%mod
print((ans*H[1])%mod)

### FIXED CODE ###

import sys
input=lambda: sys.stdin.readline().rstrip()
sys.setrecursionlimit(200000)
mod=10**9+7
n=int(input())
edge=[[] for i in range(n)]
for i in range(n-1):
  a,b=map(int,input().split())
  edge[a-1].append(b-1)
  edge[b-1].append(a-1)
inf=10**6
Par=[inf]*n
Par[0]=-1
Chk=[0]
while Chk:
  c=Chk.pop()
  for next in edge[c]:
    if Par[next]==inf:
      Par[next]=c
      Chk.append(next)

C=[-1]*n
def ch(x):
  ret=0
  if x!=0 and len(edge[x])==1:
    C[x]=0
    return C[x]
  else:
    for e in edge[x]:
      if e==Par[x]:
        continue
      else:
        ret+=ch(e)+1
    C[x]=ret
    return C[x]
ch(0)

H=[0]*n
H[0]=1
H[1]=pow(2,mod-2,mod)
for i in range(2,n):
  H[i]=(H[i-1]*H[1])%mod

ans=0
for i in range(n):
  if len(edge[i])==1:
    continue
  else:
    A=[]
    for e in edge[i]:
      if e==Par[i]:
        A.append(n-1-C[i])
      else:
        A.append(C[e]+1)
    cur=1+(len(edge[i])-1)*H[-1]
    for a in A:
      cur-=H[n-1-a]
    ans=(ans+cur)%mod
print((ans*H[1])%mod)
### BUGGY CODE ###

from collections import deque
s=list(str(input()))
s=deque(s)
q=int(input())
for i in range(q):
    que=list(input().split())
    if len(que)==1:
        s.reverse()
    else:
        if int(que[1])==1:
            s=deque(s)
            s.appendleft(que[2])
        elif int(que[1])==2:
            s=deque(s)
            s.append(que[2])
print(''.join(s)) 

### FIXED CODE ###

from collections import deque
s=list(str(input()))
s=deque(s)
q=int(input())
cnt=0
for i in range(q):
    que=list(input().split())
    if len(que)==1:
        cnt+=1
    if len(que)!=1 and cnt%2==0:
        if int(que[1])==1:
            s.appendleft(que[2])
        elif int(que[1])==2:
            s.append(que[2])
    if len(que)!=1 and cnt%2!=0:
        if int(que[1])==1:
            s.append(que[2])
        elif int(que[1])==2:
            s.appendleft(que[2])
if cnt%2!=0:
    s.reverse()
print(''.join(s))
### BUGGY CODE ###

n = int(input())
s = input()

rcount=0
gcount=0
bcount=0
for i in range(n):
    if s[i]=="R":
        rcount+=1
    elif s[i]=="G":
        gcount+=1
    else:
        bcount+=1

al=rcount*bcount*gcount

for i in range(n-2):
    for k in range(i+1,n):
        dis=k-i
        if k+dis<=n-1:
            l=k+dis
            if s[i]!=s[k] and s[i]!=s[l] and s[k]!=s[l]:
                al-=1

print(al)


### FIXED CODE ###

n = int(input())
s = input()

al=s.count("R")*s.count("G")*s.count("B")

for i in range(n-2):
    for k in range(i+1,n-1):
        l=k+(k-i)
        if l>=n:
            continue
        if s[i]!=s[k] and s[i]!=s[l] and s[k]!=s[l]:
            al-=1

print(al)
### BUGGY CODE ###

from functools import reduce
n = int(input())
A = list(map(int,input().split()))
S = reduce(lambda x, y: x * y, A)
if S > 10**18:
    print(-1)
else:
    print(S)

### FIXED CODE ###

import sys
l = 10**18
n = int(input())
A = list(map(int,input().split()))
S = 1
if 0 in A:
    print(0)
    sys.exit()
for i in range(n):
    S = S * A[i]
    if S > l:
        print(-1)
        break
if S <= l:
    print(S)
### BUGGY CODE ###

import collections as c
d=c.defaultdict(list)
d2=c.defaultdict(list)
a,b=map(int,input().split())
l=[]
for s in range(b):
    g,j=map(int,input().split())
    d[g].append(j)
    l.append([g,j])
#print(d)
d3=c.defaultdict(list)
for k,v in d.items():
    d2[k]=sorted(v)
for t in d2.keys():
    for k,v in enumerate(d2[t]):
        d3[t].append([v,k+1])
#print(d3)
#print(l)
for sss in l:
    for ttt in d3[sss[0]]:
        if ttt[0]==sss[1]:
            print('{:06d}'.format(sss[0])+'{:06d}'.format(ttt[1]))
  #          print(sss[0],ttt[1])

### FIXED CODE ###

a,b=map(int,input().split())
l=[]
for _ in range(b):
    c,d=map(int,input().split())
    l.append((c,d))
l2=sorted(sorted(l, key=lambda x:x[1]), key=lambda y:y[0])
m=1
count=0
dic={}
for t in l2:
    if t[0] !=m:
        m=t[0]
        count=1
    else:
        count+=1
    dic[t]=count
#print(dic)
for q in l:
    print('{:06d}'.format(q[0])+'{:06d}'.format(dic[q]))
### BUGGY CODE ###

import sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = 10**20
def I(): return int(input())
def F(): return float(input())
def S(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()

def resolve():
    N, K = LI()
    A = LI()

    for _ in range(K):
        tmp = [0] * (N + 1)
        b = [0] * (N + 1)
        for i in range(N):
            tmp[max(i - A[i], 0)] += 1
            tmp[min(i + A[i] + 1, N)] -= 1
        for i in range(N):
            b[i+1] = tmp[i] + b[i]
        for i in range(N):
            A[i] = b[i+1] 
        if A.count(N) == N:
            break

    print(*A)

if __name__ == '__main__':
    resolve()


### FIXED CODE ###

import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = 10**20
def I(): return int(input())
def F(): return float(input())
def S(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()

def resolve():
    N, K = LI()
    A = LI()

    # 全部0の最遅ケースでもlog(N)*2くらいで収束する log(2*10**5)<50
    for _ in range(min(K, 50)):
        tmp = [0] * (N + 1)
        b = [0] * (N + 1)
        for i in range(N):
            tmp[max(i - A[i], 0)] += 1
            tmp[min(i + A[i] + 1, N)] -= 1
        for i in range(N):
            b[i+1] = tmp[i] + b[i]
        for i in range(N):
            A[i] = b[i+1] 
        # print(A)

    print(*A)

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

n, k = map(int, input().split())
a = list(map(int, input().split()))

prev = 1
for i in range(k):
    prev *= a[i]

res = []
for i in range(k, n):
    curr = prev // a[i - k] * a[i]
    res.append(curr > prev)
    prev = curr

#print(res)
for b in res:
    if(b): print("Yes")
    else: print("No")

### FIXED CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))

res = []
for i in range(k, n):
    res.append(a[i-k] < a[i])

#print(res)
for b in res:
    if(b): print("Yes")
    else: print("No")
### BUGGY CODE ###

l=list(map(int,input().split()))
d=list(map(int,input().split()))
u={i for i in range(10)}
d_bar=u-set(d)
n=l[0]
n_list=list(int(j) for j in str(n))  
while True:
    n_set=set(n_list)
    if n_set<=d_bar:
        print(n)
    else:
        n=n+1
    

### FIXED CODE ###

l=list(map(int,input().split()))
d=list(map(int,input().split()))
u={i for i in range(10)}
d_bar=u-set(d)
d_bar={str(i) for i in d_bar}
n=l[0]
n_set=set(str(n))
while True:
    if n_set<=d_bar:
        print(n)
        break
    n=n+1
    n_set=set(str(n))
### BUGGY CODE ###

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

dp = [[0 for _ in range(n+1)] for _ in range(n+1)]
#dp[l][r]: 左l個右r個取ったところからの前-後max
for i in range(n):
	dp[i][n-1-i] = a[i]
for x in range(n-2, -1, -1):
	for y in range(x+1):
		l, r = y, x-y
		dp[l][r] = max(-dp[l+1][r] + a[l], -dp[l][r+1] + a[-(r+1)])

print(dp[0][0])

### FIXED CODE ###

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

dp = [[0 for _ in range(n+1)] for _ in range(n+1)]
#dp[l][r]: 左l個右r個取ったところからの前-後max
for i in range(n):
	dp[i][n-1-i] = a[i]
for x in range(n-2, -1, -1):
	for y in range(x+1):
		l, r = y, x-y
		dp[l][r] = max(-dp[l+1][r] + a[l], -dp[l][r+1] + a[-(r+1)])

print(dp[0][0])
### BUGGY CODE ###

N = int(input())
A = [int(i) for i in input().split()]
res=1
for x in A:
    res = res*x
if res > 10**18:
    print(-1)
else:
    print(res)

### FIXED CODE ###

N = int(input())
A = sorted([int(i) for i in input().split()])
res=1
for x in A:
    res = res*x
    if res > 10 ** 18:
        res = -1
        break
print(res)
### BUGGY CODE ###

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

exp_sum = []
sum_max = 0
exp1 = 0
for j in range(0,len(p)-k+1):
    sum_each = 0
    exp1 = 0
    sum1 = 0
#if k == 1:
#for k in range()
#sum1 += sum(p[0:k])
#exp1 = sum1/p[0]
#exp_sum.append(exp1)
#else:
    for i in range(j,j + k):
        sum1 += p[i]
        sum_max = max(sum1,sum_max)
    if sum_max <= sum1:
        for i in range(j,j + k):
            sum_each = 0.5 * p[i] * (p[i] + 1)
            exp1 += sum_each/p[i]
        exp_sum.append(exp1)
print(max(exp_sum))

### FIXED CODE ###

import sys

def LI(): return list(map(int, sys.stdin.readline().split()))
N, K = LI()
p = LI()
ps = []
for i in range(N):
    ps.append((p[i] + 1) / 2)
 
anss = []
tmp = 0
for i in range(N):
    tmp += ps[i]
    if i > K - 1:
        tmp -= ps[i - K]
    anss.append(tmp)
 
print(max(anss))
### BUGGY CODE ###

S = input()[::-1]
keta = len(S)
mod = 10 ** 9 + 7

dp = [[0 for _ in range(13)] for _ in range(keta + 1)]
dp[0][0] = 1
for i in range(1, keta + 1):
    if S[i - 1] != "?":
        x = int(S[i - 1]) * (10 ** (i - 1)) % 13
        for j in range(13):
            dp[i][(x + j) % 13] += dp[i - 1][j] % mod
    else:
        for k in range(10):
            x = k * (10 ** (i - 1)) % 13
            for j in range(13):
                dp[i][(x + j) % 13] += dp[i - 1][j] % mod

print(dp[keta][5] % mod)

### FIXED CODE ###

S = input()[:: -1]
mod = 10 ** 9 + 7
dp = [[0 for _ in range(13)] for _ in range(len(S) + 1)]

if S[0] == "?":
    for k in range(10):
        dp[1][k % 13] += 1
else:
    dp[1][int(S[0]) % 13] += 1

tmp = 1
for i in range(2, len(S) + 1):
    tmp *= 10
    tmp %= 13
    for j in range(13):
        if dp[i - 1][j] > 0:
            if S[i - 1] == "?":
                for k in range(10):
                    dp[i][(tmp * k + j) % 13] += dp[i - 1][j] % mod
            else:
                dp[i][(tmp * int(S[i - 1]) + j) % 13] += dp[i - 1][j] % mod

print(dp[len(S)][5] % mod)
### BUGGY CODE ###

n = int(input())
s = list(input())

dp = [[0 for _ in range(5001)]] * 5001
ans = 0

for i in range(n-1, -1, -1):
    for j in range(i, -1, -1):
        if s[i] == s[j]:
            a = dp[i+1][j+1]
            dp[i][j] = a + 1
        ans = max(ans, min(i-j, dp[i][j]))
        
print(ans)


### FIXED CODE ###

n = int(input())
s = input()

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

for i in range(n-1, -1, -1):
    for j in range(i, -1, -1):
        if s[i] == s[j]:
             dp[i][j] = dp[i+1][j+1] + 1
             ans = max(ans, min(i-j, dp[i][j]))
        
print(ans)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
for i in range(n):
    print(a.count(i+1))

### FIXED CODE ###

from collections import Counter
n=int(input())
a=list(map(int,input().split()))
s=Counter(a)
for i in range(n):
    print(s[i+1])
### BUGGY CODE ###

R, G, B, N = map(int,input().split())
count = 0

for r in range(N // R + 1):
    for g in range(N // G + 1):
        b = (N - R*r - G*g) / B
        if b >= 0 and b.is_integer():
            count += 1

print(count)


### FIXED CODE ###

R, G, B, N = map(int,input().split())
count = 0

for r in range(N // R + 1):
    for g in range(N // G + 1):
        b = (N - R*r - G*g) / B
        if b >= 0 and b.is_integer():
            count += 1

print(count)
### BUGGY CODE ###

H,W=map(int,input().split())
A=[list(map(int,input().split())) for i in range(H)]
B=[list(map(int,input().split())) for i in range(H)]
d=[[[0]*80*H*W for i in range(W+1)] for j in range(H+1)]
d[1][1][A[0][0]-B[0][0]]=d[1][1][B[0][0]-A[0][0]]=1
for h in range(H):
    for w in range(W):
        x=A[h][w]-B[h][w]
        for y in range(80*H*W):
            if d[h][w+1][y] or d[h+1][w][y]:
                d[h+1][w+1][(y+x)%(80*H*W)]=d[h+1][w+1][(y-x)%(80*H*W)]=1
for i in range(40*H*W):
    if d[H][W][i] or d[H][W][-i]:
        print(i)
        exit()

### FIXED CODE ###

H,W=map(int,input().split())
A=[list(map(int,input().split())) for i in range(H)]
B=[list(map(int,input().split())) for i in range(H)]
d=[[0]*W for j in range(H)]
m=80*(H+W)
d[0][0]=1<<m
for h in range(H):
    for w in range(W):
        x=abs(A[h][w]-B[h][w])
        if h>0:
            d[h][w]|=d[h-1][w]
        if w>0:
            d[h][w]|=d[h][w-1]
        d[h][w]=d[h][w]<<x|d[h][w]>>x
x,y=1<<m,1<<m
for i in range(99):
    if d[H-1][W-1]&x or d[H-1][W-1]&y:
        print(i)
        exit()
    x<<=1
    y>>=1