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

# coding: utf-8
# Your code here!
from heapq import heappush, heappop, heapify

n=int(input())
a,b=map(int,input().split())
G=[(a,b)]
que = []
for i in range(n-1):
    x,y=map(int,input().split())
    G.append((x,y))
    heappush(que,(min(abs(a-x),abs(b-y)),i+1))
used = [0 for i in range(n)]
used[0] = 1

ans = 0
while que:
    cv, v = heappop(que)
    if used[v]:
        continue
    used[v] = 1
    ans += cv
    for i in range(n):
        if used[i]:
            continue
        heappush(que, (min(abs(G[i][0]-G[v][0]),abs(G[i][1]-G[v][1])), i))
print(ans)

### FIXED CODE ###

# coding: utf-8
# Your code here!
from heapq import heappush, heappop, heapify
n=int(input())
G=[[]for i in range(n)]
d=[]
for i in range(n):
    a,b=map(int,input().split())
    d.append((a,b,i))
d=sorted(d,key=lambda x:x[0])
for i in range(n-1):
    G[d[i][2]].append((d[i+1][0]-d[i][0],d[i+1][2]))
    G[d[i+1][2]].append((d[i+1][0]-d[i][0],d[i][2]))
d=sorted(d,key=lambda x:x[1])
for i in range(n-1):
    G[d[i][2]].append((d[i+1][1]-d[i][1],d[i+1][2]))
    G[d[i+1][2]].append((d[i+1][1]-d[i][1],d[i][2]))
used = [0 for i in range(n)]
que = [(c, w) for c, w in G[0]]
used[0] = 1
heapify(que)

ans = 0
while que:
    cv, v = heappop(que)
    if used[v]:
        continue
    used[v] = 1
    ans += cv
    for c, w in G[v]:
        if used[w]:
            continue
        heappush(que, (c, w))
print(ans)
### BUGGY CODE ###

(a, b, q) = map(int, input().split())
s = [int(input()) for _ in range(a)]
t = [int(input()) for _ in range(b)]
x = [int(input()) for _ in range(q)]


def find_left_and_right(st, pos):
    for i, s_i in enumerate(st):
        if s_i - pos > 0:
            return (i-1, i)
    return (len(st) - 1, -1)


def find_optimum(ss, ts, pos):
    (sl_index, sr_index) = find_left_and_right(ss, pos)
    (tl_index, tr_index) = find_left_and_right(ts, pos)

    penalty = 9999999999999
    s_left = s[sl_index] if 0 <= sl_index else penalty
    s_right = s[sr_index] if 0 <= sr_index else penalty
    t_left = t[tl_index] if 0 <= tl_index else penalty
    t_right = t[tr_index] if 0 <= tr_index else penalty

    dist0 = abs(s_left - pos) + min(abs(t_left - s_left), abs(t_right - s_left))
    dist1 = abs(s_right - pos) + min(abs(t_left - s_right), abs(t_right - s_right))
    dist2 = abs(t_left - pos) + min(abs(s_left - t_left), abs(s_right - t_left))
    dist3 = abs(t_right - pos) + min(abs(s_left - t_right), abs(s_right - t_right))
    return min([dist0, dist1, dist2, dist3])


for x_i in x:
    print(find_optimum(s, t, x_i))

### FIXED CODE ###

import bisect

(a, b, q) = map(int, input().split())
s = [-10 ** 19]
for _ in range(a):
    s.append(int(input()))
s.append(10 ** 19)
t = [-10 ** 19]
for _ in range(b):
    t.append(int(input()))
t.append(10 ** 19)
x = [int(input()) for _ in range(q)]

for x_i in x:
    ss = bisect.bisect_left(s, x_i)
    tt = bisect.bisect_left(t, x_i)

    sc = [ss - 1, ss]
    tc = [tt - 1, tt]
    optimum = 10 ** 19
    for s_i in sc:
        for t_i in tc:
            dist = abs(s[s_i] - x_i) + abs(s[s_i] - t[t_i])
            if dist < optimum:
                optimum = dist
            dist = abs(t[t_i] - x_i) + abs(t[t_i] - s[s_i])
            if dist < optimum:
                optimum = dist
    print(optimum)
### BUGGY CODE ###

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

for i in range(1, N+1):
  print(A.count(i))

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
answer = [0] * N

for i in A:
  answer[i-1] += 1

for n in answer:
  print(n)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
MAX = 1000000

