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

import numpy as np

N = int(input())
A = []
B = []
for _ in range(N):
    s = input().split()
    A.append(int(s[0]))
    B.append(int(s[1]))

def set_list(es):
    es = es.tolist()
    return len(list(set(es))) == 1

ind = 0

A = np.array(A)
B = np.array(B)

a_happy = 0
b_happy = 0

for i in range(N):
    if i%2 == 0:
        if set_list(A):
            ind = np.argmax(B)
        else:
            ind = np.argmax(A)
        a_happy += A[ind]
        A = np.delete(A, ind)
        B = np.delete(B, ind)
    if i%2 == 1:
        if set_list(B):
            ind = np.argmax(A)
        else:
            ind = np.argmax(B)
        b_happy += B[ind]
        A = np.delete(A, ind)
        B = np.delete(B, ind)

print(a_happy - b_happy)


### FIXED CODE ###

import numpy as np

N = int(input())
C = []
for _ in range(N):
    a, b = map(int, input().split())
    C.append([a+b, a, b])

D = sorted(C, reverse=True)

ans = 0

for i in range(N):
    if i % 2 == 0:
        ans += D[i][1]
    elif i % 2 == 1:
        ans -= D[i][2]

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

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

aa = sorted([a[i]-i-1 for i in range(n)])
aa = [_-min(aa) for _ in aa]

if n % 2 == 1:
    idx = n // 2
    res = 0
    for ai in aa[:idx]:
        res += aa[idx] - ai
    for ai in aa[idx:]:
        res += ai - aa[idx]

else:
    idx_1 = n // 2 -1
    idx_2 = n // 2
    res_1 = 0
    for ai in aa[:idx_1]:
        res_1 += aa[idx_1] - ai
    for ai in aa[idx_1:]:
        res_1 += ai - aa[idx_1]
    res_2 = 0
    for ai in aa[:idx_2]:
        res_2 += aa[idx_2] - ai
    for ai in aa[idx_2:]:
        res_2 += ai - aa[idx_2]
    res = min(res_1, res_2)

print(res)

### FIXED CODE ###

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

aa = sorted([a[i]-i-1 for i in range(n)])

if n % 2 == 1:
    idx = n // 2
    res = 0
    for ai in aa[:idx]:
        res += aa[idx] - ai
    for ai in aa[idx:]:
        res += ai - aa[idx]

else:
    idx_1 = n // 2 -1
    idx_2 = n // 2
    res_1 = 0
    for ai in aa[:idx_1]:
        res_1 += aa[idx_1] - ai
    for ai in aa[idx_1:]:
        res_1 += ai - aa[idx_1]
    res_2 = 0
    for ai in aa[:idx_2]:
        res_2 += aa[idx_2] - ai
    for ai in aa[idx_2:]:
        res_2 += ai - aa[idx_2]
    res = min(res_1, res_2)

print(res)
### BUGGY CODE ###

import sys
import numpy as np
input = sys.stdin.readline
 
MOD = 10**9 + 7
U = 2 ** 20
 
N = int(input())
A = [int(x) for x in input().split()]
C = np.zeros(N,dtype = np.int64) # cumsum
 
cum = 0
for i,a in enumerate(A):
  cum ^= a
  C[i] = cum
 
arr = np.zeros((U,2),dtype=np.int64)
arr[:,0] = 1
 
zero_update = np.zeros(U,dtype=np.int64) #0が出てきて更新した回数
zero_cnt = 0
 
for i in range(N):
  c = C[i]
  if c == 0:
    zero_cnt += 1
    continue
  n = zero_cnt - zero_update[c]
  zero_update[c] = zero_cnt
  a = arr[c,0]
  b = arr[c,1]
  a,b = a+n*b,b
  a,b = a,a+b
  a %= MOD
  b %= MOD
  arr[c,0] = a
  arr[c,1] = b
 
answer = 0
final = C[-1]
if final != 0:
  answer = arr[final,0]
else:
  answer = arr[1:,1].sum()
  answer += pow(2,zero_cnt-1,MOD)
  answer %= MOD
print(answer)

### FIXED CODE ###

import sys
input = sys.stdin.readline
 
MOD = 10**9 + 7
U = 2 ** 20
 
N = int(input())
A = [int(x) for x in input().split()]
 
arr_0 = [1] * U
arr_1 = [0] * U
 
