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

N, M, L = map(int, input().split())
ABC = [tuple(map(int, input().split())) for _ in range(M)]
Q = int(input())
ST = [tuple(map(int, input().split())) for _ in range(Q)]
INF = float('inf')

dist = [[INF] * N for _ in range(N)]
fuel = [[INF] * N for _ in range(N)]

for i in range(N):
    dist[i][i] = 0
    fuel[i][i] = 0

for fr, to, cost in ABC:
    if cost > L:
        continue
    fr -= 1
    to -= 1
    dist[fr][to] = cost
    dist[to][fr] = cost

for k in range(N):
    for i in range(N):
        for j in range(N):
            d = dist[i][k] + dist[k][j]
            dist[i][j] = min(dist[i][j], d)
            if d <= L:
                fuel[i][j] = 1

for k in range(N):
    for i in range(N):
        for j in range(N):
            fuel[i][j] = min(fuel[i][j], fuel[i][k] + fuel[k][j])

ans = []
for start, end in ST:
    start -= 1
    end -= 1
    ans.append(fuel[start][end] - 1 if fuel[start][end] != INF else -1)

print(*ans, sep='\n')


### FIXED CODE ###

import sys
input = sys.stdin.readline
INF = float('inf')

N, M, L = map(int, input().split())
ABC = [tuple(map(int, input().split())) for _ in range(M)]
Q = int(input())
ST = [tuple(map(int, input().split())) for _ in range(Q)]

dist = [[INF] * N for _ in range(N)]
fuel = [[INF] * N for _ in range(N)]

for i in range(N):
    dist[i][i] = 0
    fuel[i][i] = 0

for fr, to, cost in ABC:
    if cost > L:
        continue
    fr -= 1
    to -= 1
    dist[fr][to] = cost
    dist[to][fr] = cost

for k in range(N):
    for i in range(N):
        for j in range(N):
            d = dist[i][k] + dist[k][j]
            if dist[i][j] > d:
                dist[i][j] = d
            if d <= L:
                fuel[i][j] = 1

for k in range(N):
    for i in range(N):
        for j in range(N):
            d = fuel[i][k] + fuel[k][j]
            if fuel[i][j] > d:
                fuel[i][j] = d

for start, end in ST:
    print(fuel[start - 1][end - 1] - 1 if fuel[start - 1][end - 1] != INF else -1)
### BUGGY CODE ###

N, M, Q = list(map(int, input().split(' ')))
st_ed = {}
for i in range(M):
    l, r = list(map(int, input().split(' ')))
    st_ed[(l, r)] = st_ed.get((l, r), 0) + 1

memo_s = {}
# memo[(p, q)] = memo[(p, q-1)] + sum([st_ed.get((i, q), 0) for i in [1,2,3...p]])
def f(p, q):
    if (p, q) in memo_s:
        return memo_s[(p, q)]
    if p == q:
        return st_ed.get((p, q), 0)
    temp = f(p, q - 1)
    for i in range(p, q + 1):
        temp += st_ed.get((i, q), 0)
    return temp
    
memo = {}
for i in range(Q):  # 1e5
    p, q = list(map(int, input().split(' ')))
    if not (p, q) in memo:
        temp = f(p, q)
        memo[(p, q)] = temp
    print(memo[(p, q)])



### FIXED CODE ###

N, M, Q = list(map(int, input().split(' ')))
st_ed = {}
for i in range(M):
    l, r = list(map(int, input().split(' ')))
    st_ed[(l, r)] = st_ed.get((l, r), 0) + 1

memo_g = {}
def g(p, q):
    if p == q:
        return st_ed.get((p, q), 0)
    if not (p, q) in memo_g:
        memo_g[(p, q)] = st_ed.get((p, q), 0) + g(p + 1, q)
    return memo_g[(p, q)]

