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

# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

N = int(input())
S = list(input())
Q = int(input())


alphabet = "abcdefghijklmnopqrstuvwxyz"

bag = { l:[] for l in alphabet}

for i in range(N):
  bag[S[i]].append(i+1)


import bisect

for _ in range(Q):
  t,a,b = input().split()
  a = int(a)
  if int(t) == 1:
    bag[S[a-1]].remove(a)
    S[a-1] = b
    bisect.insort(bag[b],a)
  else:
    count = 0
    b = int(b)
    for l in alphabet:
      if len(bag[l])>0:
        left = bisect.bisect_left(bag[l],a)
        if left != len(bag[l]):
          if bag[l][left] <= b:
            count += 1
    print(count)

### FIXED CODE ###

# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

N = int(input())
S = list(input())
Q = int(input())


alphabet = "abcdefghijklmnopqrstuvwxyz"

bag = { l:[] for l in alphabet}

for i in range(N):
  bag[S[i]].append(i+1)


import bisect

for _ in range(Q):
  t,a,b = input().split()
  a = int(a)
  if int(t) == 1:
    if S[a-1]!=b:
      bag[S[a-1]].remove(a)
      S[a-1] = b
      bisect.insort(bag[b],a)
  else:
    count = 0
    b = int(b)
    for l in alphabet:
      if len(bag[l])>0:
        left = bisect.bisect_left(bag[l],a)
        if left != len(bag[l]):
          if bag[l][left] <= b:
            count += 1
    print(count)
### BUGGY CODE ###

import collections, sys
from heapq import *
input = sys.stdin.readline
N, Q = [int(_) for _ in input().split()]
STX = [[int(_) for _ in input().split()] for _ in range(N)]
D = [int(input()) for _ in range(Q)]
event = []
for stx in STX:
    s, t, x = stx
    heappush(event, [s - x, 1, x])
    heappush(event, [t - x, 0, x])
for d in D:
    heappush(event, [d, 2])
block = set()
while event:
    e = heappop(event)
    if e[1] == 0:
        block.remove(e[2])
    elif e[1] == 1:
        block.add(e[2])
    else:
        if block:
            print(min(block))
        else:
            print(-1)


### FIXED CODE ###

import sys
input = sys.stdin.readline
N, Q = [int(_) for _ in input().split()]
STX = [[int(_) for _ in input().split()] for _ in range(N)]
D = [int(input()) for _ in range(Q)]
events = []
for stx in STX:
    s, t, x = stx
    events += [[s - x, 1, x], [t - x, 0, x]]
for i in range(Q):
    events += [[D[i], 2, i]]
events.sort()
block = set()
ans = [-1] * Q
m = float('inf')
for e in events:
    if e[1] == 0:
        block.remove(e[2])
        if m == e[2]:
            if block:
                m = min(block)
            else:
                m = float('inf')
    elif e[1] == 1:
        block.add(e[2])
        m = min(m, e[2])
    else:
        if block:
            if m == float('inf'):
                ans[e[2]] = -1
            else:
                ans[e[2]] = m
print(*ans, sep='\n')
### BUGGY CODE ###

import itertools
n = int(input())
a = list(map(int,input().split()))
c = [i for i in range(n)]
comb = list(itertools.combinations(c,2))
cnt=0
for x in range(len(comb)):
    i = comb[x][0]
    j = comb[x][1]
    if j-i==a[j]+a[i]:
        cnt+=1
print(cnt)

### FIXED CODE ###

from collections import Counter
n = int(input())
a = list(map(int,input().split()))
L = [0]*n
R = [0]*n
cnt=0
for i in range(n):
    L[i] = i+a[i]
    R[i] = i-a[i]
z1=Counter(L)
z2=Counter(R)
cnt=0
for k1,v1 in z1.items():
    v2 = z2[k1]
    cnt += v1*v2
print(cnt)
### BUGGY CODE ###

