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

class SegmentTree :
    def __init__(self, n) :
        self.n = n
        self.N0 = 1 << n.bit_length()
        self.data = [10**15] * (self.N0*2)
 
    def update(self, l, r, val) :
        l += self.N0
        r += self.N0
        while l < r:
            if l & 1 :
                self.data[l] = min(self.data[l], val)
                l += 1
            if r & 1:
                self.data[r-1] = min(self.data[r-1], val)
                r -= 1
            l //= 2
            r //= 2
 
    def query(self, i) :
        i += len(self.data) // 2
        ret = self.data[i]
        while i > 0 :
            i //= 2
            ret = min(ret, self.data[i])
        return ret if ret < 10**15 else -1
import bisect
N, Q = map(int, input().split())
roads = []
for _ in range(N):
    s, t, x = map(int, input().split())
    roads.append((x, s, t))
compress_list = []
query = []
for _ in range(Q):
    d = int(input())
    compress_list.append(d)
    query.append(d)
compress_list.sort()
S = SegmentTree(Q)
for x, s, t in roads:
    l = bisect.bisect_left(compress_list, s-x)
    r = bisect.bisect_left(compress_list, t-x)
    S.update(l, r, x)
for d in query:
    i = bisect.bisect_left(compress_list, d)
    print(S.query(i))



    

### FIXED CODE ###

class SegmentTree :
    def __init__(self, n) :
        self.n = n
        self.N0 = 1 << n.bit_length()
        self.data = [10**15] * (self.N0*2)
 
    def update(self, l, r, val) :
        l += self.N0
        r += self.N0
        while l < r:
            if l & 1 :
                self.data[l] = min(self.data[l], val)
                l += 1
            if r & 1:
                self.data[r-1] = min(self.data[r-1], val)
                r -= 1
            l //= 2
            r //= 2
 
    def query(self, i) :
        i += len(self.data) // 2
        ret = self.data[i]
        while i > 0 :
            i //= 2
            ret = min(ret, self.data[i])
        return ret if ret < 10**15 else -1
import bisect
import sys
input = sys.stdin.readline
N, Q = map(int, input().split())
roads = []
for _ in range(N):
    s, t, x = map(int, input().split())
    roads.append((x, s, t))
compress_list = []
query = []
for _ in range(Q):
    d = int(input())
    compress_list.append(d)
S = SegmentTree(Q)
for x, s, t in roads:
    l = bisect.bisect_left(compress_list, s-x)
    r = bisect.bisect_left(compress_list, t-x)
    S.update(l, r, x)
for i in range(Q):
    print(S.query(i))
### BUGGY CODE ###

s,t=[input() for u in (1,1)]
l,li=[['' for i in range(len(s)+1)] for j in (1,1)]
for j in range(len(t)):
  for i in range(len(s)):
    if t[j]==s[i]:
      l[i+1]=li[i]+t[j]
    else:l[i+1]=li[i+1] if len(li[i+1])>len(l[i]) else l[i]
    li=l
print(l[-1])

### FIXED CODE ###

s,t=input(),input()
n,m=len(s),len(t)
dp=[[0]*(m+1) for i in range(n+1)]
for i in range(n):
  for j in range(m):
    if s[i]==t[j]:
      dp[i+1][j+1]=dp[i][j]+1
    else:
      dp[i+1][j+1]=max(dp[i+1][j],dp[i][j+1])
ans=""
while m>0 and n>0:
  if s[n-1]==t[m-1]:ans=s[n-1]+ans;n-=1;m-=1
  elif dp[n][m]==dp[n-1][m]:n-=1
  else:m-=1
print(ans)
### BUGGY CODE ###

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

K = int(input())
total = 0
for a in range(K):
    for b in range(K):
        for c in range(K):
           total += gcd(a+1,b+1,c+1)
print(total)

### FIXED CODE ###

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

K = int(input())
total = 0
for a in range(K):
    for b in range(K):
        for c in range(K):
           total += gcd(a+1,b+1,c+1)