memo_f = {}
# memo[(p, q)] = memo[(p, q-1)] + sum([st_ed.get((i, q), 0) for i in [1,2,3...p]])
def f(p, q):
    if p == q:
        return st_ed.get((p, q), 0)
    if not (p, q) in memo_f:
        temp = f(p, q - 1) + g(p, q)
        memo_f[(p, q)] = temp
    return memo_f[(p, q)]

memo = {}
for i in range(Q):  # 1e5
    p, q = list(map(int, input().split(' ')))
    if not (p, q) in memo:
        temp = f(p, q)
        memo[(p, q)] = temp
    print(memo[(p, q)])
### BUGGY CODE ###

import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

n,k = li()

ab = []
for _ in range(n):
    a,b = li()
    if a <= k:
        ab.append((a,b))

binn = len(bin(k))-2
bink = bin(k)[2:]

cands = [bink]
for i, s in enumerate(list(bink)):
    if int(s):
        cands.append(bink[:i] + "0" + "1"*(binn-i-1))
        
ans = 0
for cand in cands:
    tmp = 0
    for a,b in ab:
        bina = bin(a)[2:].zfill(binn)
        lt = True
        
        for digitc, digita in zip(cand, bina):
            if digita > digitc:
                lt = False
                
        if lt:
            tmp += b
                
    ans = max(ans, tmp)
    
print(ans)

### FIXED CODE ###

import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

n,k = li()

# aをbin文字列で、bを数値で管理する
alis = []
blis = []
for _ in range(n):
    a,b = li()
    if a <= k:
        alis.append(a)
        blis.append(b)

binn = len(bin(k))-2
bink = bin(k)[2:]
binas = [bin(ai)[2:].zfill(binn) for ai in alis]


# binの候補を挙げる
cands = [bink]
for i, s in enumerate(list(bink)):
    if int(s):
        cands.append(bink[:i] + "0" + "1"*(binn-i-1))
        
ans = 0
for cand in cands:
    tmp = 0    
    cand = int("0b"+cand, 0)
    
    for a, b in zip(alis, blis):

        if cand | a <= cand:
            tmp += b
                
    ans = max(ans, tmp)
    
print(ans)
### BUGGY CODE ###

n = int(input())

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

result = 1

for x in a:
    result *= x

if result > 10 ** 18:
    result = -1

print(result)

### FIXED CODE ###

n = int(input())

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

result = 1

if 0 in a:
    result = 0
else:
    for x in a:
        result *= x
        if result > 10 ** 18:
            result = -1
            break

print(result)
### BUGGY CODE ###

from collections import deque


def main():
    S = list(input())
    D = deque(S)
    Q = int(input())
    T = [tuple(map(str, input().split())) for _ in range(Q)]

    for t in T:
        if t[0] == "1":
            D.reverse()
        else:
            if t[1] == "1":
                D.appendleft(t[2])
            else:
                D.append(t[2])

    print("".join(D))


if __name__ == "__main__":
    main()


### FIXED CODE ###

from collections import deque


def main():
    S = list(input())
    D = deque(S)
    Q = int(input())
    T = [tuple(map(str, input().split())) for _ in range(Q)]
    r = False

    for t in T:
        if t[0] == "1" and r == False:
            r = True
        elif t[0] == "1" and r == True:
            r = False
        else:
            if t[1] == "1" and r == False:
                D.appendleft(t[2])
            elif t[1] == "1" and r == True:
                D.append(t[2])
            elif t[1] == "2" and r == False:
                D.append(t[2])
            elif t[1] == "2" and r == True:
                D.appendleft(t[2])

    if r == False:
        print("".join(D))
    else:
        D.reverse()
        print("".join(D))


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

import itertools
from collections import Counter
from functools import reduce
from operator import add, mul

n = int(input())
l = list(input())
l = list(Counter(l).values())

ans = n

for i in range(2, len(l)+1):
    conbis = list(itertools.combinations(l, i))
    for conbi in conbis:
        ans += reduce(mul, conbi)

print(ans%(10**9 + 7))

### FIXED CODE ###

from collections import Counter

n = int(input())
l = list(input())
l = list(Counter(l).values())

ans = 1

for i in l:
    ans *= i+1
