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

import itertools
N, M, Q = map(int, input().split())
P = []
LR = [[0] * (N+1) for _ in range(N+1)] 
for m in range(M):
    l, r = map(int, input().split())
    LR[l][r] += 1

for q in range(Q):
    p = list(map(int, input().split()))
    P.append(p)

csum = []
for L in LR:
    a = list(itertools.accumulate(L))
    csum.append(a)

for p in P:
    ans = 0
    l, r = p
    for c in csum[l:r+1]:
        ans += (c[r] - c[l-1])
    print (ans)


### FIXED CODE ###

import itertools
N, M, Q = map(int, input().split())
P = []
LR = [[0] * (N+1) for _ in range(N+1)] 
for m in range(M):
    l, r = map(int, input().split())
    LR[l][r] += 1

for q in range(Q):
    p = list(map(int, input().split()))
    P.append(p)

csum = []
for L in LR:
    a = list(itertools.accumulate(L))
    csum.append(a)

for p in P:
    ans = 0
    l, r = p
    for c in csum[l:r+1]:
        ans += (c[r] - c[l-1])
    print (ans)
### BUGGY CODE ###

import sys,collections as cl,bisect as bs,copy
sys.setrecursionlimit(100000)
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return k
    else:
        return False

n = onem()

on = []
wh = [[-1 for j in range(n)] for i in range(n)]
de = cl.deque()
for i in range(n):
    k = l()
    for j in range(n-1):
        k[j] -= 1
    k.reverse()
    de.append([k[0],i])
    on.append(cl.deque(k))


co = 1
ddd = cl.deque()
de.append([-1,-1])
cl = [1 for i in range(n)]

while de:

    kkk = de.popleft()
    if kkk[0] == -1 and kkk[1] == -1:
        if sum(cl) == n:
            co = -1
            break
        if len(de) == 0:
            break
        de.append([-1,-1])
        co += 1
        cl = [1 for i in range(n)]

    elif len(on[kkk[0]]) != 0 and on[kkk[0]][0] == kkk[1] and cl[kkk[0]] and cl[kkk[1]]:
        cl[kkk[0]] = 0
        cl[kkk[1]] = 0
        on[kkk[0]].popleft()
        on[kkk[1]].popleft()
        if len(on[kkk[1]]) != 0 and len(on[kkk[0]]) != 0 and on[kkk[1]][0] == kkk[0] and on[kkk[0]][0] == kkk[1]:
            de.append([on[kkk[1]][0],kkk[1]])
        else:
            if len(on[kkk[1]]) != 0:
                de.append([on[kkk[1]][0],kkk[1]])
            if len(on[kkk[0]]) != 0:
                de.append([on[kkk[0]][0],kkk[0]])


print(co)

### FIXED CODE ###

import collections as cl
def l(): #intのlist
    return list(map(int,input().split()))
def onem(): #Nとかの取得
    return int(input())
n = onem()

on = []
de = cl.deque()
ppp = [n-1 for i in range(n)]
for i in range(n):
    k = l()
    for j in range(n-1):
        k[j] -= 1
    k.reverse()
    de.append([k[0],i])
    on.append(cl.deque(k))


co = 1
ddd = cl.deque()
de.append([-1,-1])
ppppp = [1 for i in range(n)]
cl = ppppp[:]
while de:
    kkk = de.popleft()
    if kkk[0] == -1 and kkk[1] == -1:
        if sum(cl) == n:
            co = -1
            break
        if len(de) == 0:
            break
        de.append([-1,-1])
        co += 1
        cl = ppppp[:]

    elif ppp[kkk[0]] != 0 and on[kkk[0]][0] == kkk[1] and cl[kkk[0]] and cl[kkk[1]]:
        cl[kkk[0]] = 0
        cl[kkk[1]] = 0
        on[kkk[0]].popleft()
        on[kkk[1]].popleft()
        ppp[kkk[0]] -= 1
        ppp[kkk[1]] -= 1
        if ppp[kkk[1]] != 0 != 0 and ppp[kkk[0]] != 0 and on[kkk[1]][0] == kkk[0] and on[kkk[0]][0] == kkk[1]:
            de.append([on[kkk[1]][0],kkk[1]])
        else:
            if len(on[kkk[1]]) != 0:
                de.append([on[kkk[1]][0],kkk[1]])
            if len(on[kkk[0]]) != 0:
                de.append([on[kkk[0]][0],kkk[0]])