print(total)
### BUGGY CODE ###

n = int(input())
a = [i for i in map(int, input().split())]
for j in range(1, n+1):
  ans = a.count(j)
  print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
ans= [0] * n
         
for i in range(n-1):
    ans[a[i] - 1] += 1

for j in range(n):
    print(ans[j])
### BUGGY CODE ###

import bisect


N, Q = map(int, input().split(" "))
check_points = [list(map(int, input().split(" "))) for _ in range(N)]
querys = [int(input()) for i in range(Q)]
time = {}
for q in querys:
    time[q] = -1

for s, f, x in check_points:
    start, end = [s-x, f-x]
    left = bisect.bisect_left(querys, start)
    right = bisect.bisect_left(querys, end)
    for q in querys[left:right]:
        if time[q] == -1 or time[q] > x:
            time[q] = x


for q in querys:
    print(time[q])


### FIXED CODE ###

from bisect import bisect_left
from operator import itemgetter

N, Q = map(int, input().split(" "))
check_points = [tuple(map(int, input().split(" "))) for _ in range(N)]
querys = [int(input()) for _ in range(Q)]
time = [-1 for _ in range(Q)]
jump = [-1 for _ in range(Q)]
check_points = sorted(check_points, key=itemgetter(2))
b_left = bisect_left

for line in check_points:
    s, f, x = line
    start = s-x
    end = f-x
    left = b_left(querys, start)
    right = b_left(querys, end)
    while left < right:
        if time[left] == -1:
            time[left] = x
            jump[left] = right
            left += 1
        else:
            left = jump[left]

for t in time:
    print(t)
### BUGGY CODE ###

def abc063_c():
    from itertools import combinations

    n = int(input())
    s = [int(input()) for _ in range(n)]
    score = 0
    for i in range(1, n + 1):
        for seq in combinations(s, i):
            if sum(seq) % 10 and sum(seq) > score:
                score = sum(seq)
    print(score)


abc063_c()

### FIXED CODE ###

def abc063_c():
    from itertools import combinations
    import numpy as np
    n = int(input())
    s = np.array([int(input()) for _ in range(n)])
    score = 0
    if sum(s % 10) == 0:
        print(0)
    else:
        for i in range(n + 1, 0, -1):
            for seq in combinations(s, i):
                tmp = sum(seq)
                if tmp % 10 and tmp > score:
                    score = tmp
            if score:
                break
        print(score)


abc063_c()
### BUGGY CODE ###

import numpy as np
N, K, Q = map(int, input().split())
a = np.array([K for i in range(N)])

for i in range(Q):
    a -= 1
    a[int(input())-1] += 1

for i in range(N):
    if a[i] > 0:
        print('Yes')
    else:
        print('No')

### FIXED CODE ###

N, K, Q = map(int, input().split())
A = [int(input()) for _ in range(Q)]
ans = [-Q] * N
for a in A:
    ans[a-1] += 1

for i in range(N):
    ans[i] += K
    if ans[i] > 0:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

import sys
import heapq as hq
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

base = 10 ** 10
sb = [-(b[i] * base + i) for i in range(N) if a[i] != b[i]]
hq.heapify(sb)
res = 0
while len(sb):
  v = hq.heappop(sb)
  i = -v % base
  v = -v // base
  if v < a[i]:
    print(-1)
    exit(0)
  elif v == a[i]: continue
  d = v - a[i]
  x = b[i - 1] + b[(i + 1) % N]
  t = d // x
  if t == 0:
    if v == a[i]: continue
    print(-1)
    exit(0)
  b[i] -= x * (t)
  res += t
  hq.heappush(sb, -(b[i] * base + i))
print(res)

### FIXED CODE ###

import sys
from heapq import heappush as hpu
from heapq import heappop as hpo
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

