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

import numpy as np
import copy
import queue


q = queue.Queue()

n, m = map(int, input().split())
l = [[0 for _ in range(n)] for _ in range(n)]
for i in range(m):
    a, b = map(int, input().split())
    l[a-1][b-1] = 1
    l[b-1][a-1] = 1


l = np.array(l)
lc = copy.deepcopy(l)
li = [-1 for _ in range(n)]

def search(x):
    if sum(lc[x]) == 0:
        q.queue = False
        return
    
    ind_lis = np.where(lc[x] == 1)
#     print(ind_lis)
    for e in ind_lis[0]:
#         print(e+1)
        if li[e] == -1:
            li[e] = x
    for e in ind_lis[0]:
        lc[x][e] =0
        lc[e][x] =0
        q.put(e)
x = 0
search(x)
while q.queue:
    search(q.get())

if li[1:].count(-1) == 0:
    print('Yes')
    for e in li[1:]:
        print(e+1)
else:
    print('No')


### FIXED CODE ###

# import numpy as np
# import copy
from collections import defaultdict
import queue


q = queue.Queue()

n, m = map(int, input().split())
graph = defaultdict(list)
for _ in range(m):
    a, b = map(lambda x: int(x), input().split())
    graph[a].append(b)
    graph[b].append(a)


# l = np.array(l)
# lc = copy.deepcopy(l)
li = [-1 for _ in range(n)]
li[0] = 1

def search(x):
#     if sum(l[x]) == 0:
#         q.queue = False
#         return
    
#     ind_lis = np.where(lc[x] == 1)[0]
#     ind_lis = [e for e in ind_lis if li[e] == -1]
#     print(li)
#     print(lc[x])
    for e in graph[x]:
#         print(e)
        if li[e-1] != -1:
            continue
        li[e-1] = x
#         print('q', i+1)
        q.put(e)
x = 1
search(x)
while q.queue:
    search(q.get())

if li[1:].count(-1) == 0:
    print('Yes')
    for e in li[1:]:
        print(e)
else:
    print('No')
### BUGGY CODE ###

n,m,q=map(int,input().split())

a=[]
b=[]
for i in range(n):
    a.append([0]*(n))
    b.append([0]*(n))

import numpy as np
a=np.array(a)
b=np.array(b)
#print(a)
for i in range(m):
    l,r=map(int,input().split())
    #print(a[(r-1):n,0:l])
    a[r-1,l-1]+=1

for l in range(n):
    for r in range(l,n):
        temp=a[r,l]
        b[r:n,0:l+1]+=temp

#print(a)
#print(b)

for i in range(q):
    P,Q=map(int,input().split())
    print(b[(Q-1),(P-1)])

### FIXED CODE ###

from itertools import accumulate
from operator import add, mul
n,m,q=map(int,input().split())

a=[]
b=[]
for i in range(n):
    a.append([0]*(n))
    b.append([0]*(n))

#import numpy as np
#b=np.array(b)
#print(a)
'''
for i in range(m):
    l,r=map(int,input().split())
    #print(a[(r-1):n,0:l])
    #a[(r-1):n,0:l]+=1
    for j in range(r-1,n):
        for k in range(l):
            a[j][k]+=1
'''
for i in range(m):
    l,r=map(int,input().split())
    #print(a[(r-1):n,0:l])
    a[l-1][r-1]+=1

#print(a)

for i in range(n):
    a[i]=list(accumulate(a[i]))

#print(a)

for i in range(n):
    for j in range(n-i-1):
        a[n-i-j-2][n-i-1]+=a[n-i-j-1][n-i-1]
        #print(a)

#print(a)

'''
for l in range(n):
    for r in range(l,n):
        temp=a[r][l]
        for i in range(r,n):
            for j in range(0,l+1):
                b[i][j]+=temp
        #b[r:n,0:l+1]+=temp
'''
#print(a)
#print(b)

for i in range(q):
    P,Q=map(int,input().split())
    print(a[(P-1)][(Q-1)])
'''
for i in range(que):
    p,q=MI()
    if p==1:
        ans=lis[q-1][q-1]
    else:
        ans=lis[q-1][q-1]-lis[p-2][q-1]
    print(ans)
'''
### BUGGY CODE ###

