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

# input
h, w = [int(i) for i in input().split()]
ary = []
for y in range(h):
    ary.append([None if i == '.' else 0 for i in input()])


from collections import deque

update_q = deque((y, x) for y, line in enumerate(ary) for x, elem in enumerate(line) if elem == 0)

pass
from copy import copy
def update(ary, update_q):
    for _ in range(len(update_q)):
        pos = update_q.popleft()
        y, x = pos
        if x > 0:
            uy, ux = y, x-1
            if ary[uy][ux] is None:
                ary[uy][ux] = ary[y][x] + 1
                update_q.append((uy, ux))
        if x < w-1:
            uy, ux = y, x+1
            if ary[uy][ux] is None:
                ary[uy][ux] = ary[y][x] + 1
                update_q.append((uy, ux))
        if y > 0:
            uy, ux = y-1, x
            if ary[uy][ux] is None:
                ary[uy][ux] = ary[y][x] + 1
                update_q.append((uy, ux))
        if y < h-1:
            uy, ux = y+1, x
            if ary[uy][ux] is None:
                ary[uy][ux] = ary[y][x] + 1
                update_q.append((uy, ux))
    return ary, update_q


black_count = len(update_q)
while black_count < w * h:
    ary, update_q = update(ary, update_q)
    black_count += len(update_q)


print(max(elem for line in ary for elem in line))


### FIXED CODE ###

# input
h, w = [int(i) for i in input().split()]
ary = []
for y in range(h):
    ary.append([None if i == '.' else 0 for i in input()])


from collections import deque

update_q = deque((y, x) for y, line in enumerate(ary) for x, elem in enumerate(line) if elem == 0)

def update(ary, update_q):
    for _ in range(len(update_q)):
        pos = update_q.popleft()
        y, x = pos
        if x > 0:
            uy, ux = y, x-1
            if ary[uy][ux] is None:
                ary[uy][ux] = ary[y][x] + 1
                update_q.append((uy, ux))
        if x < w-1:
            uy, ux = y, x+1
            if ary[uy][ux] is None:
                ary[uy][ux] = ary[y][x] + 1
                update_q.append((uy, ux))
        if y > 0:
            uy, ux = y-1, x
            if ary[uy][ux] is None:
                ary[uy][ux] = ary[y][x] + 1
                update_q.append((uy, ux))
        if y < h-1:
            uy, ux = y+1, x
            if ary[uy][ux] is None:
                ary[uy][ux] = ary[y][x] + 1
                update_q.append((uy, ux))
    return ary, update_q


black_count = len(update_q)
update_count = 0
while black_count < w * h:
    ary, update_q = update(ary, update_q)
    black_count += len(update_q)
    update_count += 1


print(update_count)
### BUGGY CODE ###

n=int(input())
a=[int(_) for _ in input().split()]
ans=-10**15
for i in range(n,2*n+1):ans=max(ans, sum(sorted(a[:i])[::-1][:n])-sum(sorted(a[i:])[:n]))
print(ans)

### FIXED CODE ###

from heapq import heappush,heappop
n=int(input()); a=[int(_) for _ in input().split()]
fh=[]; lh=[]
for i in range(n):
    heappush(fh, a[i])
    heappush(lh, -1*a[-i-1])
f=[sum(fh)]; l=[-1*sum(lh)]
for i in range(n,2*n):
    heappush(fh, a[i]); f.append(f[-1]+a[i]-heappop(fh))
    heappush(lh, -1*a[-i-1]); l.append(l[-1]+a[-i-1]+heappop(lh))
ans=-10**15
for i,j in zip(f,l[::-1]):ans=max(ans, i-j)
print(ans)
### BUGGY CODE ###

k = int(input())
number = 7
cnt = 1
if k % 2 == 0:
    print(-1)
    exit()
while 1:
    if number % k == 0:
        print(cnt)
        break
    else:
        cnt += 1
        number = number + 7 * 10 ** (cnt - 1)


### FIXED CODE ###