N, M = map(int, input().split())
ab = [0]*M
C = [0]*M
for i in range(M):
    ab[i] = list(map(int, input().split()))
    c = list(map(int, input().split()))
    for cc in c:
        C[i] += (1<<(cc-1)) # bit

dp = [[MAX]*(2**N) for _ in range(M)]
dp[0][0] = 0

for i in range(M-1):
#    for p in range(M):
#        print(dp[p])
    for j in range(1<<N):
        dp[i+1][j] = min(dp[i+1][j], dp[i][j])
        dp[i+1][j|C[i]] = min(dp[i+1][j|C[i]], dp[i][j]+ab[i][0])

res = dp[-1][-1]
if res == MAX:
    print(-1)
else:
    print(res)

### FIXED CODE ###

import sys
input = sys.stdin.readline
MAX = 1000000

N, M = map(int, input().split())
ab = [0]*M
C = [0]*M
for i in range(M):
    ab[i] = list(map(int, input().split()))
    c = list(map(int, input().split()))
    for cc in c:
        C[i] += (1<<(cc-1)) # bit

dp = [[MAX]*(2**N) for _ in range(M)]
dp[0][0] = 0

for i in range(M-1):
#    for p in range(M):
#        print(dp[p])
    for j in range(1<<N):
        dp[i+1][j] = min(dp[i+1][j], dp[i][j])
        dp[i+1][j|C[i]] = min(dp[i+1][j|C[i]], dp[i][j]+ab[i][0])

res = dp[-1][-1]
if res == MAX:
    print(-1)
else:
    print(res)
### BUGGY CODE ###

n, k = map(int, input().split())
h_list = list(map(int, input().split()))
cost_list = [0, abs(h_list[0] - h_list[1])]
for i, hi in enumerate(h_list):
    if i >= 2:
        cost = 10 ** 9
        start = max(i - k, 0)
        for j, hj in enumerate(h_list):
            if j >= start:
                if i > j:
                    cost = min(cost, abs(hj - hi) + cost_list[j])
                else:
                    break
        cost_list.append(cost)
print(cost_list[-1])


### FIXED CODE ###

import numpy as np

n, k = map(int, input().split())
h_arr = np.array(list(map(int, input().split())))
cost_arr = np.zeros(n, dtype=int)
for i in range(1, n):
    start = max(i-k, 0)
    cost_arr[i] = (abs(h_arr[start:i] - h_arr[i]) + cost_arr[start:i]).min()
print(int(cost_arr[-1]))
### BUGGY CODE ###

import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(1000000000)

N = int(input())
MOD = 10**9 + 7

neighbor = [[] for _ in range(N)]
for _ in range(N-1):
    x,y = map(int, input().split())
    neighbor[x-1].append(y-1)
    neighbor[y-1].append(x-1)

memo = [[-1]*2 for _ in range(N)]

def dp(node, color, parent):
    if memo[node][color] != -1:
        return memo[node][color]
    output = 1
    for child in neighbor[node]:
        if child == parent:
            pass
        else:
            tmp = dp(child, 0, node)
            if color == 0:
                tmp += dp(child, 1, node)
            output *= tmp
            output %= MOD
    memo[node][color] = output
    return output

print((dp(0,0,-1) + dp(0,1,-1)) % MOD)

### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(1000000000)

N, *XY = map(int,open(0).read().split())
MOD = 10**9 + 7

neighbor = [[] for _ in range(N)]
for x,y in zip(*[iter(XY)]*2):
    neighbor[x-1] += y-1,
    neighbor[y-1] += x-1,

parent = {0}

def dp(node):
    black_output = white_output = 1
    for child in neighbor[node]:
        if child in parent:
            continue
        else:
            parent.add(child)
            tmp_black, tmp_white = dp(child)
            black_output *= tmp_white
            white_output *= tmp_black + tmp_white
    black_output %= MOD
    white_output %= MOD
    return black_output, white_output

print(sum(dp(0)) % MOD)
### BUGGY CODE ###

a, b = map(int, input().split())
ans = []

for i in range(1,min(a,b)+1):
    if a%i == 0 and b%i ==0:
        while True:
            for j in range(2,i):
                if i%j==0:
                    break
            else:
                ans.append(i)
            break
            
print(len(ans))
        

### FIXED CODE ###

import collections

def gcd(x, y):
    if y == 0:
        return x
    return gcd(y, x%y)

def trial_division(n):
    a = []  
    while n % 2 == 0:
        a.append(2)
        n /= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n /= f
        else:
            f += 2   
    if n != 1: a.append(n)
    return a