from collections import Counter
import math

def nCr(n, r):
    if n < r:
        return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


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

counter = Counter(A)

for i in range(n):
    ans = 0
    for k, v in counter.items():
        if k == A[i]:
            v -= 1
        ans += nCr(v, 2)
    print(ans)

### FIXED CODE ###

from collections import Counter

mod = (10 ** 9 + 7) ** 5
MAX = 2 * 10 ** 5 + 1 # これは変動するので注意

def com_init(MAX, mod):
    fac = [0] * MAX
    finv = [0] * MAX
    inv = [0] * MAX
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2, MAX):
        fac[i] = fac[i - 1] * i % mod
        inv[i] = mod - inv[mod % i] * (mod // i) % mod
        finv[i] = finv[i - 1] * inv[i] % mod
    return fac, finv

fac, finv = com_init(MAX, mod)

def nCr(n, r):
    if n < r:
        return 0
    elif n < 0 or r < 0:
        return 0
    return fac[n] * (finv[r] * finv[n - r] % mod) % mod

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

counter = Counter(A)

mapping = {}
for k, v in counter.items():
    mapping[k] = nCr(v, 2)

all_sum = 0
for v in mapping.values():
    all_sum += v

memo = {}
for i in range(n):
    num = A[i]
    if num in memo:
        print(memo[num])
    else:
        t = counter[num]
        ans = all_sum - nCr(t, 2) + nCr(t - 1, 2)
        print(ans)
        memo[num] = ans
### BUGGY CODE ###

moji=input()
cycle=int(input())
for i in range(cycle):
  line=input()
  if line[0]=="1":
    moji="".join(list(reversed(moji)))
  elif line[0]=="2":
    fi,ci=line[2],line[4]
    if fi=="1":
      moji=ci+moji
    elif fi=="2":
      moji+=ci
print(moji)

### FIXED CODE ###

def main():
    moji=input()
    cycle=int(input())
    flont_or_back=0
    flont=""
    back=""
    for i in range(cycle):
        line=input()
        if line[0]=="1":
            flont_or_back+=1
        else:
            fi=line[2]
            ci=line[4]
            if flont_or_back%2==0:
                if fi=="1":
                    flont=ci+flont
                else:
                    back+=ci
            else:
                if fi=="1":
                    back+=ci
                else:
                    flont=ci+flont
    moji=flont+moji+back
    if flont_or_back%2==0:
        print(moji)
    else:
        print(moji[::-1])
    

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

import math
ans = 0
k = int(input())
for i in range(1,k+1):
    for j in range(1,k+1):
        for k in range(1,k+1):
            ans += math.gcd(i,math.gcd(j,k))
print(ans)

### FIXED CODE ###

import math
ans = 0
k = int(input())
for i in range(1,k+1):
    for j in range(1,k+1):
        for k in range(1,k+1):
            ans += math.gcd(i,math.gcd(j,k))
print(ans)
### BUGGY CODE ###

S = list(map(int, list(input())))
N = len(S)
CNT = [0]*2019
CNT[0] = 1
base = pow(10, N)
num = 0
for i in range(N):
    base //= 10
    num = num * 10 + S[i]
    CNT[(num*base)%2019] += 1
ans = 0 
for cnt in CNT:
    if cnt==0: continue
    ans += (cnt*(cnt - 1)) // 2
print(ans)

### FIXED CODE ###

S = list(map(int, list(input())))[::-1]
N = len(S)
CNT = [0]*2019
CNT[0] = 1
num = 0
d = 0
for i in range(N):
    num += S[i]*pow(10, d, 2019)
    num %= 2019
    CNT[num] += 1
    d += 1
ans = 0 
for cnt in CNT:
    ans += (cnt*(cnt - 1)) // 2
print(ans)
### BUGGY CODE ###

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

if any(i % 2 == 0 for i in [A, B, C]):
    print(0)
else:
    AB = A * B
    lis = [AB for i in range(C)]
    mid = len(lis) // 2
    print(sum(lis[mid:]) - sum(lis[0:mid]))


### FIXED CODE ###

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

if any(i % 2 == 0 for i in [A, B, C]):
    print(0)
else:
    print(min(A*B, B*C, C*A))
### BUGGY CODE ###

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

from collections import defaultdict
from queue import deque

def main():
  n = int(input())
  graph = defaultdict(list)
  
  def is_bt():
    colors = [-1] * len(graph)
    visited = [False] * len(graph)
    def dfs(inode, color):
      visited[inode] = True
      colors[inode] = color
      for ichild in graph[inode]:
        if not visited[ichild]:
          if not dfs(ichild, abs(color - 1)):
            return False
        else:
          if colors[ichild] == color:
            return False
      return True
    return dfs(0, 0)
        
  def wf(edges):
    dp = edges
    for k in range(len(graph)):
      for i in range(len(graph)):
        for j in range(len(graph)):
          dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])
    return dp
  
  edges = [[n+1] * n for _ in range(n)]  
  for i in range(n):
    for j, c in enumerate(input().strip()):
      if c == '1':
        graph[i].append(j)
        edges[i][j] = 1
    edges[i][i] = 0
    
  if not is_bt():
    print(-1)
    return
  print(max([max(x) for x in wf(edges)]) + 1)
  
