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

import sys
input = sys.stdin.readline
N, M, Q = map(int, input().split())
S = [list(map(int, list(input())[: -1])) for _ in range(N)]
e = [[0] * M for _ in range(N)]
for i in range(N):
  for j in range(M - 1): e[i][j + 1] = e[i][j] + ((S[i][j] == 1) and (S[i][j + 1] == 1))
for i in range(N - 1):
  for j in range(M): e[i + 1][j] += e[i][j]
e = [[0] * M] + e


cs = [[0] * (M + 1) for _ in range(N)]
for i in range(N):
  for j in range(M): cs[i][j + 1] = cs[i][j] + (S[i][j] == 1)
for i in range(N - 1):
  for j in range(M + 1): cs[i + 1][j] += cs[i][j]
cs = [[0] * (M + 1)] + cs
#print(cs)
qs = []
resq = [0] * Q
for i in range(Q):
  u, l, d, r = map(lambda x: int(x) - 1, input().split())
  rese = e[d + 1][r] - e[d + 1][l] - e[u][r] + e[u][l]
  res = cs[d + 1][r + 1] - cs[d + 1][l] - cs[u][r + 1] + cs[u][l]
  qs.append((u, l, d, r))
  resq[i] = res - rese
  #print(res, rese)

T = [[S[i][j] for i in range(N)] for j in range(M)]
N, M = M, N
e = [[0] * M for _ in range(N)]
for i in range(N):
  for j in range(M - 1): e[i][j + 1] = e[i][j] + ((T[i][j] == 1) and (T[i][j + 1] == 1))
for i in range(N - 1):
  for j in range(M): e[i + 1][j] += e[i][j]
e = [[0] * M] + e
for i in range(Q):
  l, u, r, d = qs[i]
  resq[i] -= e[d + 1][r] - e[d + 1][l] - e[u][r] + e[u][l]
  print(resq[i])

### FIXED CODE ###

import sys
input = sys.stdin.readline
N, M, Q = map(int, input().split())
S = [list(map(int, list(input())[: -1])) for _ in range(N)]
e = [[0] * M for _ in range(N + 1)]
for i in range(1, N + 1):
  for j in range(M - 1): e[i][j + 1] = e[i][j] + ((S[i - 1][j] == 1) and (S[i - 1][j + 1] == 1))
for i in range(1, N):
  for j in range(M): e[i + 1][j] += e[i][j]

cs = [[0] * (M + 1) for _ in range(N + 1)]
for i in range(1, N + 1):
  for j in range(M): cs[i][j + 1] = cs[i][j] + (S[i - 1][j] == 1)
for i in range(1, N):
  for j in range(M + 1): cs[i + 1][j] += cs[i][j]

T = [[0] * N for _ in range(M)]
for i in range(N):
  for j in range(M): T[j][i] = S[i][j]

N, M = M, N
ee = [[0] * M for _ in range(N + 1)]
for i in range(1, N + 1):
  for j in range(M - 1): ee[i][j + 1] = ee[i][j] + ((T[i - 1][j] == 1) and (T[i - 1][j + 1] == 1))
for i in range(1, N):
  for j in range(M): ee[i + 1][j] += ee[i][j]


#print(cs)

for i in range(Q):
  u, l, d, r = map(lambda x: int(x) - 1, input().split())
  rese = e[d + 1][r] - e[d + 1][l] - e[u][r] + e[u][l]
  resee = ee[r + 1][d] - ee[r + 1][u] - ee[l][d] + ee[l][u]
  res = cs[d + 1][r + 1] - cs[d + 1][l] - cs[u][r + 1] + cs[u][l]
  print(res - rese - resee)
### BUGGY CODE ###

import copy
n = int(input())
a = list(map(int, input().split()))
a_copy = copy.deepcopy(a)
Sum = 0
a.insert(0, 0)
a.append(0)
s = []
b = []
for i in range(len(a) - 1):
    b.append(abs(a[i] - a[i + 1]))