zero_update = [0] * U #0が出てきて更新した回数
zero_cnt = 0
 
c = 0
for a in A:
  c ^= a
  if c == 0:
    zero_cnt += 1
    continue
  n = zero_cnt - zero_update[c]
  zero_update[c] = zero_cnt
  a = arr_0[c]
  b = arr_1[c]
  a,b = a+n*b,b
  a,b = a,a+b
  a %= MOD
  b %= MOD
  arr_0[c] = a
  arr_1[c] = b
 
answer = 0
if c != 0:
  answer = arr_0[c]
else:
  answer = sum(arr_1[1:])
  answer += pow(2,zero_cnt-1,MOD)
  answer %= MOD
print(answer)
### BUGGY CODE ###

N, M = map(int, input().split())
L = [None] * M
R = [None] * M

ans = [0] * (N + 1)

for i in range(M):
  L[i], R[i] = map(int, input().split())

for i in range(M):
  for j in range(L[i], R[i] + 1):
    ans[j] += 1


print(ans.count(M))


### FIXED CODE ###

N, M = map(int, input().split())
L = [None] * M
R = [None] * M

for i in range(M):
  L[i], R[i] = map(int, input().split())

ans = list(range(max(L), min(R) + 1))


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

import networkx as nx
n, m, *AB = map(int, open(0).read().split())
G = nx.Graph()
G.add_nodes_from(range(1, n+1))
for a, b in zip(AB[::2], AB[1::2]):
    G.add_edge(a, b)
print('Yes')
for i in range(2, n+1):
    print(nx.shortest_path(G, 1, i)[-2])

### FIXED CODE ###

from collections import deque
n, m, *AB = map(int, open(0).read().split())
graph = [[] for _ in range(n)]
for a, b in zip(AB[::2], AB[1::2]):
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)

d = [0] * n
queue = deque([0])
while queue:
    current_node = queue.popleft()
    for next_node in graph[current_node]:
        if d[next_node] == 0:
            d[next_node] = current_node+1
            queue.append(next_node)
print('Yes')
print(*d[1:], sep='\n')
### BUGGY CODE ###

#ABC116D-VariousSushi.py

import numpy as np

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

N, K = INPUT1[0], INPUT1[1]
Parameters = [[None for col in range(2)] for row in range(N)]
Score= 0
kind = []
kindnumber = 0

for i in range(N):
    INPUT2 = [int(m) for m in input().split()]
    Parameters[i] = [INPUT2[0], INPUT2[1]]

Parameters = sorted(Parameters, key=lambda x: x[1], reverse=True)

def SearchNew(List, kind, I):
    newkind = -1
    kindset = kind[:]
    oldkindnumber = len(set(kindset))
    newkindnumber = 0
    for i in range(len(List)-I):
        kindset.append(List[I+i][0])
        newkindnumber = len(set(kindset))
        if oldkindnumber != newkindnumber:
            newkind = I+i
            break
    return newkind

def SearchDouble(List, kind, J):
    result = -1
    testkind = kind[:]
    oldkindnumber = len(set(testkind))
    testkindPop = testkind.pop
    for i in range(J):
        testkindPop(J-1-i)
        newkindnumber = len(set(testkind))
        if oldkindnumber == newkindnumber:
            result = J-1-i
            break
        oldkindnumber = newkindnumber
    return result

kindAppend = kind.append

for i in range(K):
    kindAppend(Parameters[i][0])
kindnumber = len(set(kind))
Score = np.sum(Parameters[:K], axis=0)[1] + kindnumber**2

Test1, Test2 = 0, Score

I, J = K, K

for t in Parameters:
    kindnumber = len(set(kind))
    i = SearchNew(Parameters, kind, I)
    j = SearchDouble(Parameters, kind, J)
    if i != -1 and j != -1:
        kindnumber += 1
        I, J = i, j
        kind[j] = Parameters[i][0]
        Parameters[i], Parameters[j] = Parameters[j], Parameters[i]
    else:
        break
    Test1 = Test2 - Parameters[i][1] + Parameters[j][1] + kindnumber * 2 - 1
    Test2 = Test1
    if Score <= Test2:
        Score = Test2

print(Score)


### FIXED CODE ###

#ABC116D-VariousSushi.py

from sys import stdin
#from numpy import sum

input = stdin.readline