k = int(input())
mod = 7 % k
cnt = 1
answer = -1

for i in range(k):
    if mod == 0:
        answer = cnt
        break
    else:
        cnt += 1
        mod = (mod * 10 + 7) % k
print(answer)
### BUGGY CODE ###

n = int(input())
apple = []
for _ in range(n):
    apple.append(str(input()))
orange = []

if len(set(apple)) == len(apple):
    orange = []
else:    
    for i in apple:
        if i not in orange:
            orange.append(i)
        else:
            orange.remove(i)
print(len(orange))

### FIXED CODE ###

n = int(input())
apple = []
for _ in range(n):
    apple.append(int(input()))
apple = sorted(apple)
apple.append(0)
count = 0
ans = 1
for i in range(n):
    if apple[i] == apple[i + 1]:
        ans += 1
    else:
        if ans%2 == 0:
            ans = 1
        else:
            count += 1
print(count)
### BUGGY CODE ###

import sys
import numpy as np

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

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

p_a = 0
for i in range(n-k+1):
    p_r = p[i:i+k]
    p_b = 0
    for j in p_r:
        if j == 1:
            p_b += 1
        else:
            p_b += (j + 1) / 2
    if p_b > p_a:
        p_a = p_b
print(p_a)

### FIXED CODE ###

import sys
import numpy as np

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

p = np.array([list(map(int, input().split()))]).reshape(-1)

sum_max = p[:k].sum()
mx = sum_max
index_max = -1
for i in range(1, n-k+1):
    mx += p[i+k-1]
    mx -= p[i-1]
    if mx > sum_max:
        sum_max = mx
        index_max = i
print(str((sum_max+k) / 2))
### BUGGY CODE ###

n=int(input())
plan=[None]*n
for i in range(n):
  p=list(map(int,input().split()))
  for j in range(len(p)):
    p[j]=p[j]-1
  plan[i]=p
 
d=0
error=False
while True:
  d=d+1
  done=[True]*n
  thisday=False
  for i in range(n):
    if done[i]==False:
      continue
    if len(plan[i])==0:
      continue
    target=plan[i][0]
    if done[target]==False:
      continue
    if len(plan[target])==0:
      continue
    if plan[target][0]==i:
      # match
      plan[i]=plan[i][1:]
      plan[target]=plan[target][1:]
      done[i]=False
      done[target]=False
      thisday=True
  if thisday==False:
    # no game today
    # check if every plan is finished
    for i in range(len(plan)):
      if len(plan[i])!=0:
        error=True
    break
  
if error:
  print(-1)
else:
  print(d-1)

### FIXED CODE ###

N=int(input())
a=[[0 for j in range(N-1)] for i in range(N)]
for i in range(N):
  line=list(map(int,input().split()))
  for j in range(N-1):
    a[i][j]=line[j]-1
  a[i]=a[i][::-1]
    
q=[]

#seen=[[False for j in range(N)] for i in range(N)]

# 選手nが試合できるならqueに入れる
def check(i):
  if len(a[i])==0:
    return False
  j=a[i][-1]
  if a[j][-1]==i:
    q.append([i,j])
  
for i in range(N):
  check(i)
  
from collections import defaultdict

day=0
while q:
  day+=1
 # q=sorted(q)
  prevQ=q.copy()
  q=[]
  matched=defaultdict(list)
  for p in prevQ:
    i=p[0]
    j=p[1]
    if i>j:
      i,j=j,i
    if matched[i]:
      continue
    a[i].pop()
    a[j].pop()
    check(i)
    check(j)
    matched[i].append(j)
    
for i in range(N):
  if len(a[i])!=0:
    print(-1)
    break
else:
  print(day)
### BUGGY CODE ###

n,m=map(int,input().split())
a=[]
b=[]
C=[]
s=[0 for i in range(n)]
s[0] = "Yes"
 
for i in range(m):
  c,d=map(int,input().split())
  a.append(c)
  b.append(d)
 