for i in range(len(b) - 1):
    ans = sum(b) - (b[i] + b[i + 1]) + abs(a[i] - a[i + 2])
    print(ans)


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
Sum = 0
a.insert(0, 0)
a.append(0)
s = []
b = []
for i in range(len(a) - 1):
    b.append(abs(a[i] - a[i + 1]))
Sum_b = sum(b)
for i in range(len(b) - 1):
    ans = Sum_b - (b[i] + b[i + 1]) + abs(a[i] - a[i + 2])
    print(ans)
### BUGGY CODE ###

import sys
import bisect

stdin = sys.stdin
 
ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split()))
rs = lambda: stdin.readline().rstrip()  # ignore trailing spaces

N = ri()
A = [ri() for _ in range(N)]
l = []
for a in A:
    i = bisect.bisect_left(l, a)
    if i == 0:
        l.insert(0, a)
    else:
        l[i-1] = a

print(len(l))
#39


### FIXED CODE ###

import sys
import bisect

stdin = sys.stdin
 
ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split()))
rs = lambda: stdin.readline().rstrip()  # ignore trailing spaces

N = ri()
INF = 10 ** 18
A = [10 ** 10 - ri() for _ in range(N)]
dp = [INF] * (N+1)
for a in A:
    i = bisect.bisect_right(dp, a)
    dp[i] = a

print(bisect.bisect_left(dp, INF))
#39 答え見る
### BUGGY CODE ###

N = int(input())
def shiki(a, b, c):
    return a ** 2 + b ** 2 + c ** 2 + a * b + b * c + c * a

def condition(n):
    count = 0
    i = 0
    j = 0
    z = 1
    while shiki(i, j, z) <= n and n > 5:
        for i in range(1, 100):
            for j in range(1, 100):
                z = 1
                while shiki(i, j, z) <= n and n > 5:
                    if n == shiki(i, j, z):
                        if i == j and j == z and i == z:
                            count += 1
                        else:
                            count += 1
                    z += 1
    print(count)

for i in range(1, N+1):
    condition(i)

### FIXED CODE ###

N = int(input())
ans = [0] * 100000
for x in range(1, 100):
    for y in range(1, 100):
        for z in range(1, 100):
            ans[x*x+y*y+z*z+x*y+y*z+z*x-1] += 1
for i in range(N):
    print(ans[i])
### BUGGY CODE ###


n,m  = list(map(int, input().split()))
ab =[]
cs =[]
for i in range(m):
    ab.append(list(map(int, input().split())))
    cs.append(list(map(int, input().split())))

csbit = []
for i in cs:
    csum = 0
    for j in i:
        csum += 2**(j-1)
    csbit.append(csum)

dp = [float("inf") for _ in range(1 << n)]
dp[0] = 0

for i in range(m):
    for j in range(1 << n):
        dp[j | csbit[i]] = min(dp[j | csbit[i]], dp[j] + ab[i][0])

if dp[-1] == float("inf"):
    print(-1)
else:
    print(dp[-1])

### FIXED CODE ###

n,m  = list(map(int, input().split()))
ab =[]
cs =[]
for i in range(m):
    ab.append(list(map(int, input().split())))
    cs.append(list(map(int, input().split())))

dp = [float("inf") for _ in range(1 << n)]
dp[0] = 0

for i in range(m):
    csbit = 0
    for j in cs[i]:
        csbit += 2**(j-1)
    for j in range(1 << n):
        dp[j | csbit] = min(dp[j | csbit], dp[j] + ab[i][0])

if dp[-1] == float("inf"):
    print(-1)
else:
    print(dp[-1])
### BUGGY CODE ###

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

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

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
mod = 10**9 + 7

ans = 0
count=[0]*60
for a in A:
  for i in range(60):
    count[i] += a & 1
    a >>= 1
    
for i in range(60):
  ans += count[i] * (N - count[i]) * (2 ** i)
  ans %= mod
print(ans)
### BUGGY CODE ###

h,w,d = map(int,input().split())
A = [[int(i) for i in input().split()] for j in range(h)]
q = int(input())
dic = {}


for i in range(h):
    for j in range(w):
        dic[A[i][j]] = (i+1,j+1)