N, M = map(int, input().split())
left = []
right = []
for i in range(M):
  a, b = map(int, input().split())
  if a == 1:
    left.append(b)
  elif b == N:
    right.append(a)
    
flag = False
for r in right:
  if r in left:
    flag = True
    break
    
if flag:
  print('POSSIBLE')
else:
  print('IMPOSSIBLE')

### FIXED CODE ###

N, M = map(int, input().split())
left = []
right = []
for i in range(M):
  a, b = map(int, input().split())
  if a == 1:
    left.append(b)
  elif b == N:
    right.append(a)
    
flag = False
left = set(left)
for r in right:
  if r in left:
    flag = True
    break
    
if flag:
  print('POSSIBLE')
else:
  print('IMPOSSIBLE')
### BUGGY CODE ###

n=int(input())

def bin(start):
    ok=1
    ng=n+1
    while abs(ng-ok)>1:
        mid=(ok+ng)//2
        print(mid)
        s=input()
        if s=='Vacant':exit()
        if mid%2==0 and start==s:
            ok=mid
        if mid%2!=0 and start!=s:
            ok=mid
        else:
            ng=mid
print(0)
start=input()
bin(start)


### FIXED CODE ###

import sys
n=int(input())

def bin(start):
    ok=0
    ng=n
    while abs(ng-ok)>1:
        mid=(ok+ng)//2
        print(mid)
        sys.stdout.flush()
        s=input()
        if s=='Vacant':exit()
        if mid%2==0 and start==s:
            ok=mid
        elif mid%2!=0 and start!=s:
            ok=mid
        else:
            ng=mid
print(0)
start=input()
sys.stdout.flush()
if start=='Vacant':exit()
bin(start)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

s_len, n = map(int, input().split())
s = input().rstrip()
for i in range(n):
  count = 0
  a, b = map(int, input().split())
  s_slice = s[a-1:b]  
  for i in range(len(s_slice)-1):
    if s_slice[i:2+i]=="AC":
      count += 1
  print(count)
  


### FIXED CODE ###

import sys
input = sys.stdin.readline

import bisect
left = bisect.bisect_left
right = bisect.bisect_right 

n, q = list(map(int, input().split()))
s = input()
lr = [list(map(int, input().split())) for i in range(q)]
a = [i for i in range(n-1) if s[i:i+2]=="AC"]

for i in range(q):
  left_index = left(a, lr[i][0]-1)      
  right_index = right(a, lr[i][1]-2)  
  print(right_index - left_index)
### BUGGY CODE ###

import itertools
N=int(input())
S=input()
kes=N-3
pass_set=set([])
for thing in itertools.combinations(range(0,N),3):
    t=sorted(thing)
    pswd=S[t[0]]+S[t[1]]+S[t[2]]
    pass_set.add(pswd)
print(len(pass_set))

### FIXED CODE ###

import itertools
N=int(input())
S=[int(thing) for thing in list(input())]
kes=N-3
pass_set=set([])
def passkosu(k):
    num = 0

    if k in S[0:N-1]:
        l_left=S.index(k)
        for l in range(0,10):
            if l in S[l_left+1:N-1]:
                l_center=S[l_left+1:].index(l)+l_left+1
                dif=len(set(S[l_center+1:]))
                num=num+dif
    return num

print(sum([passkosu(i) for i in range(0,10)]))
### BUGGY CODE ###

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

q = int(input())

from collections import Counter

ca = Counter(a)

def sum_dict(dic):
    return sum([num*cnt for num,cnt in dic.items()])

for _ in range(q):
    b,c = list(map(int, input().split()))
    
    if b in ca:
        cnt = ca.pop(b)
        ca[c] += cnt
    
    print(sum_dict(ca))

### FIXED CODE ###

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

q = int(input())

from collections import Counter

ca = Counter(a)

ans=sum(a)
for _ in range(q):
    b,c = list(map(int, input().split()))
    
    if b in ca:
        cnt = ca.pop(b)
        ca[c] += cnt

        ans -= b * cnt
        ans += c * cnt
    
    print(ans)