print(co)
### BUGGY CODE ###

N=int(input())
a=list(map(int,input().split()))
l=""
for i in range(N):
    print(a.index(i+1)+1,end=" ")

### FIXED CODE ###

N=int(input())
a=list(map(int,input().split()))
b=[0]*N
for index, m in enumerate(a):
    b[m-1]=index+1
print(*b)
### BUGGY CODE ###

a,b,x = map(int,input().split())
c=0
for i in range(a,b+1):
    if i%x == 0:
        c+=1
print(c)

### FIXED CODE ###

a,b,x = map(int,input().split())
ans=0
if a>0:
    ans = b//x-(a-1)//x
elif a==0:
    ans = b//x+1
print(ans)
### BUGGY CODE ###

from itertools import product

INF = 10**18

N, M = map(int, input().split())
XYZ = [list(map(int, input().split())) for _ in range(N)]

# i番目までのケーキの内、j個食べた時のpointの最大値
# (ただしpointの計算時には、8通りのmaskを乗算する)

def mul_mask(l, mask):
    return [a*b for a, b in zip(l, mask)]

dp_std = [[-INF for _ in range(M+1)] for _ in range(N+1)]
for i in range(N+1):
    dp_std[i][0] = 0
# print(dp_std)

max_p = -INF
for mask in product([-1, 1], repeat=3):
    dp = dp_std.copy()
    for i in range(1, N+1):
        score = sum(mul_mask(XYZ[i-1], mask))
        for j in range(1, M+1):
            # print(i, j, XYZ[i-1], mask)
            dp[i][j] = max(
                dp[i-1][j],
                dp[i-1][j-1] + score
            )
            # for dp_i in dp:
            #     print(dp_i)
    p = dp[N][M]
    max_p = max(max_p, p)
    # print(p)

print(max_p)

### FIXED CODE ###

# from itertools import product

INF = 10**18

N, M = map(int, input().split())
XYZ = [list(map(int, input().split())) for _ in range(N)]

# i番目までのケーキの内、j個食べた時のpointの最大値
# (ただしpointの計算時には、8通りのmaskを乗算する)

def mul_mask(l, mask):
    p = []
    for i, m in enumerate(l):
        p.append(m*mask[i])
        # print(p)
    return p
    # return [a*b for a, b in zip(l, mask)]

dp_std = [[-INF for _ in range(M+1)] for _ in range(N+1)]
for i in range(N+1):
    dp_std[i][0] = 0
# print(dp_std)

max_p = -INF
# masks = product([-1, 1], repeat=3)
masks = []
for i in [1, -1]:
    for j in [1, -1]:
        for k in [1, -1]:
            masks.append([i, j, k])
# print(masks)
for mask in masks:
    dp = dp_std[:]
    for i in range(1, N+1):
        score = sum(mul_mask(XYZ[i-1], mask))
        for j in range(1, M+1):
            # print(i, j, XYZ[i-1], mask)
            dp[i][j] = max(
                dp[i-1][j],
                dp[i-1][j-1] + score
            )
            # for dp_i in dp:
            #     print(dp_i)
    p = dp[N][M]
    max_p = max(max_p, p)
    # print(p)

print(max_p)
### BUGGY CODE ###

N=int(input())
A = list(map(int, input().strip().split()))
for i in range(1,N+1):
  print(A.count(i))

### FIXED CODE ###

n=int(input())
A = list(map(int, input().split()))
list=[0]*(n+2)

for i in range(n-1):
  list[A[i]]+=1
for i in range(1,n+1):
  print(list[i])
### BUGGY CODE ###

s = input()
s_len = len(s)
n = 2019
mod_list = [0] * n
mod_list[0] = 1

for i in range(s_len):
    t_i = int(s[i:])
    m = t_i % n
    mod_list[m] += 1