for i in range(q):
    ans = 0
    l,r = map(int,input().split())
    current = l
    current_m = dic[l]
    while current != r:
        current += d
        next_m = dic[current]
        ans += abs(next_m[0]-current_m[0])+abs(next_m[1]-current_m[1])
        current_m = dic[current]
        
    
    print(ans)

### FIXED CODE ###

h,w,d = map(int,input().split())
 
dic = {}
for i in range(h):
    a = input().split()
    for j in range(w):
        dic[int(a[j])] = (i+1,j+1)
        
q = int(input())
c = [0]*(h*w+1)
for i in range(d+1,h*w+1):
    pi,pj = dic[i]; qi,qj = dic[i-d]
    c[i] = c[i-d] + abs(pi-qi) + abs(pj-qj)
    
for i in range(q):
    l,r = map(int,input().split())
    print(c[r]-c[l])
### BUGGY CODE ###

#coding: utf-8
K,S=map(int,input().split(" "))
answer=0
for X in range(K+1):
  for Y in range(K+1):
    for Z in range(K+1):
      if X+Y+Z==S:
        answer+=1
print(answer)

### FIXED CODE ###

#coding: utf-8
K,S=map(int,input().split(" "))
answer=0
for X in range(K+1):
  if S-X>2*K:
    continue
  for Y in range(K+1):
    if S-(X+Y)<=K and S-(X+Y)>=0:
      answer+=1
print(answer)
### BUGGY CODE ###

count = int(input())
numbers = map(int, input().split(' '))

tmp = 0
counter = 0
while True:
  for item in numbers:
    tmp += item % 2
  if tmp > 0:
    break
  counter += 1
  numbers = [item / 2 for item in numbers]
  if numbers.count(0):
    break
print(counter)

### FIXED CODE ###

count = int(input())
numbers = [int(num) for num in input().split()]

counter = 0
while True:
  tmp = 0
  for item in numbers:
    tmp += item % 2
  if tmp > 0:
    break
  counter += 1
  numbers = [item / 2 for item in numbers]
print(counter)
### BUGGY CODE ###

#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():

    def add(i,x):
        while i < len(bit):
            bit[i] += x
            i += i&-i
    def sum_(i):
        res = 0
        while i > 0:
            res += bit[i]
            i -= i&-i
        return res
    n,Q = LI()
    c = LI()
    q = LIR(Q)
    q = [[i,q[i]] for i in range(Q)]
    q.sort(key = lambda x:x[1][1])
    bit = [0]*(n+2)
    i = 0
    p = [None]*(n+1)
    ans = [0]*Q
    for ind,(l, r) in q:
        while i < r:
            ci = c[i]
            j = p[ci]
            if j is not None:
                add(j,-1)
            add(i+1,1)
            p[ci] = i+1
            i += 1
        ans[ind] = sum_(r)-sum_(l-1)
    for i in ans:
        print(i)
    return

#Solve
if __name__ == "__main__":
    solve()


### FIXED CODE ###

#!usr/bin/env python3
import sys
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LIR(n):
    return [LI() for i in range(n)]
class BIT:
    def __init__(self, size):
        self.size = size + 1
        self.dat = [0]*self.size

    def add(self, i, x=1):
        while i < self.size:
            self.dat[i] += x
            i += i&-i

    # sum[l,r)
    # sum[0,l] (r = None)
    def sum(self, l, r=None):
        if r is None:
            res = 0
            while l > 0:
                res += self.dat[l]
                l -= l&-l
            return res

        else:
            rres = 0
            while r > 0:
                rres += self.dat[r]
                r -= r&-r

            l -= 1
            lres = 0
            while l > 0:
                lres += self.dat[l]
                l -= l&-l

            return rres - lres


def solve():
    n,Q = LI()
    c = LI()
    c = [0]+c
    q = LIR(Q)
    q = [[i,q[i]] for i in range(Q)]
    q.sort(key = lambda x:x[1][1])
    bit = BIT(n+1)
    i = 1
    p = [None]*(n+1)
    ans = [0]*Q
    s = 0
    for ind,(l, r) in q:
        l -= 1
        while i <= r:
            ci = c[i]
            j = p[ci]
            if j is not None:
                bit.add(j)
            else:
                s += 1
            p[ci] = i
            i += 1
        ans[ind] = s-l+bit.sum(l)
    for i in ans:
        print(i)
    return