### BUGGY CODE ###

import sys
c=0
b=0
wi=0
x=[-1,0,1,0]
y=[0,-1,0,1]
buf=[]
def count(h,w,S,table,H,W,index):
    global buf,x,y,b,wi
    if index==1:
        b+=1
    else:
        wi+=1
    if index==1:
        S[h][w]='6'
    for i in range(4):
        if h+y[i]>=0 and h+y[i]<H and w+x[i]>=0 and w+x[i]<W:
            if table[h+y[i]][w+x[i]]==-1:
                if index==0 and S[h+y[i]][w+x[i]]=='#':
                    table[h+y[i]][w+x[i]]=table[h][w]+1
                    buf.append([h+y[i],w+x[i],1])
                elif index==1 and S[h+y[i]][w+x[i]]=='.':
                    table[h+y[i]][w+x[i]]=table[h][w]+1
                    buf.append([h+y[i],w+x[i],0])
    if buf:
        a=buf.pop(0)
        count(a[0],a[1],S,table,H,W,a[2])
sys.setrecursionlimit(10000000)
H,W=map(int,input().split())
T=[]
for i in range(H):
    T.append(input())
S=[['' for j in range(W)]for i in range(H)]
for h in range(H):
    for w in range(W):
        S[h][w]=T[h][w]
for h in range(H):
    for w in range(W):
        if S[h][w]=='#':
            table=[[-1 for j in range(W)] for i in range(H)]
            table[h][w]=0
            p=0
            count(h,w,S,table,H,W,1)
            
            c+=b*wi
            b=0
            wi=0
print(c)




### FIXED CODE ###

import sys
c=0
b=0
wi=0
x=[-1,0,1,0]
y=[0,-1,0,1]
buf=[]
def one():
    return -1
def count(h,w,S,table,H,W,index):
    global buf,x,y,b,wi
    if index==1:
        b+=1
    else:
        wi+=1
    if index==1:
        S[h][w]='@'
    for i in range(4):
        if h+y[i]>=0 and h+y[i]<H and w+x[i]>=0 and w+x[i]<W:
            if table[h+y[i]][w+x[i]]==-1:
                if index==0 and S[h+y[i]][w+x[i]]=='#':
                    table[h+y[i]][w+x[i]]=1
                    buf.append([h+y[i],w+x[i],1])
                elif index==1 and S[h+y[i]][w+x[i]]=='.':
                    table[h+y[i]][w+x[i]]=1
                    buf.append([h+y[i],w+x[i],0])
    if buf:
        a=buf.pop(0)
        count(a[0],a[1],S,table,H,W,a[2])
sys.setrecursionlimit(10000000)
H,W=map(int,input().split())
T=[]
table=[[-1 for j in range(W)] for i in range(H)]
for i in range(H):
    T.append(input())
S=[['' for j in range(W)]for i in range(H)]
for h in range(H):
    for w in range(W):
        S[h][w]=T[h][w]
for h in range(H):
    for w in range(W):
        if S[h][w]=='#':
            table[h][w]=0
            count(h,w,S,table,H,W,1)
            c+=b*wi
            b=0
            wi=0
print(c)
### BUGGY CODE ###

from sys import stdin
f_i = stdin

N = int(f_i.readline())

adj = [[] for i in range(N)]
for i in range(N - 1):
    A, B = map(int, f_i.readline().split())
    A -= 1
    B -= 1
    adj[A].append(B)
    adj[B].append(A)

mod = 10 ** 9 + 7
pow2 = [(2 ** i) % mod for i in range(N + 1)]

from sys import setrecursionlimit
setrecursionlimit(10 ** 6)

ans = 0
def dfs(node, parent):
    global ans
    cnt = 1
    for child in adj[node]:
        if child != parent:
            cnt += dfs(child, node)
    
    ans += (pow2[cnt] - 1) * (pow2[N-cnt] - 1)
    ans %= mod
    return cnt

dfs(0, None)