N, K = list(map(int, input().split()))
List1= []
kind = set()
point1, point2 = 0, 0

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

INPUT.sort(key = lambda x: -x[1])

for ti, di in INPUT[:K]:
    point1 += di
    if ti in kind:
        List1.append(di)
    kind.add(ti)

point2 = len(kind)

Score = point1 + point2**2
Test = Score

List1POP = List1.pop

for ti, di in INPUT[K:]:
    if 0 >= len(List1):
        break
    if ti in kind:
        continue
    Test = Test - List1POP() + di + 2 * point2 + 1
    point2 += 1
    kind.add(ti)
    Score = max(Score, Test)

print(Score)
### BUGGY CODE ###

x,y,z,K=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
c=list(map(int,input().split()))
a.sort(reverse=1)
b.sort(reverse=1)
c.sort(reverse=1)
m=[]
for i in range(x):
  for j in range(y):
    for k in range(z):
      if (i+1)*(j+1)*(k+1)<=K:
        m.append(a[i]+b[j]+c[k])
m.sort(reverse=1)
for i in m[:K]:
  print(i)

### FIXED CODE ###

x,y,z,K=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
c=list(map(int,input().split()))
a.sort(reverse=1)
b.sort(reverse=1)
c.sort(reverse=1)
m=[]
for i in range(x):
  for j in range(y):
    for k in range(z):
      if (i+1)*(j+1)*(k+1)>K:
        break
      m.append(a[i]+b[j]+c[k])
m.sort(reverse=1)
for i in m[:K]:
  print(i)
### BUGGY CODE ###

import sys
import bisect
input = sys.stdin.readline
 
def main():
    n,m = map(int,input().split())
    a = list(map(int,input().split()))	
    for i in range(m):
        a.sort()
        a[n-1]=a[n-1]//2
    print(sum(a))


main()

### FIXED CODE ###

import sys
import bisect
input = sys.stdin.readline
 
def main():
    n,m = map(int,input().split())
    a = list(map(int,input().split()))
    cnt=0
    while(cnt<m):
        a.sort()
        a[n-1]=a[n-1]//2
        cnt+=1
        if(cnt==m):
            break
        for i in range(n-1):
            if(a[n-1]<=a[n-i-2]):
                a[n-i-2]=a[n-i-2]//2
                cnt+=1
                if(cnt==m):
                    break
    print(sum(a))


main()
### BUGGY CODE ###

def z_algorithm(s: str) -> list:
	n = len(s)
	Z = [0] * n
	Z[0] = n
	i, j = 1, 0
	while i < n:
		while i + j < n and s[j] == s[i + j]:
			j += 1
		Z[i] = j
		if j == 0:
			i += 1
			continue
		k = 1
		while i + k < n and k + Z[k] < j:
			Z[i + k] = Z[k]
			k += 1
		i += k
		j -= k
	return Z


n = int(input())
s = input()
ans = 0
for i in range(n):
	z = z_algorithm(s[i:])
	t = max(min(j, z[j]) for j in range(n - i))
	ans = max(ans, t)
print(ans)


### FIXED CODE ###

n=int(input())
s=input()
a=0
i=0
j=1
while j<n:
	if s[i:j] in s[j:]:
		a=max(a,len(s[i:j]))
		j+=1
	else:
		i+=1
	if i==j:
		i+=1
		j+=2
print(a)
### BUGGY CODE ###

s = input()
K=int(input())

subs = set()
L = len(s)
for l in range(1,L+1):
    for i in range(L-l+1):
        subs.add(s[i:i+l])
print(sorted(list(subs))[K-1])

### FIXED CODE ###

s = input()
K=int(input())

subs = set()
L = len(s)
for l in range(1,min(L,5)+1):
    for i in range(L-l+1):
        subs.add(s[i:i+l])
print(sorted(list(subs))[K-1])
### BUGGY CODE ###

import re
N,Q = map(int,input().split())
S = input()
qa = []
for i in range(Q):
    lr = [int(i) for i in input().split()]
    qa.append(lr)

for j in range(Q):
    count = 0
    start = qa[j][0]-1
    end = qa[j][1]
    string = S[start:end]
    Re = re.findall("AC", string)
    count += len(Re)
    print(count)

### FIXED CODE ###

import time
N,Q = map(int, input().split())
S = input()
AC = [0]*(N+1)