print((ans-1)%(10**9+7))
### BUGGY CODE ###

import sys
import fractions
import math
input = sys.stdin.readline

N = int(input())

#a, b, c = (int(i) for i in input().split())  
a = [int(i) for i in input().split()] 
#e = [[int(i) for i in input().split()] for i in range(n)] 

ans = a[0]
total = 0
for i in range(1, N):
    ans = ans * a[i] // fractions.gcd(ans, a[i])

for j in range(N):
    total += ans//a[j]
    total %= (10**9+7)

print(int(total%(10**9+7)))


### FIXED CODE ###

import sys
import fractions
input = sys.stdin.readline


def gcd(x, y):
    while y > 0:
        r = x%y
        x = y
        y = r
    return x
 
def lcm(x, y):
    return x//fractions.gcd(x, y)*y
 
n = int(input())
a = list(map(int, input().split()))
 
l = 1
for x in a:
    l = lcm(x, l)
 
ans = 0
for x in a:
    ans += l//x
 
print(ans%(10**9+7))
### BUGGY CODE ###

n = int(input())
ls = [e for e in range(n+1)]
if sum(ls[:int((2*n)**(1/2))+1]) < n:
    print(int((2*n)**(1/2))+1)
else:
    print(int((2*n)**(1/2)))

### FIXED CODE ###

n = int(input())
if (int((2*n)**(1/2))+1)*(int((2*n)**(1/2)))/2 < n:
    print(int((2*n)**(1/2))+1)
else:
    print(int((2*n)**(1/2)))
### BUGGY CODE ###

import copy
N = int(input())
A = list(map(int,input().split()))

result = ['' for _ in range(N)]