def Next(be):
  C.clear()
  for j in be:
    for i in range(len(a)):
      if a[i] == j:
        
        if s[b[i]-1]==0 and 0 == be.count(b[i]):
          C.append(b[i])
          s[b[i]-1]=j
        continue
      if b[i] == j:
        
        if s[a[i]-1]==0 and 0 == be.count(a[i]):
          C.append(a[i])
          s[a[i]-1]=j
        continue
  return C
co=[1]
while True:
  if s.count(0) == 0:
    break
  co = Next(list(co))
 
for i in s:
  print(i)

### FIXED CODE ###

from collections import deque

N, M=map(int,input().split())
a=[]
b=[]
for i in range(M):
  A,B=map(int,input().split())
  a.append(A)
  b.append(B)

graph = [[] for _ in range(N + 1)]
for i in range(M):
  graph[a[i]].append(b[i])
  graph[b[i]].append(a[i])

    # bfs
queue = deque([1])
signposts = [0] * (N + 1)
signposts[1] = 1
while queue:#キューが空になるまで
  u = queue.popleft()
  for v in graph[u]:
    if not signposts[v]:
      signposts[v] = u
      queue.append(v)
 
if all(signposts[2:]):
  print("Yes")
  print("\n".join(map(str, signposts[2:])))
else:
  print("No")
### BUGGY CODE ###

from collections import defaultdict

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

dic = defaultdict(int)
ans1 = defaultdict(int)
ans2 = defaultdict(int)

def calc_patern1(n, ans, dic):
    for k, v in dic.items():
        ans[k] = v * (v - 1) / 2


def calc_patern2(n, ans, dic):
    for k, v in dic.items():
        ans[k] = (v - 1) * (v - 2) / 2

for i in range(n):
    dic[a[i]] += 1
for v in dic.values():
    calc_patern1(v, ans1, dic)
    calc_patern2(v - 1, ans2, dic)
for i in range(n):
    ans = 0
    for k, v in dic.items():
        #print(ans)
        if k == a[i]:
            ans += ans2[k]
        else:
            ans += ans1[k]
    print(int(ans))

### FIXED CODE ###

from collections import defaultdict, Counter

n = int(input())
a = list(map(int, input().split()))
ans = [0] * n
dic = defaultdict(int)
for i in range(n):
    dic[a[i]] += 1

sum = 0
for v in dic.values():
    sum += v * (v - 1) / 2
    
for i in range(n):
    print(int(sum - (dic[a[i]] - 1)))
### BUGGY CODE ###

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

def exp_k(s, k):
    exp_sum = 0
    for i in range(s, s+k):
        exp = (P[i] * (P[i] + 1) / 2) / P[i]
        exp_sum += exp
    return exp_sum

exp_max = 0
for i in range(n-k+1):
    a = exp_k(i, k)
    if a > exp_max:
        exp_max = a
print(exp_max)

### FIXED CODE ###

import itertools
N, K = map(int, input().split())
p = list(map(int, input().split()))

pos = [(p[i]+1)/2 for i in range(N)]

pos_acum = list(itertools.accumulate(pos))

ans = pos_acum[K-1]
for i in range(N-K):
    ans = max(ans, pos_acum[K+i]-pos_acum[i])
print(ans)
### BUGGY CODE ###

i = int(input())

count = 0;

for j  in range(i+1):
    lst = []
    while j > 0:
        lst.append(j%10)
        j //= 10 # 必須
    lst.reverse()
    
    flag3 = 3 in lst
    flag5 = 5 in lst
    flag7 = 7 in lst
    
    flag0 = 0 in lst
    flag1 = 1 in lst
    flag2 = 2 in lst
    flag4 = 4 in lst
    flag6 = 6 in lst
    flag8 = 8 in lst
    flag9 = 9 in lst

    if not flag0 and not flag1 and not flag2 and not flag4 and not flag6 and not flag8 and not flag9 :
        if flag3 and flag5 and flag7 :
            count = count + 1
            
print(count)

### FIXED CODE ###