if __name__=='__main__':
  main()



### FIXED CODE ###

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

from collections import defaultdict
from queue import deque

def main():
  n = int(input())
  graph = defaultdict(list)
  
  def is_bt():
    def bfs():
      colors = [-1] * len(graph)
      dq = deque()
      dq.append(0)
      colors[0] = 0
      while dq:
        inode = dq.popleft()
        for ichild in graph[inode]:
          if colors[ichild] == -1:
            colors[ichild] = abs(colors[inode]-1)
            dq.append(ichild)
          else:
            if colors[ichild] == colors[inode]:
              return False
      return True
    return bfs()
  
  def wf(edges):
    dp = edges
    for k in range(len(graph)):
      for i in range(len(graph)):
        for j in range(len(graph)):
          dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])
    return dp
  
  edges = [[n+1] * n for _ in range(n)]  
  for i in range(n):
    for j, c in enumerate(input().strip()):
      if c == '1':
        graph[i].append(j)
        edges[i][j] = 1
    edges[i][i] = 0
  graph = dict(graph)
    
  if not is_bt():
    print(-1)
    return
  print(max([max(x) for x in wf(edges)]) + 1)
  
if __name__=='__main__':
  main()
### BUGGY CODE ###

from bisect import bisect_left,bisect
n = int(input())
s = list(input())
q = int(input())
al=[[] for i in range(26)]
for i in range(n):
    al[ord(s[i])-97].append(i)

for i in range(q):
    a , b , x = input().split()
    if a == "1":
        al[ord(s[int(b)-1])-97].pop(bisect_left(al[ord(s[int(b)-1])-97],int(b)-1))
        al[ord(x)-97].insert(bisect_left(al[ord(x)-97],int(b)-1),int(b)-1)
        s[int(b)-1] = x
    elif a == "2":
        b = int(b)-1
        x = int(x)-1
        cou = 0
        for j in range(26):
            l = bisect_left(al[j],b)
            r = bisect(al[j],x)
            if l != r:
                cou += 1
        print(cou)

### FIXED CODE ###

def main():
    from bisect import bisect_left,bisect
    n = int(input())
    s = list(input())
    q = int(input())
    al=[[] for i in range(26)]
    for i in range(n):
        al[ord(s[i])-97].append(i)
    ans = []
    for i in range(q):
        a , b , x = input().split()
        if a == "1":
            al[ord(s[int(b)-1])-97].pop(bisect_left(al[ord(s[int(b)-1])-97],int(b)-1))
            al[ord(x)-97].insert(bisect_left(al[ord(x)-97],int(b)-1),int(b)-1)
            s[int(b)-1] = x
        elif a == "2":
            b = int(b)-1
            x = int(x)-1
            cou = 0
            for j in range(26):
                l = bisect_left(al[j],b)
                r = bisect(al[j],x)
                if l != r:
                    cou += 1
            ans.append(cou)
    for i in ans:
        print(i)

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