for i in range(N):
    if S[i:i+2] == "AC":
        AC[i+1] = AC[i] + 1
    else:
        AC[i+1] = AC[i]

for i in range(Q):
    l, r = map(int, input().split())
    print(AC[r-1] - AC[l-1])
### BUGGY CODE ###

def main():
    N = int(input())
    S = list(str(input()))
    print()
    sum = 0
    for i in range(0, N-2):
        si = S[i]
        for j in range(i, N-1):
            sj = S[j]
            for k in range(j, N):
                sk = S[k]
                #if S[i] != S[j] and S[i] != S[k] and S[j] != S[k]:
                #if j - i != k -j:
                if j - i != k -j and si != sj and si != sk and sj != sk:
                    #if si != sj and si != sk and sj != sk:
                    #if j - i != k -j:
                    sum += 1
    print(sum)



main()

### FIXED CODE ###

def main():
    N = int(input())
    S = list(str(input()))
    sum = S.count("R") * S.count("G") * S.count("B")
    for i in range(0, N-2):
        si = S[i]
        for j in range(i+1, N-1):
            sj = S[j]
            k = 2*j -i  # Nを超える
            if k < N:
                sk = S[k]
                #if j - i != k -j and si != sj and si != sk and sj != sk:
                if si != sj and si != sk and sj != sk:
                    sum -= 1
    print(sum)

    # 提出 #11871188


main()
### BUGGY CODE ###

import sys
import math  # noqa
import bisect  # noqa
import queue  # noqa


def input():
    return sys.stdin.readline().rstrip()


if __name__ == '__main__':
    S = input()

    que = queue.Queue()
    que.put("")
    ans = False
    while not que.empty():
        t = que.get()
        if len(S) == len(t):
            if S == t:
                ans = True
                break
        elif len(S) > len(t):
            if S[:len(t) + 7] == t + "dreamer":
                que.put(t + "dreamer")
            if S[:len(t) + 5] == t + "dream":
                que.put(t + "dream")
            if S[:len(t) + 5] == t + "erase":
                que.put(t + "erase")
            if S[:len(t) + 6] == t + "eraser":
                que.put(t + "eraser")

    if ans:
        print("YES")
    else:
        print("NO")


### FIXED CODE ###

import sys
import math  # noqa
import bisect  # noqa
import queue  # noqa


def input():
    return sys.stdin.readline().rstrip()


if __name__ == '__main__':
    S = input()

    i = 0
    ans = False
    while True:
        res = S[i:i + 5]
        if res == "dream":
            i = i + 5
            if S[i:i + 5] == "dream":
                continue
            elif S[i:i + 7] == "erdream":
                i = i + 2
                continue
            elif S[i:i + 5] == "erase":
                continue
            elif S[i:i + 7] == "ererase":
                i = i + 2
                continue
            elif i == len(S):
                ans = True
                break
            elif i == len(S) - 2:
                if S[i:] == "er":
                    ans = True
                    break
                else:
                    ans = False
                    break
            else:
                ans = False
                break
        elif res == "erase":
            i = i + 5
            if S[i:i + 5] == "dream":
                continue
            elif S[i:i + 6] == "rdream":
                i = i + 1
                continue
            elif S[i:i + 5] == "erase":
                continue
            elif S[i:i + 6] == "rerase":
                i = i + 1
                continue
            elif i == len(S):
                ans = True
                break
            elif i == len(S) - 1:
                if S[i:] == "r":
                    ans = True
                    break
                else:
                    ans = False
                    break
            else:
                ans = False
                break

    if ans:
        print("YES")
    else:
        print("NO")
### BUGGY CODE ###

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

def S(i):
    A = []
    for j in range(i):
        A.append((P[j]+1)/2)
    return sum(A)

B =[]
for j in range(N-K+1):
    B.append(S(j+K)-S(j))
ans = max(B)
print(ans)
    



### FIXED CODE ###

from itertools import accumulate
N, K = map(int, input().split())
P = list(map(int, input().split()))
P = [0]+[(p+1)/2 for p in P]
S = list(accumulate(P))
B = []
for j in range(N-K+1):
    B.append(S[j+K]-S[j])
ans = max(B)
print(ans)
### BUGGY CODE ###

import math
n = int(input())
ans = 0