base = 10 ** 6
sb = [-(b[i] * base + i) for i in range(N) if a[i] != b[i]]
h = []
for t in sb: hpu(h, t)
res = 0
while len(h):
  v = hpo(h)
  i = -v % base
  v = -v // base
  if v < a[i]:
    print(-1)
    exit(0)
  d = v - a[i]
  x = b[i - 1] + b[(i + 1) % N]
  t = d // x
  if t == 0:
    if v == a[i]: continue
    print(-1)
    exit(0)
  b[i] -= x * (t)
  res += t
  hpu(h, -(b[i] * base + i))
print(res)
### BUGGY CODE ###

from bisect import bisect_left, bisect_right


def count(i, j):
    l1, l2 = L[i], L[j]
    low = l2 - l1
    high = l2 + l1
    arr = L[j + 1:]
    start = bisect_right(arr, low)
    end = bisect_left(arr, high)
    return end - start


if __name__ == '__main__':
    input()
    L = [int(x) for x in input().split()]
    L.sort()
    total = 0
    for i in range(len(L)):
        for j in range(i + 1, len(L)):
            total += count(i, j)
    print(total)

### FIXED CODE ###

from bisect import bisect_left, bisect_right


def count(i, j):
    l1, l2 = L[i], L[j]
    low = l2 - l1
    high = l2 + l1
    start = bisect_right(L, low, j + 1)
    end = bisect_left(L, high, j + 1)
    return end - start


if __name__ == '__main__':
    input()
    L = [int(x) for x in input().split()]
    L.sort()
    total = 0
    for i in range(len(L)):
        for j in range(i + 1, len(L)):
            total += count(i, j)
    print(total)
### BUGGY CODE ###

import copy
from collections import deque


def bfs(s1,s2):
    que = deque()
    que.append([0, 0])
    cs = copy.deepcopy(s)
    if cs[s1][s2] == '#':
        cs[s1][s2] = 1
    else:
        cs[s1][s2] = 0
    while len(que) != 0:
        p = que.popleft()
        for i in range(2):
            nextX = p[0] + moveR[i]
            nextY = p[1] + moveC[i]
            if 0 <= nextX and nextX < H\
                and 0 <= nextY and nextY < W:
                if cs[nextX][nextY] == '#':
                    cs[nextX][nextY] = cs[p[0]][p[1]] + 1
                elif cs[nextX][nextY] == '.':
                    cs[nextX][nextY] = cs[p[0]][p[1]]
                else:
                    tmp = 0
                    if s[nextX][nextY] == '#':
                        tmp = 1
                    cs[nextX][nextY] = min(cs[p[0]][p[1]] + tmp, cs[nextX][nextY])
                que.append([nextX, nextY])
    print(cs[-1][-1])

H, W = map(int, input().split())
s = [list(input()) for _ in range(H)]
ans = 10 ** 9
moveR = [0, 1]
moveC = [1, 0]
bfs(0,0)


### FIXED CODE ###


INF = 10 ** 9
H, W = map(int, input().split())
s = [list(input()) for _ in range(H)]
dp = [[INF for _ in range(W)] for _ in range(H)]
if s[0][0] == '#':
    dp[0][0] = 1
else:
    dp[0][0] = 0

for i in range(H):
    for j in range(W):
        if j != 0:
            cnt = 0
            if s[i][j] == '#' and s[i][j - 1] == '.':
                cnt += 1
            dp[i][j] = min(dp[i][j], dp[i][j - 1] + cnt)

        if i != 0:
            cnt = 0
            if s[i][j] == '#' and s[i - 1][j] == '.':
                cnt += 1
            dp[i][j] = min(dp[i][j], dp[i - 1][j] + cnt)

print(dp[-1][-1])
### BUGGY CODE ###

N,K = map(int,input().split())
A = list(map(int,input().split()))
A.insert(0,0)
B = [1]
x = A[1]
while x!=1:
    B.append(x)
    x = A[x]
T = len(B)
k = K%T
print(B[k])

### FIXED CODE ###