n, k = list(map(int,input().split(' ')))
path = []
for i in range(n+1):
    path.append([])
for i in range(n-1):
    a, b = list(map(int,input().split(' ')))
    path[a].append(b)
    path[b].append(a)
val = [0] * (n+1)
for i in range(k):
    v, pt = list(map(int,input().split(' ')))
    val[v] += pt

used = {}
q = [1]
used[1] = True
while q:
    v = q.pop(0)
    for next_v in path[v]:
        if next_v not in used:
            used[next_v] = True
            val[next_v] += val[v]
            q.append(next_v)

print(' '.join([str(pt) for pt in val[1:]]))


### FIXED CODE ###

from collections import deque

n, k = list(map(int,input().split(' ')))
path = []
for i in range(n+1):
    path.append([])
for i in range(n-1):
    a, b = list(map(int,input().split(' ')))
    path[a].append(b)
    path[b].append(a)
val = [0] * (n+1)
for i in range(k):
    v, pt = list(map(int,input().split(' ')))
    val[v] += pt

used = {}
q = deque([1])
used[1] = True
while q:
    v = q.pop()
    for next_v in path[v]:
        if next_v not in used:
            used[next_v] = True
            val[next_v] += val[v]
            q.append(next_v)

print(' '.join([str(pt) for pt in val[1:]]))
### BUGGY CODE ###

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

ans=1

for i in a:
    ans=ans*i

if ans>1000000000000000000:
    print("-1")
else:
    print(ans)

### FIXED CODE ###

import sys

def main():
    n = int(input())
    a=sys.stdin.readline().rstrip().split()
    if '0' in a:
        print(0)
        return
    ans=1
 
    for i in a:
        ans=ans*int(i)
        if ans>1000000000000000000:
            print("-1")
            return
    else:
        print(ans)
main()
### BUGGY CODE ###

from collections import defaultdict

N, Q = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(N-1)]
px = [list(map(int, input().split())) for _ in range(Q)]

counter = defaultdict(lambda: 0)
parent_dict = defaultdict(lambda: 0)  # 親ノード
rank_dict = defaultdict(lambda: 0)  # 根からの距離

for p, x in px:
    counter[p] += x

# 根からの距離(after test用)
ab = sorted(ab)
for a, b in ab:
    if a == 1:
        rank_dict[b] = 1
        parent_dict[b] = 1
    else:
        if rank_dict[a] != 0 and rank_dict[b] == 0:
            rank_dict[b] = rank_dict[a] + 1
            parent_dict[b] = a
        elif rank_dict[a] == 0 and rank_dict[b] != 0:
            rank_dict[a] = rank_dict[b] + 1
            parent_dict[a] = b

rank_sorted = sorted(rank_dict.items(), key=lambda x: x[1])
for k, v in rank_sorted:
    counter[k] += counter[parent_dict[k]]

ans = []
for i in range(1, N+1):
    ans.append(counter[i])
print(" ".join(map(str, ans)))

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)


def dfs(cur, par):
    for child in edge[cur]:
        if child == par:
            continue
        counter[child] += counter[cur]
        dfs(child, cur)


N, Q = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(N-1)]
px = [list(map(int, input().split())) for _ in range(Q)]
counter = [0] * N

edge = [[] for _ in range(N)]
for i in range(N-1):
    a = ab[i][0] - 1
    b = ab[i][1] - 1
    edge[a].append(b)
    edge[b].append(a)

for i in range(Q):
    p = px[i][0] - 1
    x = px[i][1]
    counter[p] += x


dfs(0, -1)
print(*counter)
### BUGGY CODE ###

n = int(input())
ret = 1
a = list(map(int, input().split()))
for ai in a:
    ret *= ai
if ret > 1000000000000000000:
    print(-1)
else:
    print(ret)


### FIXED CODE ###

n = int(input())
ret = 1
a = sorted(list(map(int, input().split())))
for ai in a:
    ret *= ai
    if ret > 1000000000000000000:
        print(-1)
        exit(0)
print(ret)
### BUGGY CODE ###

import functools
import operator