for c in range(1,n):
    ab = n - c
    for i in range(1, int(math.sqrt(ab)) + 1):
        if ab % i == 0:
            ans += 1
            if ab != i**2:
                ans += 1

print(ans)


### FIXED CODE ###

import math
n = int(input())
ans = 0

for a in range(1, n):
    ans += math.floor((n-1)/a)
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n, m = map(int, input().split())
C = [list(map(int,input().split())) for i in range(n-1+m)]

r = -1
R = [1] * (n+1)
for i in range(len(C)):
    R[C[i][1]] = 0
for i in range(1, n+1):
    if R[i] == 1:
        r = i

# print(r)

# V = [0] * (n+1)
P = [0] * (n+1)

M = [[] for i in range(n+1)]
for i in range(n-1+m):
    M[C[i][0]].append(C[i][1])

# 1始まりの場合
Q = [r]
s = 0
# V[r] = 1
while s < len(Q):
    i = Q[s]
    for x in M[i]:
        if x != P[i]:
            # V[x] = 1
            P[x] = i
            Q.append(x)
    s += 1
# print(P)

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

### FIXED CODE ###

import sys
input = sys.stdin.readline
n, m = map(int, input().split())
C = [list(map(int,input().split())) for i in range(n-1+m)]

r = -1
R = [1] * (n+1)
for i in range(len(C)):
    R[C[i][1]] = 0
for i in range(1, n+1):
    if R[i] == 1:
        r = i

# print(r)

F = [0] * (n+1)
P = [0] * (n+1)

M = [[] for i in range(n+1)]
for i in range(n-1+m):
    M[C[i][0]].append(C[i][1])
    F[C[i][1]] += 1

# 1始まりの場合
Q = [r]
s = 0
# V[r] = 1
while s < len(Q):
    i = Q[s]
    for x in M[i]:
        F[x] -= 1
        if F[x] == 0:
            P[x] = i
            Q.append(x)
    s += 1
# print(P)

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

N=int(input())
A=list(map(int, input().split()))
def calc_mod(n):
    return n %(10**9+7)
AA=list(map(calc_mod, A))
X=0
for i in range(N-1):
  X+=AA[i]*sum(AA[i+1:N])
  X=X%(10**9+7)
print(X)

### FIXED CODE ###

N=int(input())
A=list(map(int, input().split()))
def calc_mod(n):
    return n %(10**9+7)
AA=list(map(calc_mod, A))
X=0
XX=0
for i in range(N-1):
  XX+=AA[N-i-1]
  X+=AA[N-i-2]*XX
  X=X%(10**9+7)
print(X)
### BUGGY CODE ###

n = int(input())
lst = [list(map(int, input().split())) for _ in range(n)]
 
current_loop = []
current = []
for i in range(n):
    a = lst[i].pop(0)
    current_loop.append((a, i+1))
    current.append(a)

count = 0
while True:
    index_lst = []
    for pair in current_loop:
        a, b = pair
        if current[a-1] == b:
            index_lst += [a, b]   
    if len(index_lst) == 0:
        if sum(current) == 0:
            print(count)
            break
        else:
            print(-1)
            break
    for i in set(index_lst):
        if len(lst[i-1]) == 0:
            current[i-1] = 0
        else:
            a = lst[i-1].pop(0)
            current[i-1] = a
            current_loop.append((a, i))
    count += 1

### FIXED CODE ###

from collections import deque
 
n = int(input())
lst = [deque(map(int, input().split())) for _ in range(n)]
 
current = []
for i in range(n):
    current.append(lst[i].popleft())

count = 0
players = set(range(1, n+1))
while True:
    index_lst = []
    for i in players:
        candidate = current[i-1]
        if candidate in index_lst:
            continue
        if current[candidate-1] == i:
            index_lst += [i, candidate]   
    if len(index_lst) == 0:
        if sum(current) == 0:
            print(count)
            break
        else:
            print(-1)
            break
    for i in index_lst:
        if len(lst[i-1]) == 0:
            current[i-1] = 0
        else:
            current[i-1] = lst[i-1].popleft()
    players = set(index_lst)
    count += 1
### 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]

    while True:
        if len(ql) != 0:
            cost, xv, yv = ql.popleft()
            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:
                        ql.append([cost + 1, xv, yv])
                        fq[xv, yv]
        else:
            break
    print(cost)


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()
### BUGGY CODE ###

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