ans = (ans - N * pow2[N-1] + pow2[N] - 1) % mod
ans = ans * pow(pow2[N], mod - 2, mod) % mod

print(ans)

### FIXED CODE ###

from sys import stdin
f_i = stdin

N = int(f_i.readline())

adj = [[] for i in range(N)]
for i in range(N - 1):
    A, B = map(int, f_i.readline().split())
    A -= 1
    B -= 1
    adj[A].append(B)
    adj[B].append(A)

mod = 10 ** 9 + 7

pow2 = [1] * (N + 1)
for i, j in zip(range(N), range(1, N + 1)):
    pow2[j] = pow2[i] * 2 % mod

from sys import setrecursionlimit
setrecursionlimit(10 ** 6)

ans = 0

def dfs(node, parent):
    global ans
    cnt = 1
    
    for child in adj[node]:
        if child != parent:
            cnt += dfs(child, node)
    
    ans += (pow2[cnt] - 1) * (pow2[N-cnt] - 1)
    ans %= mod
    
    return cnt

dfs(0, None)

ans = (ans - N * pow2[N-1] + pow2[N] - 1) % mod
ans = ans * pow(pow2[N], mod - 2, mod) % mod

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

import queue
import sys
sys.setrecursionlimit(1000000)

h, w = map(int, input().split())
s = [list(input()) for i in range(h)]

que = queue.Queue()
class stgo:
    def __init__(self):
        self.x = 0
        self.y = 0
        self.depth = 0
y_dist = (0, 0, -1, +1)
x_dist = (-1, +1, 0, 0)
g_y = 0
g_x = 0

def bfs():
    dist = [[-1] * (w) for i in range(h)]
    maxdepth = 0
    while not que.empty():
        now = que.get()
        y = now.y
        x = now.x
        depth = now.depth
        dist[now.y][now.x] = depth
        maxdepth = max(maxdepth, depth)

        for z in range(4):
            next = stgo()
            next.y = y + y_dist[z]
            next.x = x + x_dist[z]
            next.depth = depth + 1

            if next.y >= 0 and next.y <= h - 1 and next.x >= 0 and next.x <= w - 1 and s[next.y][next.x] == "." and dist[next.y][next.x] == -1:
                que.put(next)
    return maxdepth

ans = 0
for i in range(h):
    for j in range(w):
        if s[i][j] != "#":
            start = stgo()
            start.x = j
            start.y = i
            start.depth = 0
            que.put(start)
            ans = max(ans,bfs())
print(ans)

### FIXED CODE ###

import queue

H, W = map(int, input().split())
S = [input() for i in range(H)]
q = queue.Queue()
longest_path = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == '.':
            g = [[0 if S[k][l] == '.' else -1 for l in range(W)] for k in range(H)]
            q.put((i,j))
            g[i][j] = 0
            while not(q.empty()):
                x, y = q.get()
                for nx, ny in [(x+1, y),(x-1, y),(x, y+1),(x, y-1)]:
                    if nx < 0 or nx > H-1 or ny < 0 or ny > W-1: continue
                    if g[nx][ny] != 0: continue
                    if nx == i and ny == j: continue
                    g[nx][ny] = g[x][y] + 1
                    q.put((nx,ny))
            longest_path = max(longest_path, max(map(max, g)))
print(longest_path)
### BUGGY CODE ###

s=input()

d=[0]*2019
dp=0
d[0]+=1
l=len(s)
r=1
for i in range(l-1,-1,-1):
	dp = (dp+int(s[i])*r)%2019
	r*=10%2019
	d[dp]+=1
res=0

for a in d:
	res+=a*(a-1)//2
	
print(res)

### FIXED CODE ###

s = list(input())
mods = [0]*(len(s))
countRemainder = [0] * 2019
cnt = 0


m = 1
mod = 0
for i in range(len(s)):
    mod += int(s[len(s) - i - 1]) * m

    mod %= 2019
    m *= 10
    m %= 2019

    countRemainder[mod] += 1

countRemainder[0] += 1