n = input()
li = list(map(int, input().split()))
result = functools.reduce(operator.mul, li)

if result >= 1000000000000000001:
    print(-1)
else:
    print(result)

### FIXED CODE ###

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

if 0 in li:
    print(0)
    exit(0)

ans = 1
for i in li:
    ans *= i
    if ans > 10 ** 18:
        print(-1)
        exit(0)

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

def prime_pair(n):
    pairs = {}
    tmp = n
    for i in range(2, n):
        if tmp % i != 0:
            continue
        ex = 0
        while tmp % i == 0:
            ex += 1
            tmp /= i
        pairs[i] = ex
    return pairs

def gcd(a,b):
    if b % a == 0:
        return a
    return gcd(b % a, a)


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

ppa = prime_pair(A)
ppb = prime_pair(B)

g = gcd(A,B)
ppg = prime_pair(g)

print(len(ppg.keys())+1)

### FIXED CODE ###

def factorization(n):
    arr = [[1,1]]
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr
A,B =list(map(int, input().split(" ")))

val = min(A,B)
lim = int(val ** 0.5)


ms = factorization(min(A,B)) 
res = []
maxi = max(A,B)

for v, _ in ms:
    if maxi % v == 0:
        res.append(v)
print(len(res))
### BUGGY CODE ###

import heapq

change = []
n, m = map(int, input().split())
a = [int(i) for i in input().split()]
for i in range(m):
    b, c = map(int, input().split())
    change.append([c, b])

heapq.heapify(change)
heapq.heapify(a)

while change:
    b, c = heapq.heappop(change)
    while a[0] < b and c > 0:
        tmp = heapq.heappop(a)
        heapq.heappush(a, b)
        c -= 1
        
print(sum(a))


### FIXED CODE ###

import heapq


change = []
n, m = map(int, input().split())
a = [-1 * int(i) for i in input().split()]
for i in range(m):
    b, c = map(int, input().split())
    change.append([-c, b])

l = []
heapq.heapify(change)
heapq.heapify(a)
flg = False
cnt = 0
while cnt < n:
    if change:
        atmp = -1 * a[0]
        btmp = -1 * change[0][0]
        if atmp <= btmp:
            b, c = heapq.heappop(change)
            while c > 0 and cnt < n:
                l.append(b)
                c -= 1
                cnt += 1
        else:
            aa = heapq.heappop(a)
            l.append(aa)
            cnt += 1
    else:
        aa = heapq.heappop(a)
        l.append(aa)
        cnt += 1
        
print(-1 * sum(l))
### BUGGY CODE ###

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

l,r = map(int,input().split())
temp1 = set(range(l,r+1))
for i in range(m-1):
  l,r = map(int,input().split())
  temp2 = set(range(l,r+1))
  temp1 = temp1 & temp2
  
print(len(temp1))


### FIXED CODE ###

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

s,e = map(int,input().split())
for i in range(m-1):
  l,r = map(int,input().split())
  s = max(s,l)
  e = min(e,r)

print(len(range(s,e+1)))
### BUGGY CODE ###

import math
n, k=map(int, input().split() )
a=list(map(int, input().split() ) )
b=[0]*n
for i in range(1, n):
    m=float("inf")
    for j in range(min(i,k),0,-1):
        m=min(m, b[i-j]+int(math.fabs(a[i]-a[i-j])))
    b[i] = m
print(b[-1])

### FIXED CODE ###

n, k=list(map(int, input().split()))
 
a=list(map(int, input().split()))
 
if n<3:
    print(abs(a[0]-a[-1]))
    exit()
 
c=[0]*n
c[-1]=0
mini=1000000
 
for i in reversed(range(n-k, n-1)):
    # print(i)
    c[i]=abs(a[i]-a[n-1])
    mini=min(mini, c[i])
 
 
for i in reversed(range(n-k)):
    c[i]=min([c[t]+abs(a[i]-a[t]) for t in range(i+1, i+k+1)])
 
# print("?", c)
 
print(c[0])
### BUGGY CODE ###

import sys

rr = lambda: sys.stdin.readline().rstrip()
rs = lambda: sys.stdin.readline().split()
ri = lambda: int(sys.stdin.readline())