result = sum(i * (i - 1) // 2 for i in mod_list)
print(result)

### FIXED CODE ###

s = input()
s_len = len(s)
n = 2019
mod_list = [0] * n
mod_list[0] = 1

p = 1
d = 0
for t in reversed(s):
    d += int(t) * p
    m = d % n
    mod_list[m] += 1
    p *= 10
    p %= 2019

result = sum(i * (i - 1) // 2 for i in mod_list)
print(result)
### BUGGY CODE ###

class UnionFind():
	def __init__(self, size):
		self.table = [-1 for _ in range(size)]

	def find(self, x):
		while self.table[x] >= 0:
			x = self.table[x]
		return x

	def union(self, x, y):
		s1 = self.find(x)
		s2 = self.find(y)
		if s1 != s2:
			if self.table[s1] > self.table[s2]:
				self.table[s2] = s1
			elif self.table[s1] < self.table[s2]:
				self.table[s1] = s2
			else:
				self.table[s1] = s2
				self.table[s2] -= 1


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

uf = UnionFind(n)

for i in range(m):
	x, y = map(int, input().split())
	if uf.find(x - 1) != uf.find(y - 1):
		uf.union(x - 1, y - 1)

ans = 0
for i, pp in enumerate(p):
	if uf.find(pp - 1) == uf.find(i):
		ans += 1

print(ans)

### FIXED CODE ###

class UnionFind():
	def __init__(self, size):
		self.table = [-1 for _ in range(size)]

	def find(self, x):
		if self.table[x] < 0:
			return x
		else:
			self.table[x] = self.find(self.table[x]) #xをxの根に直接つなぐ
			return self.table[x]

	def union(self, x, y):
		s1 = self.find(x)
		s2 = self.find(y)
		if s1 == s2:
			return
		else:
			st1 = self.table[s1]
			st2 = self.table[s2]
			if st1 > st2:
				self.table[s2] = s1
			elif st1 < st2:
				self.table[s1] = s2
			else:
				self.table[s1] = s2
				self.table[s2] -= 1


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

uf = UnionFind(n)

for i in range(m):
	x, y = map(int, input().split())
	uf.union(x - 1, y - 1)

ans = 0
for i, pp in enumerate(p):
	if pp - 1 == i:
		ans += 1
	elif uf.find(pp - 1) == uf.find(i):
		ans += 1

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

s = input()
q = int(input())
mode = True
for _ in range(q):
    tfc = input().split()
    if int(tfc[0]) == 1:
        mode = not mode
    else:
        if mode:
            s = tfc[2]+s if int(tfc[1]) == 1 else s+tfc[2]
        else:
            s = s+tfc[2] if int(tfc[1]) == 1 else tfc[2]+s
print(s if mode else s[::-1])

### FIXED CODE ###

s = input()
q = int(input())
mode = True
l = ''
r = ''
for _ in range(q):
    tfc = input().split()
    if int(tfc[0]) == 1:
        mode = not mode
    else:
        if mode:
            if int(tfc[1]) == 1:
                l += tfc[2]
            else:
                r += tfc[2]
        else:
            if int(tfc[1]) == 1:
                r += tfc[2]
            else:
                l += tfc[2]
print(l[::-1]+s+r if mode else r[::-1]+s[::-1]+l)
### BUGGY CODE ###

N = input()
N =int(N)
nums= list(map(int,input().split(" ")))
nums.sort()
ans = 0

for _ in  range(N):
    nums.pop(-1)
    ans += nums.pop(-1)
    nums.pop(0)
print(ans)

### FIXED CODE ###

N = input()
N =int(N)
nums= list(map(int,input().split(" ")))
nums.sort()
ans = 0

for _ in  range(N):
    nums.pop()
    ans += nums.pop()
print(ans)
### BUGGY CODE ###

import heapq
n,m=map(int,input().split())
a=list(map(int,input().split()))
q=[]
for i in range(n):
  q.append((-1)*a[i])
for k in range(m):
  heapq.heapify(q)
  ma=heapq.heappop(q)
  if ma%2==0:
    heapq.heappush(q,ma//2)
  else:
    heapq.heappush(q,ma//2+1)
print(sum(q)*(-1))

### FIXED CODE ###

import heapq
n,m=map(int,input().split())
a=list(map(int,input().split()))
q=[]
for i in range(n):
  q.append((-1)*a[i])
heapq.heapify(q)
for k in range(m):
  ma=heapq.heappop(q)
  if ma%2==0:
    heapq.heappush(q,ma//2)
  else:
    heapq.heappush(q,ma//2+1)
print(sum(q)*(-1))
### BUGGY CODE ###

# 2019/08/16

s=list(input())
t=list(input())

c1={}
c2={}
for ss,tt in zip(s,t):
    c1[ss]=c1.get(ss,'')+tt
    c2[tt]=c2.get(tt,'')+ss

for ss,tt in zip(c1.values(),c2.values()):
    if len(set(ss))>1 or len(set(tt))>1:
        print('No')
        exit()
else:print('Yes')


### FIXED CODE ###

# 2019/08/16

s=list(input())
t=list(input())

c1={}
c2={}
for ss,tt in zip(s,t):
    if c1.get(ss) is None:
        c1[ss]=tt
    if c2.get(tt) is None:
        c2[tt]=ss
    if c1[ss]==tt and c2[tt]==ss:continue
    else:
        print('No')
        exit()

print('Yes')
### BUGGY CODE ###

MOD=998244353
N,M,K=map(int,input().split())

def powmod(a,p):
  if p==0:
    return 1
  else:
    pow2=powmod(a,p//2)
    if p%2==0:
      return (pow2**2)%MOD
    else:
      return (a*pow2**2)%MOD
def invmod(a):
  return powmod(a,MOD-2)

if M==1 and K<N-1:
  print(0)
else:
  answer=0
  term1=powmod(M-1,N-1)
  inv_M1=invmod(M-1)
  term2=1
  ans_k=M
  for i in range(K+1):
    answer+=(ans_k*term1*term2)%MOD
    answer%=MOD
    term1=term1*inv_M1%MOD
    term2=term2*(N-i-1)*invmod(i+1)%MOD
    
  print(answer)

### FIXED CODE ###

MOD=998244353
N,M,K=map(int,input().split())

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

def powmod(a,p):
  if p==0:
    return 1
  else:
    pow2=powmod(a,p//2)
    if p%2==0:
      return (pow2**2)%MOD
    else:
      return (a*pow2**2)%MOD
def invmod(a):
  return powmod(a,MOD-2)

if M==1 and K<N-1:
  print(0)
elif K==N-1:
  print(powmod(M,N))
else:
  ans=0
  term1=powmod(M-1,N-1)
  term2=1
  inv_M1=invmod(M-1)
  for i in range(K+1):
    ans+=term1*term2
    ans%=MOD
    term1=term1*inv_M1%MOD
    term2=term2*(N-i-1)*inv_table[i+1]%MOD
    
  answer=M*ans%MOD
  print(answer)
### BUGGY CODE ###

import numpy as np
from itertools import accumulate

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


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

c=[i for i in range(n)]

b=np.array(b)
c=np.array(c)
c=c[1:]

ans=0
ans+=np.sum(b==c)
for i in range(1,n):
  b-=a[i-1]
  b+=a[i]
  b=b[1:]

  c-=1
  c=c[1:]

  ans+=np.sum(b==c)

print(ans)

### FIXED CODE ###

from collections import Counter

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

q1=[]
q2=[]

for i in range(n):
  q1.append(i+a[i])
  q2.append(i-a[i])

c1=Counter(q1)
c2=Counter(q2)

ans=0
for i in c1.keys():
  num1=c1[i]
  num2=c2[i]
  ans+=num1*num2

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

def input_int():
    return map(int, input().split())

def one_int():
    return int(input())

def one_str():
    return input()

def many_int():
    return list(map(int, input().split()))

S= one_str()

Q = one_int()

Qs = [ input() for i in range(Q)]
def ss(S, Qs):
    for temp in Qs:
#         temp = input()
        if len(temp)>=2:
            T, F, C = temp.split()
            if F=="1":
                S = C+S
            else:
                S = S+C
        else:        
            S=S[::-1]

    return S

print(ss(S,Qs))

### FIXED CODE ###

def input_int():
    return map(int, input().split())

def one_int():
    return int(input())

def one_str():
    return input()

def many_int():
    return list(map(int, input().split()))

S= one_str()

Q = one_int()

Qs = [ input() for i in range(Q)]
def ss(S, Qs):
    is_not_ac=False
    head = ""
    tail = ""
    for temp in Qs:
#         temp = input()
        if len(temp)>=2:
            T, F, C = temp.split()
            if F=="1":
                if is_not_ac:
                    tail += C
                else:
                    head += C
            else:
                if is_not_ac:
                    head += C
                else:
                    tail += C
        else:        
            is_not_ac = not is_not_ac
    if is_not_ac:
        return tail[::-1] + S[::-1] + head
    else:
        return head[::-1] + S + tail


print(ss(S,Qs))
### BUGGY CODE ###

k,s = map(int, input().split())
count = 0
for x in range(k+1):
    for y in range(x, k+1):
        for z in range(y, k+1):
            if x+y+z==s:
                if x==y and y==z:
                    count += 1
                elif x==y or y==z or z==x:
                    count += 3
                else:
                    count += 6
print(count)
print("\n")



### FIXED CODE ###

K, S = map(int, input().split())

counter = 0

#すべての値が等しい場合 i = j = k
if S%3 == 0:
    counter += 1

for i in range(K):
    yz = S - i
    #2つの値が等しい場合 i < j = k
    if yz%2 == 0 and yz/2 <= K and yz/2 > i:
        counter += 3
    # 2つの値が等しい場合 i = j < k
    if yz - i <= K and yz - i > i:
        counter += 3
    #すべての値が異なる場合 i < j < k
    for j in range(i+1, K):
        k = S - i - j
        if k > j and k <= K:
            counter += 6

print(counter)
print("\n")
### BUGGY CODE ###

from collections import defaultdict, deque
import sys
import heapq
import bisect
import math
import itertools
import string
import queue
import copy
import time
# import numpy as np
from fractions import gcd

sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7

def inp(): return int(sys.stdin.readline())
 
def inp_list(): return list(map(int, sys.stdin.readline().split()))

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


N = inp()
S = input()

cnt = 0
for i in range(N):
    for j in range(i + 1, N):
        for k in range(j + 1, N):
            if j - i == k - j: continue
            if (S[i] == S[j]) or (S[i] == S[k]) or (S[j] == S[k]): continue
            cnt += 1
print(cnt)


### FIXED CODE ###

from collections import defaultdict, deque
import sys
import heapq
import bisect
import math
import itertools
import string
import queue
import copy
import time
# import numpy as np
from fractions import gcd

sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7


def inp(): return int(sys.stdin.readline())


def inp_list(): return list(map(int, sys.stdin.readline().split()))


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


N = inp()
S = input()

"""
    Conditions:
        1. S[i] \ne S[j] and S[j] \ne S[k] and S[k] \ne S[i]
        2. j - i \ne k - j
"""

r = S.count('R')
g = S.count('G')
b = S.count('B')
# 条件1を満たす組は rgb 個。それから「条件1を満たしてかつ条件 2 を満たさない」組を引く。条件を満たさないもののほうが多い。


cnt = 0
for i in range(N):
    for j in range(i + 1, N):
        k = j + (j - i) # => k - j == j - i
        if k > N - 1: break
        if S[i] != S[j] and S[j] != S[k] and S[k] != S[i]:
            cnt += 1

print(r * g * b - cnt)
### BUGGY CODE ###

from collections import deque
n,m = map(int,input().split())

maze = [list(input()) for _ in range(n)]

def bfs():
    dx = (1, 0, -1, 0)
    dy = (0, 1, 0, -1)
    d = [([-1]*m)for _ in range(n)]
    q = deque([])
    for i in range(n):
        for j in range(m):
            if maze[i][j] == "#":
                d[i][j] = 0
                q.append((i,j))
    a = 0

    while q:
        x,y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<= nx < n and 0<= ny < m and maze[nx][ny] != '#' and d[nx][ny] == -1:
                q.append((nx,ny))
                d[nx][ny] = d[x][y] +1
                a = max(a,d[nx][ny])
    return a

print(bfs())

### FIXED CODE ###

from collections import deque
n,m = map(int,input().split())

maze = [list(input()) for _ in range(n)]

def bfs():
    dx = (1, 0, -1, 0)
    dy = (0, 1, 0, -1)
    d = [([-1]*m)for _ in range(n)]
    q = deque([])
    for i in range(n):
        for j in range(m):
            if maze[i][j] == "#":
                d[i][j] = 0
                q.append((i,j))
    a = 0

    while q:
        x,y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<= nx < n and 0<= ny < m and maze[nx][ny] != '#' and d[nx][ny] == -1:
                q.append((nx,ny))
                d[nx][ny] = d[x][y] +1
                a = max(a,d[nx][ny])
    return a

print(bfs())
### BUGGY CODE ###

import math
L,R = map(int,input().split())
anslist = []
for i in range(L,R):
    for j in range(i+1,R+1):
        if i%2019 == j%2019:
            continue
        anslist.append((i*j)%2019)
ans = min(anslist)
print(ans)

### FIXED CODE ###

L, R = map(int, input().split())
mn = 2019
for i in range(L, min(L + 2019, R + 1)):
    for j in range(i + 1, min(L + 2019, R + 1)):
        mn = min(mn, i * j % 2019)
print(mn)
### BUGGY CODE ###

S = input()

rs = [0] * 13

M = 10**9 + 7

if S[-1] == "?":
    rs[:10] = [1] * 10
else:
    rs[int(S[-1])] = 1

for i in range(1, len(S)):
    nrs = [0] * 13
    c = S[-i - 1]
    if c == "?":
        ns = range(10)
    else:
        ns = [int(c)]
    for n in ns:
        r = (10 ** i) * n % 13
        for j in range(13):
            jj = (j + r) % 13
            nrs[jj] = (nrs[jj] + rs[j]) % M
    rs = nrs

# print(rs)
print(rs[5])



### FIXED CODE ###

S = input()

rs = [0] * 13

M = 10**9 + 7

if S[-1] == "?":
    rs[:10] = [1] * 10
else:
    rs[int(S[-1])] = 1

for i in range(1, len(S)):
    nrs = [0] * 13
    c = S[-i - 1]
    if c == "?":
        ns = range(10)
    else:
        ns = [int(c)]
    for n in ns:
        r = (10 ** (i % 6)) * n % 13
        for j in range(13):
            jj = (j + r) % 13
            nrs[jj] = (nrs[jj] + rs[j]) % M
    rs = nrs

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

N=int(input())
A=[int(input()) for _ in range(N)]
ll=sorted(A)
  
for n in A:
  if n==max(A):
    print(ll[-2])
  else:
    print(max(A))

### FIXED CODE ###

N=int(input())
A=[int(input()) for _ in range(N)]
ll=sorted(A)
a=max(A)
b=ll[-2]
  
for n in A:
  if n==a:
    print(b)
  else:
    print(a)
### BUGGY CODE ###


N, P = input().split()
p_len = len(P)
N = int(N)
P = int(P)

S = input()

cnt = 0

if P in [2,5]:
    for i in range(N):
        cnt += i+1 if int(S[i]) % P == 0 else 0
else:
    for l in range(1, N+1):
        for i in range(N+1-l):
            cnt += 1 if int(S[i:i+l]) % P == 0 else 0
print(cnt)

### FIXED CODE ###

N, P = input().split()
p_len = len(P)
N = int(N)
P = int(P)

S = input()


cnt = 0
if P in [2,5]:
    for i in range(N):
        cnt += i+1 if int(S[i]) % P == 0 else 0
else:
    table = [0] * P # ?1
    Ui = 0
    ten = 1
    
    S = S[::-1]
    table[0] = 1 # ?2
    
    for i in range(N):
        Ui = (Ui + int(S[i]) * ten) % P # ?3
        
        cnt += table[Ui] # ?4
        
        table[Ui] += 1 # ?5
        ten = (ten * 10) % P # ?6
print(cnt)
### BUGGY CODE ###

n = int(input())
p = list(map(int, input().split()))
cnt = 0
for i in range(n):
    if p[i] == min(p[:i + 1]):
        cnt += 1
print(cnt)

### FIXED CODE ###

n = int(input())
p = list(map(int, input().split()))
cnt = 0
tmp = 2 * 10 ** 6
for i in range(n):
    if p[i] <= tmp:
        cnt += 1
        tmp = min(tmp, p[i])
print(cnt)
### BUGGY CODE ###

from operator import itemgetter
N, T = [int(i) for i in input().split()]

data = []
for i in range(N):
    data.append([int(i) for i in input().split()])

data.sort(key=itemgetter(0))

dp = [[0]*(T) for i in range(N)]
ans = data[0][1]
for i in range(1, N):
    for j in range(T):
        if j >= data[i-1][0]:
            value1 = dp[i-1][j]
            value2 = dp[i-1][j-data[i-1][0]] + data[i-1][1]
            dp[i][j] = max(value1, value2)
        else:
            dp[i][j] = dp[i-1][j]
    value3 = dp[i][T-1] + data[i][1]
    ans = max(value3, ans)
print(ans)


### FIXED CODE ###

from operator import itemgetter
N, T = [int(i) for i in input().split()]

data = []
for i in range(N):
    data.append([int(i) for i in input().split()])

data.sort(key=itemgetter(0))

dp = [[0]*(T) for i in range(N)]
ans = data[0][1]
for i in range(1, N):
    for j in range(T):
        if j >= data[i-1][0]:
            value1 = dp[i-1][j]
            value2 = dp[i-1][j-data[i-1][0]] + data[i-1][1]
            dp[i][j] = max(value1, value2)
        else:
            dp[i][j] = dp[i-1][j]
    value3 = dp[i][T-1] + data[i][1]
    ans = max(value3, ans)
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python
N, M = map(int, input().split())
l1, r1 = map(int, input().split())
ans = [i for i in range(l1, r1+1)]
for m in range(M-1):
    l1, r1 = map(int, input().split())
    l = [i for i in range(l1, r1+1)]
    ans = list(set(ans) & set(l))
print(len(ans))

### FIXED CODE ###

#!/usr/bin/env python
import numpy as np
N, M = map(int, input().split())
l_max = 1
r_min = 100000
for i in range(M):
    l, r = map(int, input().split())
    if l > l_max:
        l_max = l
    if r < r_min:
        r_min = r
    if r_min < l_max:
        print(0)
        exit()
print(r_min - l_max + 1)
### BUGGY CODE ###

n = int(input())

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

m = 0

for a in range(n-2):
	for b in range(a+1,n-1):
		for c in range(b+1,n):
			if d[a]<d[b]+d[c] and d[b]<d[c]+d[a] and d[c]<d[a]+d[b]:
				m += 1
				#print(str(a)+" "+str(b)+" "+str(c))

print(m)

### FIXED CODE ###

import bisect

n = int(input())
d = list(map(int, input().split()))
d.sort()

m = 0

for a in range(n-2):
	for b in range(a+1,n-1):
		m+=bisect.bisect_left(d,d[a]+d[b])-1-b

print(m)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
 
n = int(input())
l = list(map(int, input().split()))
l.sort(reverse=True)
 
cnt = 0
for i in range(n):
  a = l[i]
  for j, b in enumerate(l[i+1:]):
    for c in l[i+j+2:]:
      if a < b+c:
        cnt += 1
print(cnt)

### FIXED CODE ###

import bisect
import sys
input = sys.stdin.readline
 
n = int(input())
l = [int(li) for li in input().split(' ')]
l.sort()

cnt = 0
for i in range(n):
  for j in range(i+1, n):
    cnt += bisect.bisect_left(l, l[i]+l[j])-j-1
    
print(cnt)