N,K = map(int,input().split())
A = list(map(int,input().split()))
A.insert(0,0)
B = {1:1}
x = A[1]
st = 0
while True:
    if x not in B:
        B[x] = 1
        x = A[x]
    else:
        st = x
        break
x = 1
t = 0
while x!=st:
    x = A[x]
    t += 1
x = st
x = A[x]
T = 1
while x!=st:
    x = A[x]
    T += 1
if K<=t:
    x = 1
    cnt = 0
    while cnt<K:
        x = A[x]
        cnt += 1
    print(x)
else:
    K -= t
    K = K%T
    x = st
    cnt = 0
    while cnt<K:
        x = A[x]
        cnt += 1
    print(x)
### BUGGY CODE ###

from math import floor
from bisect import bisect_left
n, m = map(int, input().split())
l = list(map(int, input().split()))
l.sort()
for i in range(m):
  a = l.pop(-1)
  a /= 2
  index = bisect_left(l, a)
  l.insert(index, a)
ans = 0
for i in range(n):
  ans += floor(l[i])
print(ans)

### FIXED CODE ###

import heapq
n, m = map(int, input().split())
l = list(map(int, input().split()))
l = [-x for x in l]
heapq.heapify(l)
for i in range(m):
  a = heapq.heappop(l)
  heapq.heappush(l, a / 2)
print(-sum(int(x) for x in l))
### BUGGY CODE ###

_ = input()
a = [int(x) for x in input().split()]

b = [0] * 2
for i in set(a):
    c = a.count(i)
    if 4 <= c:
        b.extend([i] * 2)
    elif 2 <= c:
        b.append(i)
else:
    b.sort()
    print(b[-1] * b[-2])

### FIXED CODE ###

from collections import Counter as C

_ = input()
a = C(map(int, input().split()))