for i in range(2019):
    cnt += int(countRemainder[i] * (countRemainder[i] - 1) / 2)

print(cnt)
### BUGGY CODE ###

import math
import sys
input = sys.stdin.readline

s = input().strip()
t = ''
for i in range(len(s)):
	if s[i] == '?':
		t += 'D'
	else: 
		t += s[i]
print(t)

### FIXED CODE ###

import math
import sys
input = sys.stdin.readline

s = input().strip()
ans = []
for i in s:
	if i == '?':
		ans.append('D')
	else:
		ans.append(i)
print(''.join(ans))
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
s =0
for i in range(len(A)-1):
  for  j in A[i+1:]:
    s += A[i]*j
print(s % (10**9 +7) )

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
s =0
M = 10**9 +7
As = sum(A)
for i in range(N-1):
  As = As - A[i]
  s += (A[i] * As)%M
print(s%M)
### BUGGY CODE ###

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

dp=[0 for i in range(N)]

for i in range(1,N):
    for j in range(1,K+1):
        dp[i]=min(dp[i-j]+abs(H[i-j]-H[i]) for j in range(1,min(K+1,i+1)))
        
print(dp[N-1])

### FIXED CODE ###

def main():
    N,K=map(int,input().split())
    h=list(map(int,input().split()))

    ans=[0]*N
    ans[1]=abs(h[1]-h[0])


    for i in range(2,N):
        ans[i] = min(abs(h[i] - h[j]) + ans[j] for j in range(max(0,i-K),i))
    print(ans[N-1])
    
main()
### BUGGY CODE ###

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

for i in range(N):
  P[i] -= 1

ans = max(C)
S = set(range(N))
while S:
  scores = []
  x = S.pop()
  while True:
    scores.append(C[x])
    x = P[x]
    if x not in S:
      break
    S.remove(x)
  l = len(scores)
  if K <= l:
    for i in range(l):
      if scores[i] <= 0:
        continue
      ss = 0
      for k in range(K):
        ss += scores[(i+k)%l]
        ans = max(ans, ss)
  else:
    t = sum(scores)
    if t < 0:
      t = 0
    q, r = divmod(K, l)
    for i in range(l):
      if scores[i] <= 0:
        continue
      ss = t * (q - 1)
      for k in range(l):
        ss += scores[(i+k)%l]
        ans = max(ans, ss + (t if k < r else 0))

print(ans)

### FIXED CODE ###

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

for i in range(N):
  P[i] -= 1

ans = max(C)
S = set(range(N))
while S:
  scores = []
  x = S.pop()
  while True:
    scores.append(C[x])
    x = P[x]
    if x not in S:
      break
    S.remove(x)
  l = len(scores)
  if K <= l:
    for i in range(l):
      if scores[i] <= 0:
        continue
      ss = 0
      for k in range(K):
        ss += scores[(i+k)%l]
        ans = max(ans, ss)
  else:
    t = sum(scores)
    if t < 0:
      t = 0
    q, r = divmod(K, l)
    for i in range(l):
      if scores[i] <= 0:
        continue
      ss = t * (q - 1)
      for k in range(l):
        ss += scores[(i+k)%l]
        ans = max(ans, ss + (t if k < r else 0))

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

N=int(input())
A=[int(i) for i in input().split()]
B=[int(i) for i in input().split()]
count=0
if sum(A)<sum(B):
    print(-1)
else:
    dif=[A[i]-B[i] for i in range(N)]
    if min(dif)>=0:
        print(0)
    else:
        difsort=sorted(dif)
        pluslist=[i for i in difsort if i>=0]
        zero=difsort.index(pluslist[0])
        minum=len(difsort[:zero])
        maxsort=difsort[::-1]
        while sum(maxsort[0:count+1])<abs(sum(difsort[:zero])):
            count+=1
        
        print(count+1+minum)

### FIXED CODE ###

N=int(input())
A=[int(i) for i in input().split()]
B=[int(i) for i in input().split()]
count=0
if sum(A)<sum(B):
    print(-1)