N = int(input())
ans = 0

def f(target):
    for i in '753':
        targetJoin = str(target) + str(i)
        
        if int(targetJoin) > N:
            continue

        if  '7' in targetJoin and '5' in targetJoin and '3' in targetJoin :
            
            flag = True
            if '0' in targetJoin:
                flag = False
            if '1' in targetJoin:
                flag = False
            if '2' in targetJoin:
                flag = False
            if '4' in targetJoin:
                flag = False
            if '6' in targetJoin:
                flag = False
            if '8' in targetJoin:
                flag = False
            if '9' in targetJoin:
                flag = False
            
            if flag :
                global ans
                ans+=1
                
        f(targetJoin)
        
f(3)
f(5)
f(7)
print(ans)
### BUGGY CODE ###

N = int(input())
a = {}
for i in range(N):
    a[i + 1] = int(input())

i = 1
before_i = None
cnt = 0
while True:
    next_i = a[i]
    cnt += 1
    if next_i in [1, i, before_i]:
        print(-1)
        break
    elif next_i == 2:
        print(cnt)
        break

    before_i = i
    i = next_i

### FIXED CODE ###

N = int(input())
a = {}
for i in range(N):
    a[i + 1] = int(input())

i = 1
cnt = 0
while True:
    next_i = a[i]
    cnt += 1
    if next_i < 1:
        print(-1)
        break
    elif next_i == 2:
        print(cnt)
        break

    a[i] = 0
    i = next_i
### BUGGY CODE ###

import math

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