flag = False
s = rr()
q = ri()
for _ in range(q):
    query = list(rs())
    if query[0] == '1':
        flag = not flag
        continue
    else:
        f = int(query[1])
        c = query[-1]
        if flag == True:
            if f == 1:
                s += c
            else:
                s = c+s
        else:
            if f == 1:
                s = c+s
            else:
                s += c
if flag:
    print(s[::-1])
else:
    print(s)            

### FIXED CODE ###

import sys

rr = lambda: sys.stdin.readline().rstrip()
rs = lambda: sys.stdin.readline().split()
ri = lambda: int(sys.stdin.readline())

flag = False
s = rr()
q = ri()
front = ''
end = ''
for _ in range(q):
    query = list(rs())
    if query[0] == '1':
        flag = not flag
        continue
    else:
        f = int(query[1])
        c = query[-1]
        if flag == True:
            if f == 1:
                end += c
            else:
                front = c+front
        else:
            if f == 1:
                front = c+front
            else:
                end += c
if flag:
    print((front+s+end)[::-1])
else:
    print(front+s+end)
### BUGGY CODE ###

N, K = map(int, input().split())
Ps = list(map(int, input().split()))
Cs = list(map(int, input().split()))


def calcScore(C_list, P_list, idx, num_operation):
    score = 0
    scores = []
    for i in range(num_operation):
        idx = P_list[idx] - 1
        score += C_list[idx]
        scores.append(score)
    return max(scores)


max_scores = [calcScore(Cs, Ps, i, K) for i in range(N)]

print(max(max_scores))

### FIXED CODE ###

N, K = map(int, input().split())
Ps = list(map(int, input().split()))
Ps = [i - 1 for i in Ps]
Cs = list(map(int, input().split()))
max_score = -float("inf")


for i in range(N):
    scores = []
    idx = i  # starting index
    while True:
        idx = Ps[idx]  # point to the next index
        scores.append(Cs[idx])  # fetch a score to add
        if idx == i:  # when the cycle is closed
            break

    len_cycle = len(scores)
    sum_cycle = sum(scores)

    if sum_cycle <= 0:  # when each cycle reduces the total score
        score = 0
        for j in range(min(K, len_cycle)):
            score += scores[j]
            max_score = max(max_score, score)
    else:
        if K // len_cycle > 0:
            num_multiply = K // len_cycle - 1
            score = sum_cycle * num_multiply
            scores = scores * 2
            for j in range(K % len_cycle + len_cycle):
                score += scores[j]
                max_score = max(max_score, score)
        else:
            num_multiply = 0  # len_cycle > K
            score = sum_cycle * num_multiply
            for j in range(K):
                score += scores[j]
                max_score = max(max_score, score)

print(max_score)
### BUGGY CODE ###

def main():
    from collections import Counter
    N, P = (int(i) for i in input().split())
    S = input()

    ans = 0
    if P == 5 or P == 2:
        for j in range(1, N+1):
            # j文字取る
            num = int(S[:j])
            if num % P == 0:
                ans += j
    else:
        acc = [0]*(N+1)
        d = 1
        for i, s in enumerate(S[::-1], start=1):
            # print(i, s)
            acc[i] = (int(s) * d + acc[i-1]) % P
            d *= 10
            d %= P
        c = Counter(acc)
        # print(acc, c)
        ans = sum(v*(v-1)//2 for v in c.values())
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    from collections import Counter
    N, P = (int(i) for i in input().split())
    S = [int(s) for s in input()]

    ans = 0
    if P == 5 or P == 2:
        for i, s in enumerate(S, start=1):
            # j文字取る
            if s % P == 0:
                ans += i
    else:
        acc = [0]*(N+1)
        d = 1
        for i, s in enumerate(S[::-1], start=1):
            # print(i, s)
            acc[i] = (s * d + acc[i-1]) % P
            d *= 10
            d %= P
        c = Counter(acc)
        # print(acc, c)
        ans = sum(v*(v-1)//2 for v in c.values())
    print(ans)


if __name__ == '__main__':
    main()