else:
    dif=[A[i]-B[i] for i in range(N)]
    if min(dif)>=0:
        print(0)
    else:
        difsort=sorted(dif)
        plist=[i for i in difsort if i>=0][::-1]
        mlist=[i for i in difsort if i<0]
        mnum=len(mlist)
        msum=sum(mlist)
        for i in range(len(plist)):
            if msum>=0:
                break
            msum+=plist[i]
            count+=1
            
        
        print(count+mnum)
### BUGGY CODE ###

N=int(input())

for h in range(1,3501):
  for n in range(1,3501):
    x = 4*h*n - N*n - N*h
    y = N*h*n
    if x<=0 or y%x:
      continue
    else:
      print('{} {} {}'.format(h,n,y//x))
      exit()

### FIXED CODE ###

N=int(input())

if N==2:
  print('1 2 2')
  exit()

for h in range(N//4 +1, min(3501, 3*N//4 +1)):
  for n in range((N*h)//(4*h-N), min(3501, (2*N*h)//(4*h-N))):
    x = 4*h*n - N*n - N*h
    y = N*h*n
    if x>0 and not y%x:
      print('{} {} {}'.format(h,n,y//x))
      exit()
### BUGGY CODE ###

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

ans = 0
for i in range(N):
    a = A[i]
    for j in range(i+a, N):
        if j-i == A[j] + A[i]:
            ans += 1
print(ans)


### FIXED CODE ###

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

d = [0]*N
ans = 0
for i in range(N):
    a = A[i]
    l,r = i+a, i-a
    if 0 <= l < N:
        d[l] += 1
    if 0 <= r < N:
        ans += d[r]

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

# coding: utf-8
S = input()
cnt = sum(S[0:i].count("B") for i in range(len(S)) if S[i]=="W")
print(cnt)


### FIXED CODE ###

# coding: utf-8
S = input()

cnt = 0
ans = 0
for i in range(len(S)):
    if S[i]=="B":
        cnt+=1
    else:
        ans += cnt
        cnt += 0
print(ans)
### BUGGY CODE ###

import queue

N, M = map(int, input().split())
AB = {}
for i in range(N): AB[i] = set()
for _ in range(M):
    A, B = map(int, input().split())
    A -= 1
    B -= 1
    AB[A].add(B)
    AB[B].add(A)

finish = [False] * N
q = queue.Queue()
ans = 0
for i in range(N):
    if finish[i]: continue
    q.put(i)
    group = set()
    while not q.empty():
        x = q.get()
        group.add(x)
        finish[x] = True
        for friend in AB[x]:
            if finish[friend]: continue
            q.put(friend)
    ans = max(ans, len(group))
print(ans)


### FIXED CODE ###

import queue

N, M = map(int, input().split())
AB = {}
for i in range(N): AB[i] = set()
for _ in range(M):
    A, B = map(int, input().split())
    A -= 1
    B -= 1
    AB[A].add(B)
    AB[B].add(A)

finish = [False] * N
q = queue.Queue()
ans = 0
for i in range(N):
    if finish[i]: continue
    q.put(i)
    group = set()
    while not q.empty():
        x = q.get()
        group.add(x)
        finish[x] = True
        for friend in AB[x]:
            if finish[friend]: continue
            q.put(friend)
            finish[friend] = True
    tmp = len(group)
    if tmp >= N / 2:
        ans = tmp
        break
    ans = max(ans, len(group))
print(ans)
### BUGGY CODE ###

K = int(input())
total = 0

def gcd(a, b):
    if(a > b):
        a, b = b, a

    while(b > 0):
        r = a % b
        a = b
        b = r

    return a


for a in range(1, K+1):
    for b in range(1, K+1):
        res = gcd(a, b)
        for c in range(1, K+1):
           total += gcd(res, c)


print(total)

### FIXED CODE ###

K = int(input())
total = 0

def gcd(a, b):
    if(a > b):
        a, b = b, a

    while(b > 0):
        r = a % b
        a = b
        b = r

    return a

dp = [[0 for i in range(K+1)] for j in range(K+1)]

for a in range(1, K+1):
    for b in range(1, K+1):
        if(dp[a][b] == 0):
            dp[a][b] = gcd(a, b)

        res = dp[a][b]

        for c in range(1, K+1):
            if(dp[res][c] == 0):
                dp[res][c] = gcd(res, c)

            total += dp[res][c]


print(total)
### BUGGY CODE ###

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

if p == 2 or p == 5:
  ans = 0
  for i,c in enumerate(S):
    if int(c)%p == 0:
      ans += i+1
  print(ans)
  exit()

def MS(i,si,pre):
  return (si*(10**i) +pre)%p
 
M = [0]*p
pre = 0
for i,s in enumerate(S[::-1]):
  M[MS(i,int(s),pre)] += 1
  pre = MS(i,int(s),pre)

M[0] += 1
ans = sum(map(lambda m:(m*(m-1))//2, M))
print(ans)



### FIXED CODE ###

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

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

def MS(i,s,pre):
  return (s*i +pre)%p
 
M = [0]*p
M[0] = 1
t = 1
now = 0
for i in S[::-1]:
    i = int(i)
    now += i*t
    now %= p
    M[now] += 1
    t = t*10%p

ans = sum(map(lambda m:(m*(m-1))//2, M))
print(ans)
### BUGGY CODE ###

N, W = map(int, input().split())
w = [0]*N
v = [0]*N
for i in range(N):
    w[i], v[i] = map(int, input().split())

dp = [[0]*(W+1) for i in range(N+1)]

for i in range(N):
    for g in range(W+1):
        if g >= w[i]:
            dp[i+1][g] = max(dp[i][g-w[i]]+v[i], dp[i][g])
        else:
            dp[i+1][g] = dp[i][g]

print(dp[N][W])


### FIXED CODE ###

N, W = map(int, input().split())
wv = [[int(i) for i in input().split()] for i in range(N)]
 
dp=[[0]*(W+1) for i in range(N+1)]
 
for w in range(W+1):
    for n in range(N):
        if wv[n][0] <= w:
            dp[n+1][w] = max(dp[n][w-wv[n][0]] + wv[n][1], dp[n][w])
        else:
            dp[n+1][w] = dp[n][w]
 
 
print(dp[N][W])
### BUGGY CODE ###

# -*- coding: utf-8 -*-
"""
Created on Mon Apr 27 21:30:42 2020
"""

import sys
#import numpy as np

sys.setrecursionlimit(10 ** 9)
#def input():
#    return sys.stdin.readline()[:-1]
mod = 10**9+7

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

n = N
eat = X

def dfs(x):
    x

ans = 0
#print(ans,eat,n)
while eat > 0:
    if eat == (pow(2,n+2) - 3 + 1) //2:
        ans += pow(2,n) - 1 + 1
        eat = 0
        n -= 1
    elif eat > (pow(2,n+2) - 3 + 1) //2:
        ans += pow(2,n) - 1 + 1
        eat -= (pow(2,n+2) - 2) //2
        n -= 1
    else:
        eat -= 1
        n -= 1
#    print(ans,eat,n)

print(ans)
    


### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Sun May 19 16:57:17 2019

@author: Yamazaki Kenichi
"""

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

dp = [[1,1] for i in range(N+1)]
for i in range(1,N+1):
    dp[i][0] = dp[i-1][0]*2 + 1
    dp[i][1] = dp[i-1][1]*2 + 3

ans = 0
for i in range(2,N+2):
    if X - (dp[-i][1] + 2) >= 0:
        ans += dp[-i][0] + 1
        X -= (dp[-i][1] + 2)
#        print(ans,X,dp[-i])
    else:
        X -= 1
#        print(ans,X,dp[-i])
    if i == N+1 and X >= 1:
        ans += 1
#        print(ans,X,dp[-i])
print(ans)