i = 1
maxnum = 1
while i <= N:
    if (math.floor(A * (i-1) // B) - A * ((i-1) // B)) < math.floor((A * (i) // B) - A * ((i) // B)):
        maxnum = math.floor((A * (i) // B) - A * ((i) // B))
        i = i + 1

print(maxnum)


### FIXED CODE ###

a, b, n = list(map(int, input().split()))
x = min(b - 1, n)
ans = int(a * x / b)
print(ans)
### BUGGY CODE ###

n=int(input());s=input();c=s.count;print(c('R')*c('G')*c('B')-sum(sorted(s[i:j+1:(j-i)//2])==list('BGR')for i in range(n-2)for j in range(i+2,n,2)))

### FIXED CODE ###

n=int(input())
s=input()
c=s.count
r,g,b=c('R'),c('G'),c('B')
t=0
for i in range(n-2):
  for w in range(1,(n-i+1)//2):
    if s[i]+s[i+w]+s[i+w*2] in ('RGB','RBG','GRB','GBR','BRG','BGR'):
        t+=1
print(r*g*b-t)
### BUGGY CODE ###

N,K=map(int,input().split())
A,F=[list(map(int,input().split())) for i in range(2)]
A.sort()
F.sort()
l,r=-1,10**18
while r-l>1:
    h=(l+r)//2
    k=0
    for i in range(N):
        k+=max(0,A[i]-h//F[-i-1])
        if k>K:
            k=-1
            break
    if k>=0:
        r=h
    else:
        l=h
print(r)

### FIXED CODE ###

N,K=map(int,input().split())
A,F=[list(map(int,input().split())) for i in range(2)]
A.sort()
F.sort()
l,r=-1,10**18
while r-l>1:
    h=(l+r)//2
    k=0
    for i in range(N):
        k+=max(0,A[i]-h//F[-i-1])
        if k>K:
            k=-1
            break
    if k>=0:
        r=h
    else:
        l=h
print(r)
### BUGGY CODE ###

N = int(input())
power = 1
for i in range(N):
    power *= (i+1)
print(power%(10**9 +7))

### FIXED CODE ###

N = int(input())
power = 1
for i in range(N):
    power *= (i+1)
    power = power%(10**9 +7)
print(power)
### BUGGY CODE ###

N = int(input())
X = list(map(int,input().split()))
B = [0]*(N-1)
mid = int(N/2)-1
for i in range(N):
    B = X[:i]+X[i+1:]
    B.sort()
    print(B[mid])

### FIXED CODE ###

N = int(input())
X = list(map(int,input().split()))
B = [i for i in X]
B.sort()
mid_s = B[int(N/2)-1]
mid_l = B[int(N/2)]
for i in range(N):
    if X[i] <= mid_s:
        print(mid_l)
    elif X[i] >= mid_l:
        print(mid_s)
### BUGGY CODE ###

n,x,y=map(int,input().split())
g=[[]*n for i in range(n)]
for i in range(n-1):
    g[i].append(i+1)
    g[i+1].append(i)
g[x-1].append(y-1)
g[y-1].append(x-1)

from collections import deque
distance=[]

for i in range(n):
    option=deque()
    option.append(i)
    completed=[False]*n
    memo=[0]*n
    while option:
        now=option.popleft()
        completed[now]=True
        for j in g[now]:
            if completed[j]==False and j not in option:
                memo[j]=memo[now]+1
                option.append(j)
    distance.append(memo)

ans=[0]*n
for i in range(n-1):
    for j in range(i+1,n):
        ans[distance[i][j]-1]+=1

for i in range(n-1):
    print(ans[i])
        

### FIXED CODE ###

import heapq
import sys

input = sys.stdin.readline

def dijkstra_heap(s,edge):
    #始点sから各頂点への最短距離
    d = [10**20] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d

################################
n,s,t = map(int,input().split()) #n:頂点数　w:辺の数
w=n-1

edge = [[] for i in range(n)]
#edge[i] : iから出る道の[重み,行先]の配列
for i in range(w):
    x,y=i,i+1 #0-indexed
    edge[x].append([1,y])
    edge[y].append([1,x]) 
edge[s-1].append([1,t-1])
edge[t-1].append([1,s-1]) 

distance=dijkstra_heap(0,edge)
memo=[0]*n

for i in range(n-1):#i to j
    for j in range(i+1,n):
        if s-1<i<t-1:#s==2,t==4
            tmp=min(j-i,distance[i]+distance[j]-distance[s-1]*2)
        else:
            tmp=distance[j]-distance[i]

        memo[tmp]+=1
for i in range(1,n):
    print(memo[i])
### BUGGY CODE ###

import math
def c(n,r):
    r=min(r,n-r)
    a=math.factorial(n)//(math.factorial(r)*math.factorial(n-r))
    return a
q=1    
N=int(input())
s=list(map(int,input().split()))
n=max(s)
for i in s:
    t=c(n,i)
    if q<=t:
        q=t
        w=str(n)+" "+str(i)
print(w)        
    

### FIXED CODE ###

N=int(input())
s=list(map(int,input().split()))
n=max(s)
s.remove(n)
q=n
for i in s:
    t=abs(n/2-i)
    if q>=t:
        q=t
        w=str(n)+" "+str(i)
print(w)
### BUGGY CODE ###

n, k = map(int, input().split())
h = sorted([int(input()) for i in range(n)])
diff = [h[i+1] - h[i] for i in range(n-1)]
ans = float("inf")

for i in range(n-k+1):
    ans = min(ans, sum(diff[i:i+k-1]))
print(ans)

### FIXED CODE ###

n, k = map(int, input().split())
h = sorted([int(input()) for i in range(n)])
ans = float("inf")

for i in range(n-k+1):
    ans = min(ans, h[i+k-1]-h[i])
print(ans)
### BUGGY CODE ###

# coding: utf-8
# Your code here!

import numpy as np

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

a.sort()
f.sort(reverse=True)

for i in range(k):
    ans = [i*j for i, j in zip(a, f)]
    a[np.argmax(ans)] -= 1
    
ans = [i*j for i, j in zip(a, f)]
print(max(ans))

### FIXED CODE ###

# coding: utf-8
# Your code here!

import math
import sys

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

al.sort()
fl.sort(reverse=True)

ub = max([a*f for a,f in zip(al, fl)])
lb = 0

while True:
    if ub == lb:
        print(lb)
        sys.exit()
    p = 0
    t = (ub + lb) // 2
    for a, f in zip(al, fl):
        p += max(a - t // f, 0)
    if p <= k:
        ub = t
    else:
        lb = t + 1
### BUGGY CODE ###

import queue
n, x, y = map(int, input().split())

graph = {i: [] for i in range(1, n + 1)}
graph[x].append(y)
graph[y].append(x)
for i in range(1, n):
    graph[i].append(i + 1)
    graph[i + 1].append(i)

tf = [[False] * (n + 1) for i in range(n + 1)]
ans = [0] * (n + 1)
def bfs(v):
    q = queue.Queue()
    q.put([v, 0, v])
    voi[v] = True
    while not q.empty():
        sub = q.get()
        now = sub[0]
        depth = sub[1]
        before = sub[2]
        if tf[now][v] == False:
            ans[depth] += 1
            tf[now][v] = True
            tf[v][now] = True
        for next in graph[now]:
            if voi[next]:
                continue
            voi[next] = True
            q.put([next, depth + 1, now])

for i in range(1, n + 1):
    voi = [False] * (n + 1)
    bfs(i)

for i in range(1, n):
    print(ans[i])

### FIXED CODE ###

n, x, y = map(int, input().split())

ans = [0] * (n + 1)
for i in range(1, n):
    for j in range(i + 1, n + 1):
        sub = min(abs(j - i), abs(x - i) + 1 + abs(j - y), abs(y - i) + 1 + abs(j - x))
        ans[sub] += 1

for i in range(1, n):
    print(ans[i])
### BUGGY CODE ###

N, K = [int(n) for n in input().split()]

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

count = 0
for i in range(1,N+1):
    for j in range(1,min(K,N-i+1)+1):
        if sum(A[i-1:i+j-1],0) % K == j:
            count += 1

print(count)

### FIXED CODE ###

N, K = [int(n) for n in input().split()]

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

count = 0
for i in range(1,N+1):
    A[i-1] = A[i-1]-1

check = {0: [0,1,[0]]}

s = 0
for i in range(1,N+1):
    s = (s + A[i-1]) % K
    if s in check:
        j = check[s][0]
        l = check[s][1]
        while j < l and i - check[s][2][j] >= K:
            j += 1
        check[s][0] = j
        count += l - j
        check[s][2].append(i)
        check[s][1] = l + 1
    else:
        check[s] = [0,1,[i]]

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

N=int(input())
S=list(map(int,input().split()))
first=len(S)
count=0
pos=0
mokuteki=1
while count<N:
    if S[pos]!=mokuteki:
        ret=S.pop(pos)
    else:
        mokuteki+=1
        pos+=1
    count+=1

if len(S)>0:
    print(first-len(S))
else:
    print(-1)

### FIXED CODE ###

N=int(input())
S=list(map(int,input().split()))
first=len(S)
count=0
pos=0
mokuteki=1
block=0
while count<N:
    if S[pos]!=mokuteki:
        pos+=1
        block+=1
    else:
        mokuteki+=1
        pos+=1
    count+=1

if mokuteki>1:
    print(block)
else:
    print(-1)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n, m = map(int, input().split())
val = list(map(int,input().split()))
my_index = val.index
for i in range(m):
  val[my_index(max(val))] = max(val)//2
print(sum(val))

### FIXED CODE ###

import heapq
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
a = [int(i) for i in input().split()]
for i in range(n):
  a[i] *= -1

heapq.heapify(a)
for i in range(m):
    heapq.heapreplace(a, int(a[0] / 2))

print(sum(a)*-1)
### BUGGY CODE ###

import queue
def main():
    n, x, y = map(int, input().split())
#    odd = True
#    if (x+y)%2 == 0:
#        odd = False
#    for q in range(1, n):
#        ans = 0
#        for i in range(1, n):
#            if i <= x:
#                if i + q <= x:
#                    ans += 1
#                else:
#                    buf = i + q - x
#                    if 1 < buf and buf <= n-y + 1:
#                        ans += 1
#                    if buf <= (y-x+1)//2:
#                        if buf == (y-x+1)//2:
#                            if odd:
#                                ans += 2
#                            else:
#                                ans += 1
#                        else:
#                            ans += 2
#            elif i <= y:
#                if q <= (y-x + 1)//2:
    x -= 1
    y -= 1
    ans = [[0]*n for _ in range(n)]
    t = [[i+1, i-1] for i in range(n)]
    t[x].append(y)
    t[y].append(x)
#    print(t)
    q = queue.Queue()
    for i in range(n):
        f = [True]*n
        f[i] = False
        q.put([i, 0])
        while not q.empty():
            a, b = q.get()
            for v in t[a]:
                if 0 < v and v < n:
                    if f[v]:
                        if i < v:
                            ans[i][b + 1] += 1
                        f[v] = False
                        q.put([v, b+1])
    for i in range(1, n):
        p = 0
        for j in range(n):
            p += ans[j][i]
        print(p)
if __name__ == "__main__":
    main()

### FIXED CODE ###

import queue
def main():
    n, x, y = map(int, input().split())
    x -= 1
    y -= 1
    ans = [0]*n
    t = [[i+1, i-1] for i in range(n)]
    t[x].append(y)
    t[y].append(x)
    for i in range(n):
        for j in range(i+1, n):
            if j <= x:
                ans[j-i] += 1
            elif j <= y:
                buf = min(j-i, abs(i-x) + 1 + (y-j))
                ans[buf] += 1
            else:
                buf = min(y-i, abs(x-i)+1)
                ans[buf + (j-y)] += 1
    for i in range(1, n):
        print(ans[i])
if __name__ == "__main__":
    main()
### BUGGY CODE ###

import fractions
import sys

MOD = 10**9+7
input = sys.stdin.readline

def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)

n = int(input())
a = [int(_) for _ in input().split()]
LCM = 1
for i in a:
    LCM = lcm(LCM, i)

ans_arr = [0] * n
for i in range(len(a)):
    ans_arr[i] = LCM // a[i]
print(sum(ans_arr) % MOD)

### FIXED CODE ###

from fractions import gcd
from functools import reduce

MOD = 1000000007

def lcm(x, y):
    return (x * y) // gcd(x, y)

n = int(input())
a = [int(_) for _ in input().split()]
LCM = reduce(lcm, a)

arr = [LCM // _ for _ in a]
print(sum(arr) % MOD)
### BUGGY CODE ###

def main():
  n, p = map(int, input().split()) 
  s = input() 

  ans = 0

  if p == 2:
    for i, si in enumerate(s):
      if int(si) % 2 == 0:
        ans += (i+1)
    print(ans)
    exit()

  if p == 5:
    for i, si in enumerate(s):
      if int(si) % 5 == 0:
        ans += (i+1)
    print(ans)
    exit()

  rem_list = [0] * p

  for i in range(n):
    rem = int(s[i:]) % p
    ans += rem_list[rem]
    if rem == 0:
      ans += 1      
    rem_list[rem] += 1

  print(ans)

if __name__ == "__main__":
  main()

### FIXED CODE ###

def main():
  n, p = map(int, input().split()) 
  s = input() 

  ans = 0

  if p == 2:
    for i, si in enumerate(s):
      if int(si) % 2 == 0:
        ans += (i+1)
    print(ans)
    exit()

  if p == 5:
    for i, si in enumerate(s):
      if int(si) % 5 == 0:
        ans += (i+1)
    print(ans)
    exit()

  rem_list = [0] * p
  cof = 1
  prev_rem = 0
  
  for i in range(n):
    rem = (int(s[n-1-i]) * cof + prev_rem) %  p
    ans += rem_list[rem]
    if rem == 0:
      ans += 1      
    rem_list[rem] += 1

    prev_rem = rem
    cof *= 10
    cof %= p

  print(ans)

if __name__ == "__main__":
  main()