def main():
    a, b = map(int, input().split())
    c = collections.Counter(trial_division(gcd(a, b)))
    print(len(c.keys())+1)

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

n=int(input())
a=list(map(int,input().split()))
mod=10**9+7
f=True
if n%2==1:
    if a.count(0)!=1:
        f=False
    for i in  range(2,n,2):
        if a.count(i)!=2:
            f=False
else:
    for i in range(1,n,2):
        if a.count(i)!=2:
            f=False
if f:
    print((2**(n//2))%mod)
else:
    print(0)


### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
a.sort()
mod=10**9+7
f=True
if n==1:
    if a[0]==0:
        print(1)
    else:
        print(0)
    exit()
if n%2==1:
    if a[0]!=0 or a[1]==0:
        f=False
    for i in range(1,n-1,2):
        if not (a[i]==i+1 and a[i+1]==i+1):
            f=False
else:
    for i in range(0,n,2):
        if not (a[i]==i+1 and a[i+1]==i+1):
            f=False
if f:
    print((2**(n//2))%mod)
else:
    print(0)
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
ans=1
for i in a:
    ans*=i
if ans>10**18:
    print(-1)
else:
    print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
ans=1
if 0 in a:
    ans=0
else:
    for i in a:
        ans*=i
        if ans>10**18:
            ans=-1
            break
print(ans)
### BUGGY CODE ###

def main(n,a):
  import numpy as np
  a=np.array([a[i]-i for i in range(n)])
  #print(a)
  #print(len(a[a<0]))
  #print(len(a[a>0]))
  if len(a[a<0])==len(a[a>0]):
    print(sum(list(map(abs,a))))
    exit()
  elif len(a[a<0])>len(a[a>0]):
    while len(a[a<0])>len(a[a>=0]):
      a+=1
    print(sum(list(map(abs,a))))
    exit()
  elif len(a[a<0])<len(a[a>0]):
    while len(a[a<=0])<len(a[a>0]):
      a-=1
    print(sum(list(map(abs,a))))
    exit()
if __name__=='__main__':
  import sys
  input = sys.stdin.readline
  n=int(input())
  a=list(map(int,input().split()))
  main(n,a)


### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
for i in range(n):
    a[i] -= i + 1
a.sort()
b1 = a[n // 2]
b2 = a[(n // 2 ) - 1]
r1=0
r2=0
for i in range(n):
    r1+=abs(a[i]-b1)
    r2+=abs(a[i]-b2)
print(min(r1,r2))
### BUGGY CODE ###

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

ans = 0
for i in range(1, M+1):
    d, m = divmod(M, i)
    if m == 0 and d >= N:
        ans = i
    if d < N:
        break

print(ans)


### FIXED CODE ###

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


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

K = divisor(M)

ans = 0
for k in K:
    if N * k <= M:
        ans = max(ans, k)


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

#N is numbers of BAITO, M is limit of days
N,M=map(int,input().split())

i=0
inp ={}
while i<N:
  readTime,inCome=map(int,input().split())
  if readTime in inp:
    inp[readTime].append(inCome)
  else:
    inp[readTime]=[inCome]
  
  i=i+1

#print(inp)  

result=0
pool=[]
i=1
while i<=M:
  if i in inp:
	  pool=pool+inp[i]
  #print(i,pool)
  
  if len(pool)>0:
    result=result+max(pool)
    pool.remove(max(pool))
    #print(pool)
  
  i=i+1
 
print(result)

### FIXED CODE ###

import heapq

#N is numbers of BAITO, M is limit of days
N,M=map(int,input().split())
 
i=0
inp ={}
while i<N:
  readTime,inCome=map(int,input().split())
  if readTime in inp:
    inp[readTime].append(-inCome)
  else:
    inp[readTime]=[-inCome]
  
  i=i+1
 
#print(inp)  
 
result=0
pool=[]
heapq.heapify(pool)
i=1
while i<=M:
  if i in inp:
    for k in inp[i]:
      heapq.heappush(pool,k)
  if len(pool)>0:
    result=result-heapq.heappop(pool)
  i=i+1
 
print(result)
### BUGGY CODE ###

a = input()

a = int(a)

b = [int(x) for x in input().split(' ')]

b.sort()

from itertools import combinations

comb = combinations(b, 3)

possible_triangles = 0

first_num = -1
second_num = -1

skip = False

for i in comb:
    if skip:
        if i[0] == first_num and i[1] == second_num:
            continue
        else:
            skip = False
    if i[2] >= i[0] + i[1]:
        first_num = i[0]
        second_num = i[1]
        skip = True
        continue
    possible_triangles += 1

print(possible_triangles)

### FIXED CODE ###

number_of_sticks = int(input())

sticks = [int(x) for x in input().split(' ')]

sticks.sort()

triangles = 0

import bisect

for i in range (number_of_sticks - 2):
    for j in range (i+2, number_of_sticks):
        max_range = j
        min_range = max(bisect.bisect(sticks, sticks[j] - sticks[i]), i + 1)
        triangles += max_range - min_range

print(triangles)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**8)

N, Q = map(int, input().split())
a = []
p = []
x = [0]*(N)
A = [0]*(N)

for i in range(N-1):
    t=list(map(int,input().split()))
    if t[0]>t[1]:
        swap = t[1]
        t[1] = t[0]
        t[0] =swap
    a.append((int(t[0]),int(t[1])))
for i in range(Q):
    t=list(map(int,input().split()))
    p.append((int(t[0]),int(t[1])))

a =sorted(a, key=lambda x: x[0])
p =sorted(p, key=lambda x: x[0])

#print(a)
for i in range(Q):
    x[p[i][0]-1] += p[i][1]
for i in range(N):
    A[i] = x[i]
for i in range(N-1):
    La = a[i][0]-1
    Lb = a[i][1]-1

    A[Lb] = A[La]+x[Lb]

print(' '.join(map(str, A)))


### FIXED CODE ###


N, Q = map(int, input().split())
a = []
p = []
x = [0]*(N)
A = [0]*(N)

for i in range(N-1):
    t=list(map(int,input().split()))
    if t[0]>t[1]:
        swap = t[1]
        t[1] = t[0]
        t[0] =swap
    a.append((int(t[0]),int(t[1])))
for i in range(Q):
    t=list(map(int,input().split()))
    p.append((int(t[0]),int(t[1])))

a =sorted(a, key=lambda x: x[0])
p =sorted(p, key=lambda x: x[0])

#print(a)
for i in range(Q):
    x[p[i][0]-1] += p[i][1]
for i in range(N):
    A[i] = x[i]
for i in range(N-1):
    La = a[i][0]-1
    Lb = a[i][1]-1

    A[Lb] = A[La]+x[Lb]

print(' '.join(map(str, A)))
### BUGGY CODE ###

#!/usr/bin/env python3
# -*- coding:utf-8 -*-

def prime(ulim=10**5+10):
  cands = [2] + list(range(3, ulim, 2))
  while len(cands) != 0:
    prime = cands.pop(0)
    cands = [x for x in cands if x%prime != 0]
    yield prime

if __name__=='__main__':
  x = int(input())
  for p in prime():
    if p >= x:
      print(p)
      break

### FIXED CODE ###

#!/usr/bin/env python3
# -*- coding:utf-8 -*-

from math import sqrt

def prime(ulim=10**5+10):
  cands = [2] + list(range(3, ulim, 2))
  primes = []
  while True:
    prime = cands.pop(0)
    primes.append(prime)
    if prime > sqrt(ulim):
      primes += cands
      break
    cands = [x for x in cands if x%prime != 0]
  return primes


if __name__=='__main__':
  x = int(input())
  for p in prime():
    if p >= x:
      print(p)
      break
### BUGGY CODE ###

N, K = map(int, input().split())
an = []
for i in range(N):
  a, b = map(int, input().split())
  for j in range(b):
    an.append(a)
an.sort()
ans = an[K-1]
print(ans)

### FIXED CODE ###

N, K = map(int, input().split())
a = [list(map(int, input().split())) for i in range(N)]
a.sort()
ans = a[0][0]
b = a[0][1]
i = 1
while b < K:
  ans = a[i][0]
  b += a[i][1]
  i += 1
print(ans)
### BUGGY CODE ###

def cnt_car(w, p):
    car = 1
    wi = 0
    for i in w:
        if (wi + i) <= p:
            wi += i
        else:
            car += 1
            wi = i
    return car

n, k = map(int, input().split())
w = [int(input()) for i in range(n)]
p = max(w)
while True:
    if cnt_car(w, p) <= k:
        print(p)
        break
    else:
        p += 1


### FIXED CODE ###

def cnt_car(w, p):
    car = 1
    wi = 0
    for i in w:
        if (wi + i) <= p:
            wi += i
        else:
            car += 1
            wi = i
    return car

n, k = map(int, input().split())
w = [int(input()) for i in range(n)]
p = max(max(w), sum(w) // k)
while True:
    if cnt_car(w, p) <= k:
        print(p)
        break
    else:
        #print("failed: ", p, cnt_car(w, p))
        if cnt_car(w, p + 100) > k:
            p += 100
        else:
            p += 1
### BUGGY CODE ###

from collections import defaultdict
from fractions import Fraction

N = int(input())
X = [tuple(map(int, input().split())) for _ in range(N)]

MOD = 1000000007
d_plus = defaultdict(int)  # + or ∞
d_minus = defaultdict(int)  # - or 0
ans = 1
ans_00 = 0
for i, (a, b) in enumerate(X):
    if a == 0 and b == 0:
        ans_00 += 1
    elif a == 0:
        d_minus[0] += 1
    elif b == 0:
        d_plus[float('inf')] += 1
    elif a * b > 0:
        d_plus[Fraction(a, b)] += 1
    else:
        d_minus[Fraction(a, b)] += 1


def pair(p):
    if p == 0:
        return float('inf')
    elif p == float('inf'):
        return 0
    else:
        return -1 / p


for m in d_minus:
    d_plus[pair(m)] += 0
for p in d_plus:
    ans = ans * (pow(2, d_plus[p], MOD) + pow(2, d_minus[pair(p)], MOD) - 1)
    ans %= MOD
print((ans - 1 + ans_00) % MOD)


### FIXED CODE ###

from collections import defaultdict
from math import gcd

N = int(input())

MOD = 1000000007
d_plus = defaultdict(int)  # + or ∞
d_minus = defaultdict(int)  # - or 0
ans = 1
ans_00 = 0
for i in range(N):
    a, b = map(int, input().split())
    if a == 0 and b == 0:
        ans_00 += 1
    elif a == 0:
        d_minus[0] += 1
    elif b == 0:
        d_plus[float('inf')] += 1
    else:
        g = gcd(a, b)
        if (a > 0) ^ (b > 0):
            d_plus[(abs(a // g), abs(b // g))] += 1
        else:
            d_minus[(abs(a // g), -abs(b // g))] += 1


def pair(p):
    if p == 0:
        return float('inf')
    elif p == float('inf'):
        return 0
    else:
        a, b = -p[1], p[0]
        if a < 0:
            a, b = -a, -b
        return a, b


for m in d_minus:
    d_plus[pair(m)]
for p in d_plus:
    ans *= (pow(2, d_plus[p], MOD) + pow(2, d_minus[pair(p)], MOD) - 1)
    ans %= MOD
print((ans - 1 + ans_00) % MOD)
### BUGGY CODE ###

N, K = list(map(int, input().split()))
S = [1 if x=='R' else -1 for x in input()]

for i in range(K):
    l = -1
    for j in range(1, N):
        if S[j] != S[j-1]:
            l = j
            break
    if l == -1:
        break

    r = N - 1
    for j in range(l, N-1):
        if S[j] != S[j+1]:
            r = j
            break
    
    temp = [-S[l + i] for i in range(r - l + 1)]
    temp.reverse()
    for i in range(r - l + 1):
        S[l + i] = temp[i]

S.insert(0, 1)
S.append(-1)
ans = 0
for i in range(N):
    x = S[i+1]
    y = S[i+1+x]
    if x == y:
        ans += 1

print(ans)

### FIXED CODE ###

N, K = list(map(int, input().split()))
S = [1 if x=='R' else -1 for x in input()]
cnt = 0
rule = S[0]
f = False
for i in range(1, N):
    if S[i] != rule:
        f = True
        S[i] *= -1
    else:
        if f:
            f = False
            cnt += 1
    if cnt >= K:
        break

S.insert(0, 1)
S.append(-1)
ans = 0
for i in range(N):
    x = S[i+1]
    y = S[i+1+x]
    if x == y:
        ans += 1

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

H,W = map(int,input().split())
S = []
for i in range(H):
  S.append(input())

m = [[0 for i in range(W)] for j in range(H)]
#yoko
for i in range(H):
  s = S[i]
  mar = 0
  cnt = 0
  for j in range(W):
    if s[j] == ".":
      cnt += 1
    if s[j] == "#":
      for k in range(mar,j):
        m[i][k] += cnt
      cnt = 0
      mar = j+1    
    #グリッドの端の処理
    if j == W-1 and s[j] == ".":
      for k in range(mar,j+1):
        m[i][k] += cnt


#tate      
for i in range(W):
  mar = 0
  cnt = 0
  for j in range(H):
    if S[j][i] == ".":
      cnt += 1
    if S[j][i] == "#":
      for k in range(mar,j):
        m[k][i] += cnt
      cnt = 0
      mar = j+1 
    #グリッドの端の処理
    if j == H-1 and S[j][i] == ".":
      for k in range(mar,j+1):
        m[k][i] += cnt


ans = 0
for i in range(H):
  ans = max(ans,max(m[i]))
print(ans-1)  

### FIXED CODE ###

H,W = map(int,input().split())
S = []
for i in range(H):
  S.append(input())

m = [[0 for i in range(W)] for j in range(H)]
#yoko
for i in range(H):
  s = S[i]
  mar = 0
  cnt = 0
  for j in range(W):
    if s[j] == ".":
      cnt += 1
    if s[j] == "#":
      for k in range(mar,j):
        m[i][k] += cnt
      cnt = 0
      mar = j+1    
    #グリッドの端の処理
    if j == W-1 and s[j] == ".":
      for k in range(mar,j+1):
        m[i][k] += cnt


#tate      
for i in range(W):
  mar = 0
  cnt = 0
  for j in range(H):
    if S[j][i] == ".":
      cnt += 1
    if S[j][i] == "#":
      for k in range(mar,j):
        m[k][i] += cnt
      cnt = 0
      mar = j+1 
    #グリッドの端の処理
    if j == H-1 and S[j][i] == ".":
      for k in range(mar,j+1):
        m[k][i] += cnt


ans = 0
for i in range(H):
  ans = max(ans,max(m[i]))
print(ans-1)
### BUGGY CODE ###

from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n,p = inpl()
s = input()[::-1]
res = 0
if p == 2 or p == 5:
    s = s[::-1]
    for i,t in enumerate(s):
        if int(t)%p == 0: res += i+1
    print(res)
    quit()
now = 0
d = defaultdict(int)
d[0] = 1
for i,t in enumerate(s):
    now += int(t) * pow(10,i)
    # print(now)
    d[now%p] += 1
for key in list(d):
    v = d[key]
    res += v*(v-1)//2
print(res)

### FIXED CODE ###

from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n,p = inpl()
s = input()[::-1]
res = 0
if p == 2 or p == 5:
    s = s[::-1]
    for i,t in enumerate(s):
        if int(t)%p == 0: 
            res += i+1
    print(res)
    quit()
now = 0
d = [0] * p
d[0] = 1
for i,t in enumerate(s):
    now += int(t) * pow(10,i,p)
    now %= p
    d[now] += 1
for i in range(p):
    v = d[i]
    res += v*(v-1)//2
print(res)
### BUGGY CODE ###

X = int(input())
t = X**(0.2)
if t.is_integer():
    print(int(t),0)
else:
    b = 1
    while(True):
        k = b**5
        t = (X+k)**(0.2)
        if t.is_integer():
            print(int(t),b)
            break
        if X >= k:
            t = (X-k)**(0.2)
            if t.is_integer():
                print(int(t),-b)
                break
        b += 1

### FIXED CODE ###

import sys
X = int(input())
for i in range(-1000,1000):
    for j in range(-1000,1000):
        if i**5 - j**5 == X:
            print(i,j)
            sys.exit()
### BUGGY CODE ###

S = input()
Q = int(input())
query = []
for _ in range(Q):
    q = list(input().split())
    if len(q) != 1:
        q = [int(x) for x in q[:2]] + [q[2]]
    else:
        q = list(map(int, q)) + [0, '']
    query.append(q)

forward = 1
for t, f, c in query:
    if t == 1:
        forward *= -1
    else:
        if f == 1:
            if forward == 1:
                S = c + S
            else:
                S = S + c
        else:
            if forward == 1:
                S = S + c
            else:
                S = c + S

if forward == -1:
    ans = ''
    for i in range(len(S)):
        ans += S[-i-1]
else:
    ans = S
print(ans)


### FIXED CODE ###

S = input()
Q = int(input())
query = [list(input().split()) for _ in range(Q)]
forward = 1
f = ''
b = ''
for i in range(Q):
    if query[i][0] == '1':
        forward *= -1
    else:
        if query[i][1] == '1':
            if forward == 1:
                f += query[i][2]
            else:
                b += query[i][2] 
        else:
            if forward == 1:
                b += query[i][2] 
            else:
                f += query[i][2]
S = ''.join(list(reversed(f))) + S + b

if forward == -1:
    ans = ''.join(list(reversed(S)))
else:
    ans = S
print(ans)