for i in range(N//2):
    if i < N -2:
        s_1 = A[2*i+1]
        s_2 = A[2*i]
        for j in range(2*i+2, N):
            s_1 = s_1 ^ A[j]
            s_2 = s_2 ^ A[j]
        result[2*i] = str(s_1)
        result[2*i+1] = str(s_2)
        m = s_1^s_2
        for j in range(2*i+2, N):
            A[j] = m^A[j]
 
    else:
        result.append(str(A[N-1]))
        result.append(str(A[N-2]))
        break

print(' '.join(result))

### FIXED CODE ###

import copy
N = int(input())
A = list(map(int,input().split()))

result = ['' for _ in range(N)]
s = A[0]
for i in range(1,N):
    s = s ^ A[i]

for i in range(N):
    result[i] = str(s ^ A[i])

print(' '.join(result))
### BUGGY CODE ###

list=list(map(int, input().split()))
A=list[0]
B=list[1]
C=list[2]
K=list[3]
ls=[]
for a in range(A+1):
    sum=0
    for b in range(K-a+1):
        c=K-a-b
        if b<=B and c<=C:
            sum=a-c
            ls.append(sum)
        else:
            continue
print(max(ls))


### FIXED CODE ###

list=list(map(int, input().split()))
A=list[0]
B=list[1]
C=list[2]
K=list[3]
if K<=A:
    print(K)
elif K-A<=B:
    print(A)
else:
    print(A-(K-A-B))
### BUGGY CODE ###

import numpy as np

N = int(input())
A = np.array([int(i) for i in input().split()])

u = list(np.unique(A))
c = []
sum = 0
for j in u:
    _ = len(np.where(A == j)[0])
    c.append(_)
    sum += int(_ * (_ - 1) / 2)

s = ""
for k in range(N):
    v = c[u.index(A[k])]
    s += str(sum - v + 1) + "\n"
print(s)

### FIXED CODE ###

import collections

N = int(input())
A = [int(i) for i in input().split()]

u = collections.Counter(A)
sum = 0
for j, c in u.items():
    sum += int(c * (c - 1) / 2)

s = ""
for k in A:
    s += str(sum - u[k] + 1) + "\n"
print(s)
### BUGGY CODE ###

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

for i in range(M):
    A[A.index(max(A))] //= 2

print(sum(A))

### FIXED CODE ###

import heapq

N, M = map(int, input().split())
A = list(map(lambda x: int(x)*(-1), input().split()))

heapq.heapify(A)

for _ in range(M):
    mn = heapq.heappop(A)
    heapq.heappush(A, -mn//2*(-1))

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

import sys

(str_n,str_y) = input().split()
n = int(str_n)
y = int(str_y)

if y % 1000 != 0:
    print (-1,-1,-1)
    sys.exit()

for i in range(y//10000,-1,-1):
    left = y - 10000*i
    
    for j in range(left//5000,-1,-1):
        left = y - 10000*i - 5000*j
        
        for k in range(left//1000,-1,-1):
            left = y - 10000*i - 5000*j - 1000*k
            if left == 0:
                if i+j+k == n:
                    print (i,j,k)
                    sys.exit()

print (-1,-1,-1)

### FIXED CODE ###

import sys

(str_n,str_y) = input().split()
n = int(str_n)
y = int(str_y)

if y % 1000 != 0:
    print (-1,-1,-1)
    sys.exit()

i_max = min(n,y//10000)
for i in range(i_max,-1,-1):
    left = y - 10000*i
    
    j_max = min(n-i,left//5000)
    for j in range(j_max,-1,-1):
        left = y - 10000*i - 5000*j
        
        k = left // 1000
        if i+j+k == n:
            print (i,j,k)
            sys.exit()

print (-1,-1,-1)
### BUGGY CODE ###

import sys

for S in sys.stdin:
    break
S = S.strip()
le = len(S)

mod = 10**9 + 7

mo = 1

dp = ([1]*10 if S[-1] == "?" else [int(x == int(S[-1])) for x in range(10)]) + [0]*3

i = 1
while i != le:
    mo = (mo * 10)%13
    a = [0]*13
    if S[-i-1] == "?":
        j = 0
        while j != 10:
            k = 0
            while k != 13:
                a[(k+mo*j)%13] += dp[k]
                a[(k+mo*j)%13] %= mod
                k += 1
            j += 1
    else:
        j = int(S[-i-1])
        k = 0
        while k != 13:
            a[(k+mo*j)%13] += dp[k]
            a[(k+mo*j)%13] %= mod
            k += 1
    dp = a
    i += 1

print(dp[5])

### FIXED CODE ###

import sys

for S in sys.stdin:
    break
S = S.strip()
le = len(S)

mod = 10**9 + 7

mo = 1

dp = ([1]*10 if S[-1] == "?" else [int(x == int(S[-1])) for x in range(10)]) + [0]*3

i = 1
while i != le:
    mo = (mo * 10)%13
    a = [0]*13
    if S[-i-1] == "?":
        j = 0
        while j != 10:
            k = 0
            while k != 13:
                a[(k+mo*j)%13] += dp[k]
                a[(k+mo*j)%13] %= mod
                k += 1
            j += 1
    else:
        j = int(S[-i-1])
        k = 0
        while k != 13:
            a[(k+mo*j)%13] += dp[k]
            a[(k+mo*j)%13] %= mod
            k += 1
    dp = a
    i += 1

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


n,m = map(int,input().split())
s = input()
abli = [tuple(map(int,input().split())) for i in range(m)]

def addEdge(graph,u,v):
    graph[u].append(v)


def adjAB(graph,node):
    tmp =list(map(lambda x:s[x-1],graph[node]))
    return('A' in tmp and 'B' in tmp)

def deleteNode(graph,node):
    graph.pop(node,None)
    for i in graph:
        while node in graph[i]:
            graph[i].remove(node)


from collections import defaultdict
graphAB = defaultdict(list)

for i,j in abli:
    addEdge(graphAB,i,j)
    addEdge(graphAB,j,i)


flag = True

while flag:
    flag = False
    deletelist = []
    for i in graphAB:
        if not adjAB(graphAB,i):
            deletelist.append(i)
            flag = True
    for i in deletelist:
        deleteNode(graphAB,i)

if graphAB == {}:
    print('No')
else:
    print('Yes')



### FIXED CODE ###

#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#

"""
GC027 C
"""

n,m = map(int,input().split())
s = list(input())
edges = [tuple(map(int,input().split())) for i in range(m)]
ali = [0 for i in range(n)]
bli = [0 for i in range(n)]


def addEdge(graph,u,v):
    graph[u].add(v)


from collections import defaultdict
graphAB = defaultdict(set)

def incrementAB(node,adj):
    if s[adj-1] == 'A':
        ali[node-1]+=1
    if s[adj-1] == 'B':
        bli[node-1]+=1

def decrementAB(node,adj):
    if s[adj-1] == 'A':
        ali[node-1]-=1
    if s[adj-1] == 'B':
        bli[node-1]-=1

for i,j in edges:
    addEdge(graphAB,i,j)
    addEdge(graphAB,j,i)

def adjAB(node):
    if ali[node-1]!=0 and bli[node-1]!=0:
        return(True)
    else:
        return(False)

graphvers = set(graphAB.keys())
visitset = set()
for i in range(1,n+1):
    if not i in graphvers:
        s[i-1] = 'C'
    else:
        for j in graphAB[i]:
            incrementAB(i,j)
        if not adjAB(i):
            visitset.add(i)


while bool(visitset):
    #print(graphAB)
    #print(graphABopp)
    #print(abli)
    i = visitset.pop()
    for j in graphAB[i]:
        if s[j-1] != 'C':
            decrementAB(j,i)
            if not adjAB(j):
                visitset.add(j)
    s[i-1] = 'C'

#print(graphAB)
#print(graphABopp)

sset= set(s)
sset.add('C')
sset.remove('C')
if bool(sset):
    print('Yes')
else:
    print('No')
### BUGGY CODE ###

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

ans=9999999999
for b in range(min(min(A),max(A)-N),max(A)):
    num=0
    for i,a in enumerate(A):
        num += abs(a-(b+i+1))
    if num<ans:ans=num
print(ans)

### FIXED CODE ###

import numpy as np

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

AA=[]
for i,a in enumerate(A):
    AA.append(a-i+1)

b=np.median(AA)
ans=0

for a in AA:
    ans+=abs(a-b)
print(int(ans))
### BUGGY CODE ###

import math 

N, K = map(int, input().split())
scores = list(map(int, input().split()))
l = []
for i in range(N - K + 1):
  l += [math.prod(scores[i:i+K])]

for i in range(len(l) - 1):
  if l[i] < l[i + 1]:
    print('Yes')
  else:
    print('No')





### FIXED CODE ###

import math 

N, K = map(int, input().split())
scores = list(map(int, input().split()))
l = []
for i in range(N - K):
  print("Yes") if scores[i] < scores[i + K] else print("No")

for i in l:
  print(i)
### BUGGY CODE ###

import math
import calendar
import fractions
import itertools

n = int(input())
a = list(map(int, input().split()))
b = sorted(set(a))[::-1]
ans = 1
cnt = 0
for i in b:
    if cnt == 2:
        break
    if a.count(i) < 2:
        continue
    if cnt == 1:
        ans *= i
        cnt += 1
        break
    if a.count(i) >= 4:
        ans *= i ** 2
        cnt = 2
        break
    ans *= i
    cnt += 1

if cnt < 2:
    ans = 0
print(ans)

### FIXED CODE ###

import math
import calendar
import fractions
import itertools

n = int(input())
a = sorted(map(int, input().split()), reverse=True)
h = 0
w = 0
index = -1
for i in range(n - 3):
    if a[i] == a[i + 1]:
        h = a[i]
        index = i + 2
        break

for i in range(index, n - 1):
    if a[i] == a[i + 1]:
        w = a[i]
        break

print(h * w)
### BUGGY CODE ###

MOD=10**9+7
N=int(input())
xlist=list(map(int,input().split()))

inv_table = [0]+[1]
for i in range(2,N+1):
  inv_table.append(-(MOD//i)*inv_table[MOD%i]%MOD)

fact_nm1=1
for i in range(1,N):
  fact_nm1*=i
  fact_nm1%=MOD
#print(fact_nm1)

answer=0
for i in range(N-1):
  for j in range(i+1,N-1):
    ji_inv=inv_table[j-i]
    ji1_inv=inv_table[j-i+1]
    term=(ji_inv*ji1_inv)%MOD
    answer+=term*(xlist[j]-xlist[i])
    answer%=MOD
    #print(i,j,term)
  
  ni_inv=inv_table[N-1-i]
  term=ni_inv%MOD
  answer+=term*(xlist[N-1]-xlist[i])
  answer%=MOD
  #print(i,N-1,term)
  
answer*=fact_nm1
answer%=MOD  
print(answer)

### FIXED CODE ###

MOD=10**9+7
N=int(input())
xlist=list(map(int,input().split()))

fact_nm1=1
for i in range(1,N):
  fact_nm1*=i
  fact_nm1%=MOD
#print(fact_nm1)

answer_bunshi=0
answer_bumbo=1
inv_bunshi=0
inv_bumbo=1
for i in range(1,N):  
  inv_bunshi=(i*inv_bunshi+inv_bumbo)%MOD
  inv_bumbo=(inv_bumbo*i)%MOD
  #print(inv_bunshi,inv_bumbo)
  
  xdiff=xlist[i]-xlist[i-1]
  term_bunshi=(xdiff*inv_bunshi)%MOD
  answer_bunshi=(answer_bunshi*inv_bumbo+term_bunshi*answer_bumbo)%MOD
  answer_bumbo=(answer_bumbo*inv_bumbo)%MOD
#print(answer_bunshi,answer_bumbo)

answer_bunshi=(answer_bunshi*fact_nm1)%MOD
answer=answer_bunshi*pow(answer_bumbo,MOD-2,MOD)
answer%=MOD
print(answer)
### BUGGY CODE ###

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

an = 0

for i in range(1,n+1):
    for j in range(i+1,n+1):
        for k in range(j+1,n+1):
            if i<j and j<k and (j-i) != (k-j) and s[i-1]!=s[j-1] and s[i-1]!=s[k-1] and s[j-1]!=s[k-1]:
                an += 1
print(an)

### FIXED CODE ###

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

an = s.count('R') *s.count('G') *s.count('B')

for i in range(n-2):
    for j in range(i+1,n-1):
        k = 2*j-i
        if (k<n) and (s[i]!=s[j]) and (s[j]!=s[k])and(s[i]!=s[k]):
                an -= 1

print(an)
### BUGGY CODE ###

import fractions
import math
import itertools
from functools import reduce

k = int(input())

total = 0
ran = range(1, k + 1)
for i, j, k in itertools.product(ran, ran, ran):
    total += math.gcd(math.gcd(i, j), k)
    
print(total)

### FIXED CODE ###

from math import gcd
from collections import defaultdict

k = int(input())

memo = defaultdict(defaultdict)

rg = range(1, k + 1)
for i in rg:
    for j in rg:
        memo[i][j] = memo[j][i] = gcd(i, j)

ret = 0
for i in rg:
    for j in rg:
        tmp = memo[i][j]
        for k in rg:
            res = memo[k][tmp]
            ret += res

print(ret)
### BUGGY CODE ###

import sys
from collections import Counter

def cmb2(n):
	result = n * (n - 1) / 2

	return int(result)

if __name__ == "__main__":

	N = int(input())
	A = [int(i) for i in input().split()]

	S = Counter(A)
	for a in A:
		S[a] -= 1
		ans = 0
		for d in S.values():
			ans += cmb2(d)
		print(ans)
		S[a] += 1

### FIXED CODE ###

import sys
from collections import Counter

def cmb2(n):
	if n < 2:
		return 0

	return n * (n-1) // 2

if __name__ == "__main__":

	N = int(input())
	A = [int(i) for i in input().split()]
	# A = list(map(int, input().split()))

	c = Counter(A)
	s = 0
	for v in c.values():
		s += cmb2(v)

	for a in A:
		print(s - cmb2(c[a]) + cmb2(c[a] - 1))
### BUGGY CODE ###

def main():
    MOD=10**9+7

    mod13=[1]*(10**5+1)
    for i in range(10**5):
        mod13[i+1]=mod13[i]*10%13
    
    s=list(input())[::-1]
    l=len(s)
    
    dp=[[0]*13 for _ in range(1+l)]

    if s[0]=='?':
        for num in range(10):
            t=num%13
            dp[1][t]+=1
    else:
        num=int(s[0])
        t=num%13
        dp[1][t]=1

    for i in range(1,l):
        if s[i]=='?':
            for j in range(13):
                for num in range(10):
                    t=(j+mod13[i]*num)%13
                    dp[i+1][t]+=dp[i][j]
                    dp[i+1][t]%=MOD
        
        else:
            num=int(s[i])
            for j in range(13):
                t=(j+mod13[i]*num)%13
                dp[i+1][t]+=dp[i][j]
                dp[i+1][t]%=MOD
    
    print(dp[-1][5])
 
if __name__=='__main__':
    main()

### FIXED CODE ###

def main():
    MOD=10**9+7

    mod13=[1]*(10**5+1)
    for i in range(10**5):
        mod13[i+1]=mod13[i]*10%13
    
    s=list(input())[::-1]
    l=len(s)
    
    dp=[[0]*13 for _ in range(1+l)]

    if s[0]=='?':
        for num in range(10):
            t=num%13
            dp[1][t]+=1
    else:
        num=int(s[0])
        t=num%13
        dp[1][t]=1

    for i in range(1,l):
        if s[i]=='?':
            for j in range(13):
                for num in range(10):
                    t=(j+mod13[i]*num)%13
                    dp[i+1][t]+=dp[i][j]
                    dp[i+1][t]%=MOD
        
        else:
            num=int(s[i])
            for j in range(13):
                t=(j+mod13[i]*num)%13
                dp[i+1][t]+=dp[i][j]
                dp[i+1][t]%=MOD
    
    print(dp[-1][5])
 
if __name__=='__main__':
    main()
### BUGGY CODE ###

import sys
import collections


def solve():
    sys.setrecursionlimit(2000)
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    h, w = list(map(int, input().rstrip('\n').split()))
    a = [list(str(input().rstrip('\n'))) for _ in range(h)]
    ql = []
    ql = collections.deque(ql)
    fq = collections.defaultdict(list)
    for i in range(h):
        for j in range(w):
            if a[i][j] == "#":
                ql.append([0, i, j])
                fq[i, j]

    mt = 0
    while True:
        if len(ql) != 0:
            cost, xv, yv = ql.popleft()
            mt = max(mt, cost)
            for xv, yv in [[xv + 1, yv], [xv - 1, yv], [xv, yv + 1], [xv, yv - 1]]:
                if 0 <= xv < h and 0 <= yv < w:
                    if (xv, yv) not in fq and a[xv][yv] == ".":
                        ql.append([cost + 1, xv, yv])
                        fq[xv, yv]
        else:
            break
    print(mt)


if __name__ == '__main__':
    solve()


### FIXED CODE ###

import sys
import collections


def solve():
    readline = sys.stdin.buffer.readline
    h, w = list(map(int, readline().split()))
    a = [[True] * w for _ in range(h)]
    ql = collections.deque()
    for i in range(h):
        s = list(str(readline().rstrip().decode('utf-8')))
        for j in range(w):
            if s[j] == "#":
                ql.append([0, i, j])
                a[i][j] = False
    while ql:
        cost, x, y = ql.popleft()
        for xv, yv in ((x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)):
            if 0 <= xv < h and 0 <= yv < w:
                if a[xv][yv]:
                    ql.append([cost + 1, xv, yv])
                    a[xv][yv] = False
    print(cost)


if __name__ == '__main__':
    solve()