#Solve
if __name__ == "__main__":
    solve()
### BUGGY CODE ###

import sys
input = sys.stdin.readline
def main():
    N = int(input())
    X = [list(map(int,input().split())) for _ in range(N-1)]
    tree = [[] for _ in range(N+1)]
    for i in range(N-1):
        tree[X[i][0]-1].append(X[i][1])
        tree[X[i][1]-1].append(X[i][0])
    dif = [0 for _ in range(N)]
    queue = [1]
    while queue:
        i = queue.pop()
        for j in range (N-1):
            if X[j][0] == i and X[j][1] in tree[i-1]:
                dif[X[j][1]-1] = dif[i-1] + X[j][2]
                tree[X[j][1]-1].remove(i)
            if X[j][1] == i and X[j][0] in tree[i-1]:
                dif[X[j][0]-1] = dif[i-1] - X[j][2]
                tree[X[j][0]-1].remove(i)
        queue += tree[i-1]
        tree[i-1].clear()

    for i in dif:
        print(0) if i%2 == 0 else print(1)

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline
from collections import deque

def main():
    N = int(input())
    dist = [[] for _ in range(N)]
    for i in range(N-1):
        u,v,w = map(int,input().split())
        dist[u-1].append((v-1,w%2))
        dist[v-1].append((u-1,w%2))

    go = [True for _ in range(N)]
    length = [0 for _ in range(N)]
    go[0] = False
    q = deque([0])
    while q:
        now = q.pop()
        for fol,d in dist[now]:
            if go[fol]:
                length[fol] = length[now]+d
                go[fol] = False
                q.append(fol)

    for i in length:
        print(i%2)
        
if __name__ == "__main__":
    main()
### BUGGY CODE ###

k, s = [int(x) for x in input().split()]
cnt = 0
for x in range(k + 1):
    for y in range(k + 1):
        for z in range(k + 1):
            if x + y + z == s:
                cnt += 1
print(cnt)


### FIXED CODE ###

k, s = [int(x) for x in input().split()]
cnt = 0
for x in range(k + 1):
    if x > s:
        continue
    for y in range(x, k + 1):
        if y > s:
            break
        z = s - x - y
        if y <= z and z <= k:
            if x + y + z == s:
                if x == y == z:
                    cnt += 1
                elif x == y or y == z:
                    cnt += 3
                else:
                    cnt += 6
print(cnt)
### BUGGY CODE ###

n,q=map(int,input().split())
s=list(str(input()))
lr=[]
for i in range(q):
    lr.append(list(map(int,input().split())))
sl=[]
for i in range(n-1):
    if s[i]=="A" and s[i+1]=="C":
        sl.append([i+1,i+2])
    else:
        pass

for i in range(q):
    ctr1=1
    ctr2=0
    for k in range(len(sl)):
        if lr[i][0] > sl[k][0]:
            ctr1+=1
        if lr[i][1] >= sl[k][1]:
            ctr2+=1
        else:
            break
    print(ctr2-ctr1+1)

### FIXED CODE ###

n,q=map(int,input().split())
s=list(str(input()))
lr=[]
for i in range(q):
    lr.append(list(map(int,input().split())))
ctr1=0
t_list=[0]
for i in range(n-1):
    if s[i]=="A" and s[i+1]=="C":
        ctr1+=1
        t_list.append(ctr1)
    else:
        t_list.append(ctr1)

for i in range(q):
    left=lr[i][0]
    right=lr[i][1]
    print(t_list[right-1]-t_list[left-1])
### BUGGY CODE ###

N,K = map(int,input().split())
A = list(map(int,input().split()))
S = []
for i in range(K):
    n = 0
    for j in A:
        n+=1
        if j in S:
            S = S[:S.index(j)]
        else:
            S.append(j)
    if S == []:
        break