for _ in range(M):
    B, C = map(int, input().split())
    A += [C]*B
A.sort(reverse=True)
print(sum(A[:N]))

### FIXED CODE ###

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

l = []
for _ in range(M):
    B, C = map(int, input().split())
    l.append((B, C))
l.sort(key=lambda x:-x[1])

def solve():
    p = 0
    ans = 0
    for i, j in l:
        for _ in range(i):
            ans += max(A[p], j)
            p += 1
            if N==p:
                return ans
    
    for i in range(p, N):
        ans += A[i]
    return ans
    
print(solve())
### BUGGY CODE ###


def getIntList(inp):
	return [int(_) for _ in inp]


from sys import stdin
import sys

def getInputs():
	inputs=[]
	for line in stdin:
		line=line.split()
		inputs.append(line)
	return inputs


def main(inputs):
	n,p=getIntList(inputs[0])
	s=inputs[1][0]
		
	ans=0
	for i0 in range(len(s)):
		num=int(s[i0:i0+1])
		r=num%p
		if r==0: ans+=1
		for i1 in range(i0+1, len(s)):
			num=int(s[i1:i1+1])
			r1=r*10+num
			r=r1%p
			if r==0: ans+=1
	print(ans)
	

if __name__=="__main__":
	inputs=getInputs()
# 	inputs=simInputs()
	main(inputs)
	


### FIXED CODE ###


#####

import numpy as np
from numpy import newaxis, float32, float64, int32, int64, int16, int8, uint8, uint32, complex64, complex128

#####

def getIntList(inp):
	return [int(_) for _ in inp]


from sys import stdin
import sys

def getInputs():
	inputs=[]
	for line in stdin:
		line=line.split()
		inputs.append(line)
	return inputs



def main(inputs):
	n,p=getIntList(inputs[0])
	s=inputs[1][0]
	
	ans=0
	if p%2==0 or p%5==0:
		for i0 in range(len(s)-1,-1,-1):
			sub=int(s[i0:i0+1])
			if sub%p==0:
				ans+=i0+1
	else:
		numP0=np.zeros(p, int32)
		numP0[0]=1
		r=0
		modD=int(1%p)
		for i0 in range(len(s)-1,-1,-1):
			
			sub=s[i0:i0+1]
			sub=int(sub)
			sub=r+sub*modD
			r=sub%p
			ans+=numP0[r]
			numP0[r]+=1
			modD=int((modD*10)%p)
	print(ans)
		
	

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

MOD = 998244353

class BIT:
    def __init__(self, n, init=None):
        self.size = n
        if init is None:
            self.v = [0] * (n + 1) # don't use bit[0]
        else:
            self.v = [0] + init
            for i in range(1, n):
                if i + (i & -i) <= n: self.v[i + (i & -i)] += self.v[i]

    def sum(self, i):
        '''
        Calculate a[1] + ... + a[i]
        '''
        S = 0
        while i > 0:
            S += self.v[i]
            i -= i & -i
        return S

    def add(self, i, x):
        '''
        set a[i] to be a[i] + x
        '''
        assert i > 0
        while i <= self.size:
            self.v[i] += x
            i += i & -i

N, K = map(int, input().split())
segments = [tuple(map(int, input().split())) for _ in range(K)]
bit = BIT(N + 1)
bit.v[1] = 1
for i in range(1, N + 1):
    temp = bit.sum(i)
    for s, t in segments:
        if i + s <= N:
            bit.add(i + s, temp)
            bit.add(min(i + t + 1, N + 1), -temp)
print(bit.sum(N) % MOD)

### FIXED CODE ###

MOD = 998244353

N, K = map(int, input().split())
segments = [tuple(map(int, input().split())) for _ in range(K)]
dp = [0] * (2 * N + 1)
for i in range(N):
    for s, t in segments:
        t += 1
        dp[i + s] += dp[i] if i != 0 else 1
        dp[i + t] -= dp[i] if i != 0 else 1
    dp[i + 1] += dp[i]
    dp[i + 1] %= MOD
print(dp[N - 1])
### BUGGY CODE ###

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


### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
acc = [0] * (N+1)
for i in range(0, N):
    acc[i+1] = acc[i] + (i+1 < N and S[i+1] == "C" and S[i] == "A")
for i in range(Q):
    l, r = map(int, input().split())
    print(acc[r-1] - acc[l-1])