Buggy python submission (verdict: Time Limit Exceeded):
from itertools import accumulate
from collections import defaultdict
import sys
input=sys.stdin.readline
N,K = map(int, input().split(' '))
A = list(map(int, input().split(' ')))
A = [0]+[i-1 for i in A]
sumA = list(accumulate(A))
sumA = [i % K for i in sumA]
x = sumA[:K]
modmap = defaultdict(int)
ans = 0
if K==1:
  print(0)
  exit()
for i in x:
    modmap[i] += 1

for i in range(K):
    t = modmap[i]
    ans += t * (t-1) // 2

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 submission:
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 python submission (verdict: Time Limit Exceeded):
from itertools import accumulate
from collections import defaultdict
import sys

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

N,K = map(int, input().split(' '))
A = list(map(int, input().split(' ')))
A = [0]+[i-1 for i in A]
sumA = list(accumulate(A))
sumA = [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):
    t = modmap[i]
    ans += t * (t-1) // 2

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 submission:
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 python submission (verdict: Time Limit Exceeded):
from itertools import accumulate
from collections import defaultdict
import sys

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

N,K = map(int, input().split(' '))
A = list(map(int, input().split(' ')))
A = [0]+[i-1 for i in A]
sumA = list(accumulate(A))
sumA = [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):
    t = modmap[i]
    ans += t * (t-1) // 2

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 submission:
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 python submission (verdict: Runtime Error):
from itertools import accumulate
from collections import defaultdict

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

for i in range(K):
    t = modmap[i]
    ans += t * (t-1) // 2

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 submission:
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 python submission (verdict: Runtime Error):
from itertools import accumulate
from collections import defaultdict

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

for i in range(K):
    t = modmap[i]
    ans += t * (t-1) // 2

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 submission:
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 python submission (verdict: Time Limit Exceeded):
from itertools import accumulate
from collections import defaultdict

N,K = map(int, input().split(' '))
A = list(map(int, input().split(' ')))
A = [0]+[i-1 for i in A]
sumA = list(accumulate(A))
sumA = [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):
    t = modmap[i]
    ans += t * (t-1) // 2

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 submission:
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 python submission (verdict: Time Limit Exceeded):
from itertools import accumulate
from collections import defaultdict

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):
    t = modmap[i]
    ans += t * (t-1) // 2

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 submission:
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 python submission (verdict: Time Limit Exceeded):
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 submission:
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 python submission (verdict: Time Limit Exceeded):
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 submission:
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 python submission (verdict: Runtime Error):
from itertools import accumulate
from math import factorial as fc

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 = [0]*K
for i in x:
    modmap[i] += 1

ans = 0
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 submission:
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 python submission (verdict: Runtime Error):
from itertools import accumulate
from math import factorial as fc

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 = [0]*K
for i in x:
    modmap[i] += 1

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

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 submission:
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 python submission (verdict: Runtime Error):
from itertools import accumulate
from math import factorial as fc

def cmb(n,r):
    if n < 0 or r < 0 or n-r < 0:
        return 0
    return fc(n)//(fc(n-r)*fc(r))

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 = [0]*K
for i in x:
    modmap[i] += 1

ans = 0
for i in range(K):
    ans += cmb(modmap[i],2)

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 submission:
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 python submission (verdict: Time Limit Exceeded):
N, K = map(int, input().split(' '))
A = list(map(int, input().split(' ')))

sumA = [0]

for i in range(N):
    if i == 0:
        sumA.append(A[i] % K)
    else:
        sumA.append((sumA[-1] + A[i]) % K)
ans = 0

for i in range(N):
    for j in range(i+1, N+1):
        if (sumA[j] - sumA[i]) % K == j - i:
            ans += 1
#            print(sumA[j],sumA[i])

print(ans)

Fixed submission:
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 python submission (verdict: Time Limit Exceeded):
N, K = map(int, input().split(' '))
A = list(map(int, input().split(' ')))

sumA = [0]

for i in range(N):
    if i == 0:
        sumA.append(A[i])
    else:
        sumA.append(sumA[-1] + A[i])
ans = 0

for i in range(N):
    for j in range(i+1, N+1):
        if (sumA[j] - sumA[i]) % K == j - i:
            ans += 1
#            print(sumA[j],sumA[i])

print(ans)


Fixed submission:
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)