K = K%(i+1)
for i in range(K):
    n = 0
    for j in A:
        n+=1
        if j in S:
            S = S[:S.index(j)]
        else:
            S.append(j)
for i in S:
    print(i,end = " ")
print()

### FIXED CODE ###

N,K = map(int,input().split())
A = list(map(int,input().split()))
hoge = [[]for i in range(200001)]
for i in range(N):
    hoge[A[i]].append(i)
NEXT = [-1]*N
for i in hoge:
    for j in range(-len(i),0):
        NEXT[i[j]] = i[j+1]
i = 1
p = 0
while i < K:
    #print(i,p)
    if NEXT[p] <= p:
        i += 1
    if NEXT[p] == N-1:
        i += 1
    p = (NEXT[p]+1)%N
    if p == 0:
        i = (K//(i-1))*(i-1)+1
while p < N:
    if NEXT[p] <= p:
        print(A[p],end = " ")
        p += 1
    else:
        p = NEXT[p]+1
print()
### BUGGY CODE ###

import sys
import numpy as np
from numba import njit
 
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

def update(A):
  N = len(A)
  B = np.zeros_like(A)
  for i,x in enumerate(A):
    l = max(0, i-x)
    r = min(N-1, i+x)
    B[l] += 1
    if r + 1 < N:
      B[r+1] -= 1
  B = np.cumsum(B)
  return B
    
    
N,K = map(int, readline().split())
A = np.array(read().split(), np.int64)
 
K = min(K, 100)
for _ in range(K):
  A = update(A)
print(' '.join(A.astype(str)))

### FIXED CODE ###

import sys
import numpy as np
from numba import njit
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
@njit('(i8[::1],)', cache=True)
def update(A):
    N = len(A)
    B = np.zeros_like(A)
    for i, x in enumerate(A):
        l = max(0, i - x)
        r = min(N - 1, i + x)
        B[l] += 1
        if r + 1 < N:
            B[r + 1] -= 1
    B = np.cumsum(B)
    return B
 
N, K = map(int, readline().split())
A = np.array(read().split(), np.int64)
 
K = min(K, 100)
for _ in range(K):
    A = update(A)
print(' '.join(A.astype(str)))
### BUGGY CODE ###

N, K = map(int, input().split())
h = [int(x) for x in input().split()]

INF = float('inf')
dp = [INF for _ in range(N+K+10)]

# initial state
dp[0] = 0

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

print(dp[N-1])

### FIXED CODE ###

N, K = map(int, input().split())
h = [int(x) for x in input().split()]

INF = float('inf')
dp = [INF for _ in range(N+K+10)]

# initial state
dp[0] = 0

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

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

from collections import Counter
from collections import defaultdict
N, K = map(int, input().split())
A = list(map(int, input().split()))
B = Counter(A).most_common()
dict = []
for l in B:
    dict.append([l[0], l[1]])
dict.sort(key=lambda x:x[1])
count = 0
l = len(B)
if l <= K:
    print(0)
else:
    while l != K:
        count += dict[0][1]
        del dict[0]
        dict.sort(key=lambda x:x[1])
        l = len(dict)
        if l == K:
            break
    print(count)


### FIXED CODE ###

from collections import Counter
N, K = map(int, input().split())
A = list(map(int, input().split()))

ca = Counter(A)
ca = sorted(ca.items(), key=lambda x:x[1], reverse=True)

ans = 0
for i in range(min(K, len(ca))):
    ans += ca[i][1]

print(N-ans)
### BUGGY CODE ###

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

# dp[i][s] : Rをiに固定した時に、和がsとなる整数列の組が何回現れるか
dp = [[0]*(S+1) for i in range(N+1)]
ans = 0

for i, a in enumerate(A, 1):
  for s in range(S+1):
    dp[i][s] = dp[i-1][s]
    dp[i][s] += s==0 or s==a
    if s >= a:
      dp[i][s] = (dp[i][s] + dp[i-1][s-a]) % MOD
  ans = (ans + dp[i][-1]) % MOD # R=i, L=1,2,...i(=R)のf(L, R)を加算

print(ans)

### FIXED CODE ###

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

# dp[i][s] : Rをiに固定した時に、和がsとなる整数列の組が何回現れるか
dp = [[0]*(S+1) for i in range(N+1)]
ans = 0

for i, a in enumerate(A, 1):
  for s in range(S+1):
    dp[i][s] = dp[i-1][s]
    dp[i][s] += s==0 or s==a
    if s >= a:
      dp[i][s] = (dp[i][s] + dp[i-1][s-a]) % MOD
  ans = (ans + dp[i][-1]) % MOD

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

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

ans = 1
for i in a:
    ans *= i
    
if ans > pow(10, 18):
    ans = -1
        

print(ans)

### FIXED CODE ###

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

ans = 1
for i in a:
    if i == 0:
        print(0)
        exit()

for i in a:
    ans *= i
    if ans > pow(10, 18):
        ans = -1
        break


        

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

n=int(input())
x=[]
cnt=0
for i in range(n):
  a=sorted(input())
  x.append(a)
  cnt+=x.count(a)-1
print(cnt)

### FIXED CODE ###

n=int(input())
x={}
cnt=0
for i in range(n):
  a=''.join(sorted(input()))
  if a in x:x[a]+=1
  else:x[a]=1

for a in x:
  cnt+=x[a]*(x[a]-1)//2
print(cnt)
### BUGGY CODE ###

#標準入力からソートまで
N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
#Aの中で一番でかいのをdiscountしてまた並び替え
import bisect
for i in range(M):
    tmp = A.pop(N-1) // 2
    bisect.insort_left(A, tmp)
print(sum(A))

### FIXED CODE ###

#標準入力からソートまで
N, M = map(int, input().split())
A = list(map(lambda x : int(x) * (-1), input().split()))
#Aの中で一番でかいのをdiscountしてまた並び替え
#優先度付きqueuemを使う
import heapq
heapq.heapify(A)
for i in range(M):
    tmp = (-1) * heapq.heappop(A) // 2
    heapq.heappush(A, tmp * (-1))
print(-sum(A))
### BUGGY CODE ###

num = int(input())
list = []
min = 0
for i in range(1,num+1):
    p = num/i
    if p.is_integer() == True:
        if list.count(i) == 0 and list.count(int(p)) == 0:
            list.append(i)
            list.append(int(p))
        else:
          break
    

l = len(list)
list.sort()
if l%2 == 1:
    min = list[int((l/2))]*2-2
else:
    min = list[int(l/2)-1]+list[int(l/2)]-2
print(min)

### FIXED CODE ###

n = int(input())
ans = n-1
d = 1
while d*d <= n:
    if n%d == 0:
        e = n//d
        ans = min(ans,d-1+e-1)
    d+=1
print(ans)
### BUGGY CODE ###

from itertools import accumulate
from collections import defaultdict

def cmb_2(n):
    return n*(n-1)//2

N,K = map(int, input().split(' '))
A = list(map(int, input().split(' ')))
A = [i-1 for i in A]
sumA = list(accumulate(A))
sumA = [0]+[i % K for i in sumA]
x = sumA[:K]
modmap = defaultdict(int)
ans = 0
for i in x:
    modmap[i] += 1

for i in range(K):
    ans += cmb_2(modmap[i])

for i in range(N-K+1):
    modmap[sumA[K+i]] += 1
    modmap[sumA[i]] -= 1
    ans += modmap[sumA[K+i]]-1

print(ans)

### FIXED CODE ###

import sys
from itertools import accumulate
from collections import defaultdict
input = sys.stdin.readline
n,k = map(int,input().split())
a = list(map(int,input().split()))
a = [i-1 for i in a]
suma = [0]+list(accumulate(a))
suma = [i%k for i in suma]
rem = defaultdict(int)
ans = 0
if k > n:
    for i in range(n+1):
        x = suma[i]
        rem[x] += 1
    for s in rem.values():
        ans += s*(s-1)//2
    print(ans)
    exit()
for i in range(k):
    x = suma[i]
    rem[x] += 1
for s in rem.values():
    ans += s*(s-1)//2
for i in range(n-k+1):
    rem[suma[i]%k] -= 1
    rem[suma[i+k]%k] += 1
    ans += rem[suma[i+k]] -1
print(ans)
### BUGGY CODE ###

n=int(input())
p,q=1,1

for _ in range(n):
    t,a=map(int,input().split())
    n=1
    while p>n*t or q>n*a:
        n+=1
    p,q=n*t,n*a

print(p+q)

### FIXED CODE ###

n=int(input())
p,q=1,1

for _ in range(n):
    t,a=map(int,input().split())
    #n=1
    #hile p>n*t or q>n*a:
    #    n+=1
    n=max((p+t-1)//t,(q+a-1)//a)
    p,q=n*t,n*a
    #print(n,p,q)

print(p+q)
### BUGGY CODE ###

n,c=map(int, input().split())
x=[]
v=[]

for _ in range(n):
    xi,vi=map(int, input().split())
    x.append(xi)
    v.append(vi)
xr=list((map(lambda _: c-_, x[::-1])))
x.insert(0,0)
xr.insert(0,0)

score=[0] 
score_r=[0]

tmp=0
for i, vi in enumerate(v):
    tmp+=vi
    score.append(tmp-x[i+1])

tmp=0
for i, vi in enumerate(v[::-1]):
    tmp+=vi
    score_r.append(tmp-xr[i+1])

maxscore=0
for i, si in enumerate(score):
    tmp=si-x[i]+max(score_r[:n-i+1])
    maxscore=max(tmp,maxscore)
for i, si in enumerate(score_r):
    tmp=si-xr[i]+max(score[:n-i+1])
    maxscore=max(tmp,maxscore)
print(maxscore)            
        




### FIXED CODE ###

n,c=map(int, input().split())
x=[]
xr=[]
v=[]

for _ in range(n):
    xi,vi=map(int, input().split())
    x.append(xi)
    xr.append(c-xi)
    v.append(vi)
xr.reverse()
x.insert(0,0)
xr.insert(0,0)

score=[0]
score_r=[0]

tmp=0
for i, vi in enumerate(v):
    tmp+=vi
    score.append(tmp-x[i+1])
tmp=0
for i, vi in enumerate(v[::-1]):
    tmp+=vi
    score_r.append(tmp-xr[i+1])

maxscore=[0]
maxscore_r=[0]

tmp=0
for si in score:
    maxscore.append(max(si,tmp))
    tmp=max(si,tmp)
tmp=0
for si in score_r:
    maxscore_r.append(max(si,tmp))
    tmp=max(si,tmp)

ans=0
for i, si in enumerate(score):
    tmp=si-x[i]+maxscore_r[n-i+1]
    ans=max(tmp,ans)
for i, si in enumerate(score_r):
    tmp=si-xr[i]+maxscore[n-i+1]
    ans=max(tmp,ans)
print(ans)
### BUGGY CODE ###

N, P=map(int,input().split())
S = list(map(int,list(input())))
def ma25():
  ret = 0
  for i in range(N):
    if S[i]%P == 0:
      ret+=(i+1)
  print(ret)

def ma():
  dp = [0]*P
  ret = 0
  for i in range(N):
    dp_ = [0]*P
    b = S[i]%P
    for j in range(P):
      dp_[(j*10+b)%P] += dp[j]
    dp_[b] += 1
    ret += dp_[0]
    dp = dp_[:]
  print(ret)    
if P == 2 or P == 5:
  ma25()
else:
  ma()

### FIXED CODE ###

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

def ma25():
  ret = 0
  for i in range(N):
    if S[i]%P == 0:
      ret+=(i+1)
  print(ret)

def ma():
  dp = [0]*P
  dp[0] = 1
  r = 0
  for i in range(N-1,-1,-1):
    r = ((S[i]*pow(10,N-1-i,P))+r)%P
    dp[r] += 1
  ret = 0
  for m in dp:
    ret += m*(m-1)//2
  print(ret)

if P == 2 or P == 5:
  ma25()
else:
  ma()