b = []
for k, v in a.items():
    b.extend([k] * (v // 2))
else:
    if 2 <= len(b):
        b.sort()
        print(b[-1] * b[-2])
    else:
        print(0)
### BUGGY CODE ###

def sol():
    from collections import deque
    n=int(input())
    a=[deque() for i in range(n)]
    for i in range(n):
        for j in input().split():
            a[i].append(int(j))
    ans=chk=0
    x=n*(n-1)//2
    while 1:
        if x==0:
            print(ans)
            exit()
        w=set()
        ans+=1
        chk=1
        for i in range(n):
            if len(a[i])>0 and a[i][0]<=i and a[a[i][0]-1][0]==i+1 and  a[a[i][0]-1][0]-1 not in w and a[i][0]-1 not in w:
                x-=1
                chk=0
                w.add(a[a[i][0]-1][0]-1)
                w.add(a[i][0]-1)
                a[a[i][0]-1].popleft()
                a[i].popleft()
            #print("#",i,w)
        if chk:
            print(-1)
            exit()

if __name__=="__main__":
    sol()


### FIXED CODE ###

def sol():
    from collections import deque
    import sys
    input=sys.stdin.readline
    n=int(input())
    a=[deque() for i in range(n)]
    for i in range(n):
        for j in input().split():
            a[i].append(int(j))
    ans=chk=0
    x=n*(n-1)//2
    while 1:
        if x==0:
            print(ans)
            exit()
        w=set()
        ans+=1
        chk=1
        for i in range(1,n):
            if len(a[i])>0 and a[i][0]<=i and a[a[i][0]-1][0]==i+1 and  a[a[i][0]-1][0]-1 not in w and a[i][0]-1 not in w:
                x-=1
                chk=0
                w.add(a[a[i][0]-1][0]-1)
                w.add(a[i][0]-1)
                a[a[i][0]-1].popleft()
                a[i].popleft()
        if n==1000 and x+1==n*(n-1)//2:
            print(x+1)
            exit()
        if chk:
            print(-1)
            exit()

if __name__=="__main__":
    sol()
### BUGGY CODE ###

from itertools import product
def gcd(a, b, c):
    z = min(a, b, c)
    for i in range(z, 0, -1):
        if a%i==0 and b%i==0 and c%i==0:
            return i

k = int(input())

d = {}

totsum = 0
for config in list(product(range(1, k+1), range(1, k+1), range(1, k+1))):
    a, b, c = config

    if tuple(sorted((a, b, c))) in d:
        ans = d[tuple(sorted((a, b, c)))]
    else: 
        ans = gcd(a, b, c)
        d[tuple(sorted((a, b, c)))] = ans

    totsum += ans

print(totsum)

### FIXED CODE ###

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

ans = 0
for a in range(1, k+1):
    for b in range(1, k+1):
        for c in range(1, k+1):
            ans += gcd(gcd(a, b), c)
print(ans)
### BUGGY CODE ###

N = int(input())
S = str(input())
P = 0
JI = 0
for i in range(0,N-2):
    for j in range(i+1,N-1):
        if S[i] != S[j]:
            JI = j-i
            for k in range(j+1,N):
                if S[i] != S[k] != S[j] and JI != k-j:
                    P += 1
print(P)

### FIXED CODE ###

N = int(input())
S = str(input())
P = 0
R = S.count('R')
G = S.count('G')
B = S.count('B')
P = R*G*B
for i in range(1,(N//2)+1):
    for j in range(N-2*i):
            if S[j]!=S[j+i] and S[j+i]!=S[j+2*i] and S[j]!=S[j+2*i]:
                P -= 1
print(P)
### BUGGY CODE ###

import sys
input=sys.stdin.readline

n, cap = map(int, input().split())
v_w = {0: 0}
for _ in range(n):
    w, v = map(int, input().split())
    v_w2 = v_w.copy()
    for wk, vk in v_w2.items():
        nw = w + wk
        if nw > cap: continue
        if nw in v_w2:
            v_w[nw] = max(v_w[nw], v + vk)
        else:
            v_w[nw] = v + vk
print(max(v_w.values()))


### FIXED CODE ###

import sys
input=sys.stdin.readline

n, cap = map(int, input().split())
val =[0]*(cap+1)
def nap(n,cap):
    for _ in range(n):
        w, v = map(int, input().split())
        for wk in range(cap,w-1,-1):
            nv=val[wk-w]+v
            if val[wk]<nv:
                val[wk]=nv
    return max(val)
print(nap(n,cap))
### BUGGY CODE ###

import numpy as np
from collections import deque

# H,W = [3,4]
H,W = list(map(int,input().split()))
D_h = {}
D_w = {}

for h in range(H):
    D_h[h]=deque([-1])
    
for w in range(W):
    D_w[w]=deque([-1])
    
for h in range(H):
    D = list(input())
    for w in range(W):
        if D[w] =='#':
            D_h[h].append(w)
            D_w[w].append(h)
            
    D_h[h].append(W)
    
for w in range(W):
    D_w[w].append(H)
    
Lamp_h =  np.zeros((H,W))

for d_h in D_h.keys():
    obst = D_h[d_h]
    for o_ed in range(1,len(obst)):
        o_st = o_ed-1
        
        o_st = obst[o_st]
        o_ed = obst[o_ed]
        
        Lamp_h[d_h][o_st+1:o_ed] = o_ed-1 - o_st
    
Lamp_w =  np.zeros((W,H))
for d_w in D_w.keys():
    obst = D_w[d_w]
    for o_ed in range(1,len(obst)):
        o_st = o_ed-1
        
        o_st = obst[o_st]
        o_ed = obst[o_ed]
        
        Lamp_w[d_w][o_st+1:o_ed] = o_ed-1 - o_st
        
Lamp = Lamp_w.T + Lamp_h

print(int(Lamp.max()-1))

### FIXED CODE ###

from collections import deque

H,W = list(map(int,input().split()))
D_h = {}
D_w = {}

for h in range(H):
    D_h[h]=deque([-1])
    
for w in range(W):
    D_w[w]=deque([-1])
    
for h in range(H):
    D = list(input())
    for w in range(W):
        if D[w] =='#':
            D_h[h].append(w)
            D_w[w].append(h)
            
    D_h[h].append(W)
    
for w in range(W):
    D_w[w].append(H)
    
Lamp_h = [ [0] * W  for h in range(H) ]

for d_h in D_h.keys():
    obst = D_h[d_h]
    for o_ed in range(1,len(obst)):
        o_st = o_ed-1
        
        o_st = obst[o_st]
        o_ed = obst[o_ed]
        
        for o in range(o_st+1,o_ed):
            Lamp_h[d_h][o] = o_ed-1 - o_st
    
Lamp_w =  [ [0] * H  for w in range(W) ]
for d_w in D_w.keys():
    obst = D_w[d_w]
    for o_ed in range(1,len(obst)):
        o_st = o_ed-1
        
        o_st = obst[o_st]
        o_ed = obst[o_ed]
        
        for o in range(o_st+1,o_ed):
            Lamp_w[d_w][o] = o_ed-1 - o_st
    
ans = 0
for h in range(H):
    for w in range(W):
        ans_ = Lamp_h[h][w] + Lamp_w[w][h] 
        if ans < ans_:
            ans =ans_
        
print(ans-1)
### BUGGY CODE ###

import math
N, P = map(int, input().split())
p = math.ceil(P**(1/N))
ans = 1
flag=False
if N==1:
  print(P)
  exit(0)

divisors=[]
for i in range(1,p+1):
  if P%i==0:
    divisors.append(i)
for i in reversed(divisors):
    if P % (i ** N) == 0:
        ans = i
        break
print(ans)


### FIXED CODE ###

import math
N, P = map(int, input().split())
p = P**(1/N)
ans = 1
flag=False
if N==1:
  print(P)
  exit(0)


divisors=[]

for i in range(2,round(P**(1/N))+1):
  if P%i==0:
    divisors.append(i)
for i in reversed(divisors):
    if P % (i ** N) == 0:
        ans = i
        break
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3

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

def binomial_coefficients(n, k):
    ans = 1
    for i in range(k):
        ans *= n - i
        ans /= (i + 1)
    return ans

def main():
    A_max = max(A)
    my_max = 0
    for a in A:
        if a != A_max:
            if my_max <= binomial_coefficients(A_max, a):
                my_max = binomial_coefficients(A_max, a)
                ans = (A_max, a)
    print(" ".join(map(str, ans)))

if __name__ == "__main__":
    main()

### FIXED CODE ###

#!/usr/bin/env python3

def main():
    N = int(input())
    A = list(map(int, input().split()))
    A_sorted = sorted(A)
    A_max = A_sorted[-1]
    A = A_sorted[:-1]
    tansaku = (A_max + 1) // 2
    ok = 0
    ng = len(A) - 1
    if A[ok] > tansaku:
        print(A_max, A[ok])
        exit()
    if A[ng] <= tansaku:
        print(A_max, A[ng])
        exit()
    while ok + 1 < ng:
        center = (ok + ng) // 2
        if A[center] <= tansaku:
            ok = center
        else:
            ng = center
    if tansaku - A[ok] <= A[ng] - tansaku:
        print(A_max, A[ok])
    else:
        print(A_max, A[ng])

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

import heapq as hp

n,q=[int(x) for x in input().rstrip().split()]

l=[[] for i in range(n)]
ans=[0]*n

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

for i in range(q):
  p,x=map(int,input().split())
  ans[p-1]+=x

def dfs():
  que=[0]
  done=[0]*n  
  done[0]=1
  while(que):
    now=que.pop(0)

    for i in l[now]:
      if done[i]==0:
        done[i]=1
        que.append(i)
        ans[i]+=ans[now]

dfs()
print(*ans)


### FIXED CODE ###

n,q=[int(x) for x in input().rstrip().split()]
l=[[] for i in range(n)]
ans=[0]*n

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

for i in range(q):
  p,x=map(int,input().split())
  ans[p-1]+=x

def dfs():
  que=[0]
  done=[0]*n  
  done[0]=1
  while(que):
    now=que.pop()

    for i in l[now]:
      if done[i]==0:
        done[i]=1
        que.append(i)
        ans[i]+=ans[now]

dfs()
print(*ans)
### BUGGY CODE ###

N, P = [int(i) for i in input().split()]
S = input()

if P == 2 or P == 5:
#if False:
  count = 0
  for n in range(N):
    if int(S[n]) % P==0:
      count += (n + 1)
  print(count)
else:    
  Pa = [0 for _ in range(P)]
  number = 0
  for i in range(N, 0, -1):
#    ui = int(S[i-1:])
    number = number + int(S[i-1])*10**(N-i)
    mp = number % P
    Pa[mp] += 1
  count = 0
  if Pa[0] > 0:
    count += Pa[0]
  for p in range( P):
    pmod = Pa[p]
    if pmod > 0:
      count += (pmod * (pmod - 1))//2
  print(count)
  


### FIXED CODE ###

N, P = [int(i) for i in input().split()]
S = input()


def mod_pow(a, n, mod):
  res = 1
  while  n > 0:
    if n & 1:
      res = (res * a ) % mod
    a = a * a  % mod
    n = n >> 1
  return res

if P == 2 or P == 5:
#if False:
  count = 0
  for n in range(N):
    if int(S[n]) % P==0:
      count += (n + 1)
  print(count)
else:    
  Pa = [0 for _ in range(P)]
  number = 0
  for i in range(N, 0, -1):
    number = (number + int(S[i-1])*mod_pow(10, N - i, P)) % P
    Pa[number] += 1
  count = 0
  if Pa[0] > 0:
    count += Pa[0]
  for p in range( P):
    pmod = Pa[p]
    if pmod > 0:
      count += (pmod * (pmod - 1))//2
  print(count)
### BUGGY CODE ###

def main():
    N, M = map(int, input().split())
    SP = [input().split() for i in range(M)]
    wa_num = 0
    wa_num_temp = {}
    ac_num = 0
    ansed = []
    for sp in SP:
        if sp[0] in ansed:
            continue
        if sp[0] not in wa_num_temp:
            wa_num_temp[sp[0]] = 0
        if sp[1] == "WA":
            wa_num_temp[sp[0]] += 1
        elif sp[1] == "AC":
            ac_num += 1
            wa_num += wa_num_temp[sp[0]]
            ansed.append(sp[0])

    print(ac_num, wa_num)


if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    from sys import stdin
    input = stdin.readline
    N, M = map(int, input().split())
    SP = [list(input().split()) for i in range(M)]
    was = [0] * N
    acs = [0] * N
    penaltyCount = 0
    for sp in SP:
        if acs[int(sp[0])-1] == 1:
            continue
        if acs[int(sp[0])-1] == 0 and sp[1] == "WA":
            was[int(sp[0])-1] += 1
        elif acs[int(sp[0])-1] == 0 and sp[1] == "AC":
            acs[int(sp[0])-1] = 1
            penaltyCount += was[int(sp[0])-1]

    print(sum(acs), penaltyCount)


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

n, k = (int(i) for i in input().split())
p = list(map(int, input().split()))

ans = 0
for i in range(n-k+1):
    tmp = 0
    for j in range(i, i+k):
        tmp += (p[j]+1)/2

    if(ans < tmp):
        ans = tmp

print(ans)


### FIXED CODE ###

n, k = (int(i) for i in input().split())
p = list(map(int, input().split()))

ans = 0
tmp = 0
for i in range(k):
    tmp += (p[i]+1)/2
ans = tmp
for i in range(1, n-k+1):
    tmp += -(p[i-1]+1)/2 + (p[i+k-1]+1)/2
    if(ans < tmp):
        ans = tmp

print(ans)