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

N,K=map(int,input().split())
A=list(map(int,input().split()))
point=[1]*N
for i in range(K-1,N):
  for j in range(K):
    point[i]*=A[i-j]
for i in range(K-1,N-1):
  if(point[i]>=point[i+1]):
    print("No")
  else:
    print("Yes")

### FIXED CODE ###

N,K=map(int,input().split())
A=list(map(int,input().split()))
point=[1]*N
for i in range(N-K):
  if(A[K+i]>A[i]):
    print("Yes")
  else:
    print("No")
### BUGGY CODE ###

s = input()
len_s = len(s)
pre,now = 0,0
mod = [0]*2019
mod[0]=1
for i in range(len_s):
    now = (10**i*int(s[len_s-i-1])+pre)%2019
    mod[now] += 1
    pre = now
sum_mod = 0
for m in mod:
    sum_mod += m*(m-1)//2
print(sum_mod)

### FIXED CODE ###

s = input()
len_s = len(s)
pre = 0
mod = [0]*2019
mod[0]=1
x = 1
for i in range(len_s):
    pre = (x*int(s[len_s-i-1])+pre)%2019
    mod[pre] += 1
    x *= 10
    x %= 2019
print(sum([m*(m-1)//2 for m in mod]))
### BUGGY CODE ###

N,M = map(int,input().split())
A = sorted([int(input()) for _ in range(M)])
dp = [0]*(N+1)
dp[0] = 1
for i in range(1,N+1):
    dp[i] = (dp[i-1] + dp[i-2])%(1000000007)
    if i in A:dp[i] = 0
    
print(dp[N])

### FIXED CODE ###

n,m=map(int,input().split())
a=set([int(input()) for i in range(m)])
dp=[0]*(n+1)
dp[0]=1
for i in range(1,n+1):
    dp[i]=(dp[i-1]+dp[i-2])%(10**9+7)
    if i in a:dp[i]=0
print(dp[n])
### BUGGY CODE ###

def main():
    import numpy as np
    n = int(input())
    a = list(map(int, input().split()))
    l1 = np.zeros(61, dtype=np.int64)
    mod = 10**9+7
    for i in a:
        j = list(map(int, reversed(bin(i)[2:])))
        l1[:len(j)] += j
    l0 = n-l1
    ans = 0
    for i in range(len(l1)):
        ans = (ans+l0[i]*l1[i]*pow(2, i, mod)) % mod
    print(ans)


main()

### FIXED CODE ###

def main():
    n=int(input())
    a=list(map(int,input().split()))
    l1=[0]*61
    for i in a:
        j=list(reversed(bin(i)[2:]))
        for k in range(len(j)):
            if j[k]=="1":
                l1[k]+=1
    l0=[n-i for i in l1]
    ans=0
    mod=10**9+7
    for i in range(len(l1)):
        ans=(ans+l0[i]*l1[i]*pow(2,i,mod))%mod
    print(ans)
main()
### BUGGY CODE ###

import collections

s = raw_input()
q = 0
n = len(s)
while(True):
	s = s.replace('01','')
	s = s.replace('10','')
	if len(s)  == n:
		break
	else:
		q += n - len(s)

print q

### FIXED CODE ###

import collections

s = raw_input()
stack = collections.deque([])
i = 0
j = 0
while(j < len(s)):
	while(j < len(s) and s[i] == s[j]): j += 1	
	stack.append(j-i)
	i = j
n = len(s)
while(len(stack) > 1) :
	v = stack.pop()
	u = stack.pop()
	if v > u: 
		if stack:
			stack[-1] += v-u
		else:
			stack.append(v-u)
	elif v < u: stack.append( u - v)

print n - (stack[-1] if stack else 0)
### BUGGY CODE ###

N, M = map(int, input().split())
S = list(map(int, input().split()))
S.append(-1)
T = list(map(int, input().split()))
T.append(0)
mod = 10 ** 9 + 7
dp0 = [[0] * 2005 for _ in range(2005)]
dp1 = [[0] * 2005 for _ in range(2005)]
dp0[0][0] = 1
for i in range(N + 1):
    for j in range(M + 1):
        dp0[i + 1][j] += dp0[i][j]
        dp1[i][j] += dp0[i][j]
        dp1[i][j + 1] += dp1[i][j]
        if S[i] == T[j]:
            dp0[i + 1][j + 1] += dp1[i][j]
ans = dp1[N][M] % mod
print(ans)

### FIXED CODE ###

N, M = map(int, input().split())
S = list(map(int, input().split()))
S.append(-1)
T = list(map(int, input().split()))
T.append(0)
mod = 10 ** 9 + 7
dp0 = [[0] * 2005 for _ in range(2005)]
dp1 = [[0] * 2005 for _ in range(2005)]
dp0[0][0] = 1
for i in range(N + 1):
    for j in range(M + 1):
        dp0[i + 1][j] += dp0[i][j] % mod
        dp1[i][j] += dp0[i][j] % mod
        dp1[i][j + 1] += dp1[i][j] % mod
        if S[i] == T[j]:
            dp0[i + 1][j + 1] += dp1[i][j] % mod
ans = dp1[N][M] % mod
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3
#ABC128 E

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n,q = LI()
stx = [LI() for _ in range(n)]
d = [I() for _ in range(q)]
stx.sort(key = lambda x:(x[2],x[0]))
ans = [-1]*q
for s,t,x in stx:
    l = bl(d,s-x)
    r = bl(d,t-x)
    for i in range(l,r):
        if ans[i] < 0:
            ans[i] = x
print(*ans)



### FIXED CODE ###

#!/usr/bin/env python3
#ABC128 E

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n,q = LI()
stx = [LI() for _ in range(n)]
stx.sort(key = itemgetter(2))
d = [I() for _ in range(q)]
ans = [-1]*(q+1)
right = [0]*q
for s,t,x in stx:
    l,r = bl(d,s-x),bl(d,t-x)
    #l≦d<rを満たすdがxでぶつかる
    #各dにおいて一番最初にぶつかるxを求めたい
    while l < r:
        while ans[l] != -1:
            l = right[l]
        if r <= l:
            break
        ans[l] = x
        right[l] = r
        l += 1
for i in ans[:-1]:
    print(i)
### BUGGY CODE ###


N,M=[int(x) for x in input().rstrip().split()]
A=[int(x) for x in input().rstrip().split()]
A.sort()
l=[0 for i in range(N)]
l1=[]
B=[[int(x) for x in input().rstrip().split() ]for i in range(M)]


for i in range(len(B)):
    A.sort()
    for j in range(B[i][0]):
        if A[j]<B[i][1]:
            A[j]=B[i][1]
print(sum(A))



#l.sort(reverse=True)
#A=A+l[:N]
#A.sort(reverse=True)



    




### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
from bisect import bisect_left
 
 
n, m = map(int, input().split())
a = list( map(int, input().split()))
a.sort()
 
bc = [tuple(map(int,input().split())) for i in range(m)]
bc = sorted(bc, reverse=True, key=lambda x: x[1])
 
i = 0
d = []
for b, c in bc:
    d.extend([c]*b)
    if len(d) >= n:
        break
 
a=a+d
a.sort(reverse=True)
print(sum(a[:n]))

#l.sort(reverse=True)
#A=A+l[:N]
#A.sort(reverse=True)
### BUGGY CODE ###

#ABC 127 C - Prison
from collections import Counter

n, m = map(int, input().split())
gates = []
for i in range(m):
    l, r = map(int, input().split())
    for j in range(l-1, r):
        gates.append(j)

c = Counter(gates)
res = 0
for v in c.values():
    if v == m: res += 1
print(res)

### FIXED CODE ###

n, m = map(int, input().split())
L, R = [], []
for _ in range(m):
    l,r = map(int, input().split())
    L.append(l)
    R.append(r)


res = min(R) - max(L) + 1
if res < 0:
    print(0)
else:
    print(res)
### BUGGY CODE ###

s=list(input())
t=0
while t<len(s):
    if s[t]=='d':
        if t>len(s)-5:
            print('NO')
            exit()
        if s[t+1]=='r' and s[t+2]=='e' and s[t+3]=='a' and s[t+4]=='m':
            t+=5
            if t==len(s):
                print('YES')
                exit()
            elif t>len(s)-2:
                print('NO')
                exit()
            if s[t]=='e' and s[t+1]=='r':
                if t==len(s)-2:
                    print('YES')
                    exit()
                elif s[t+2]!='a':
                    t+=2
    elif s[t]=='e':
        if t>len(s)-5:
            print('NO')
            exit()
        if s[t+1]=='r' and s[t+2]=='a' and s[t+3]=='s' and s[t+4]=='e':
            t+=5
            if t==len(s):
                print('YES')
                exit()
            elif t>len(s)-1:
                print('NO')
                exit()
            if s[t]=='r':
                if t==len(s)-1:
                    print('YES')
                    exit()
                elif s[t+1]!='a':
                    t+=1
    else:
        print('NO')
        exit()
print('NO')

### FIXED CODE ###

s=list(input())
n=len(s)
t=n-1
while t>=0:
    if s[t]=='r':
        if t<5:
            print('NO')
            exit()
        elif s[t-1]=='e' and s[t-2]=='s' and s[t-3]=='a' and s[t-4]=='r' and s[t-5]=='e':
            t-=6
        elif t<6:
            print('NO')
            exit()
        elif s[t-1]=='e' and s[t-2]=='m' and s[t-3]=='a' and s[t-4]=='e' and s[t-5]=='r' and s[t-6]=='d':
            t-=7
        else:
            print('NO')
            exit()
    elif s[t]=='e':
        if t<4:
            print('NO')
            exit()
        elif s[t-1]=='s' and s[t-2]=='a' and s[t-3]=='r' and s[t-4]=='e':
            t-=5
        else:
            print('NO')
            exit()
    elif s[t]=='m':
        if t<4:
            print('NO')
            exit()
        elif s[t-1]=='a' and s[t-2]=='e' and s[t-3]=='r' and s[t-4]=='d':
            t-=5
        else:
            print('NO')
            exit()
    else:
        print('NO')
        exit()
print('YES')
### BUGGY CODE ###

import sys
inputs = sys.stdin.readline
N, Q= map(int,inputs().split())
V = [list(map(int,inputs().split())) for p in [0]*N]

mini = 1000000001
count = 0
for q in [None]*Q:
	m = int(inputs())
	num = mini
	for v in V:
		if v[0]-v[2]<=m and m <= v[1]-v[2]-1:
			num = min(v[2],num)
	if num == mini:
		print(-1)
	else:
		print(num)

### FIXED CODE ###

import sys
from operator import itemgetter
def main():
	inputs = sys.stdin.readline
	N, Q= map(int,inputs().split())
	E = [None]*2*N
	for n in range(N):
		a,b,c = map(int,inputs().split())
		E[2*n] = (a - c, 1, c)
		E[2*n + 1] = (b - c, -1, c)
	E.sort(key=itemgetter(0))
	tuple(tuple(E))
	mini = 1000000001
	kouho = {1000000001}
	my_add = kouho.add
	my_discard = kouho.discard
	q = 0
	d = int(inputs())
	flag = False
	cont = False
	for e in E:
		while e[0] > d:
			if cont == True:
				print(mini-(mini//1000000001)*1000000002)
			else:
				mini = min(kouho)
				print(mini-(mini//1000000001)*1000000002)
			cont = True
			q = q + 1
			if q > Q-1:
				flag = True
				break
			d = int(inputs())
		if flag == True:
			break
		if e[1] == 1:
			my_add(e[2])
			if mini > e[2]:
				mini = e[2]
		elif e[1] == -1:
			my_discard(e[2])
			if mini == e[2]:
				cont = False
	for t in [None]*(Q-q):
		print(-1)
main()
### BUGGY CODE ###

import numpy as np

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

def is_cuttable(N):
    n = 0
    for a in A:
        i = np.ceil(a / N)
        n += int(i) - 1
        if n > K:
            return False
    return True

n_max = 10 ** 10
n_min = 0

while n_max - n_min > 1:
    n = (n_max + n_min) // 2
    if is_cuttable(n):
        n_max = n
    else:
        n_min = n
    
print(n_max)

### FIXED CODE ###

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

def is_cuttable(N):
    n = 0
    for a in A:
        i = a // N
        if a % N == 0:
            i -= 1
        n += int(i)
        if n > K:
            return False
    return True

n_max = 10 ** 10
n_min = 0

while n_max - n_min > 1:
    n = (n_max + n_min) // 2
    if is_cuttable(n):
        n_max = n
    else:
        n_min = n
    
print(n_max)
### BUGGY CODE ###

def main():
    n,k = map(int,input().split())
    A = list(map(int,input().split()))

    dp = [[0]*n for _ in range(k+1)]
    for i in range(n):
        dp[0][i] = A[i]

    for i in range(1,k+1):
        fin = 0
        for j in range(n):
            pwr = dp[i-1][j]
            if pwr >= max(j,n-1-j) :
                fin+=1
                continue
            for a in range(max(j-pwr,0),min(j+pwr+1,n)):
                dp[i][a]+=1

        if fin == n:
            break
        else:
            for j in range(n):
                dp[i][j] += fin
    
    if fin == n:
        for j in range(n-1):
            print(n, end=" ")  
        print(n)

    else:
        for j in range(n-1):
            print(dp[i][j], end=" ")
        print(dp[i][n-1])
main()

### FIXED CODE ###

def main():
    n,k = map(int,input().split())
    A = list(map(int,input().split()))
    k = min(50,k)

    dp = [[0]*n for _ in range(k+1)]
    for i in range(n):
        dp[0][i] = A[i]

    flag = False
    for i in range(1,k+1):
        pos = [0]*n
        neg = [0]*n

        for j in range(n):
            pwr = dp[i-1][j]
            pos[max(0,j-pwr)]+=1
            neg[min(n-1,j+pwr)]+=1

        ac_pos = 0
        ac_neg = 0
        for j in range(n):
            ac_pos += pos[j]
            ac_neg += neg[j]
            pos[j] = ac_pos
            neg[j] = ac_neg

        if pos[0]==n and neg[n-2]==0:
            flag = True
            break

        dp[i][0] = pos[0]
        for j in range(1,n):
            dp[i][j] = pos[j] - neg[j-1]

    
    if flag:
        for j in range(n-1):
            print(n, end=" ")  
        print(n)

    else:
        for j in range(n-1):
            print(dp[i][j], end=" ")
        print(dp[i][n-1])
main()
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)
N, Q = map(int, input().split())
to = [[] for _ in range(N)]
ans = [0] * N
def dfs(v, p=-1):
    for u in to[v]:
        if u == p:
            continue
        ans[u] += ans[v]
        dfs(u, v)
for _ in range(N-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    to[a].append(b)
    to[b].append(a)
for _ in range(Q):
    p, x = map(int, input().split())
    p -= 1
    ans[p] += x
dfs(0)
print(*ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
N, Q = map(int, input().split())
to = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    to[a].append(b)
    to[b].append(a)

count = [0] * N
for _ in range(Q):
    p, x = map(int, input().split())
    p -= 1
    count[p] += x

stack = [0]
visited = [0] * N
while stack:
    v = stack.pop()
    visited[v] = 1
    for next_v in to[v]:
        if visited[next_v] == 1:
            continue
        count[next_v] += count[v]
        stack.append(next_v)
print(*count)
### BUGGY CODE ###

n, a, b = map(int, input().split())
h = []
for _ in range(n):
    h.append(int(input()))
ans = 0
while (max(h) > 0):
    h[h.index(max(h))] -= a - b
    h = [hh - b for hh in h]
    ans += 1
print(ans)

### FIXED CODE ###

def calc(n):
    damage = (b * n)
    d = [max(dd - damage, 0) for dd in h]
    a_num = 0
    for i in range(len(d)):
        a_num += max(0, 1 + (d[i]-1) // (a - b))
    if a_num <= n:
        return True
    return False

n, a, b = map(int, input().split())
h = []
for _ in range(n):
    h.append(int(input()))
ans = 0
h.sort()

left = 0
right = 10000000000

while (right - left) > 1:
    middle = (left + right) // 2
    if calc(middle):
        right = middle
    else:
        left = middle
print(right)
### BUGGY CODE ###

def gcd(x_y):
    tmp = list(map(int, x_y.split()))
    x = tmp[0]
    y = tmp[1]

    xcd = set([ n for n in range(1, x+1) if  x % n == 0])  # xの約数
    ycd = set([ n for n in range(1, y+1) if  y % n == 0])  # yの約数
    cd = list(xcd & ycd)  # ｘとyの公約数
    return max(cd)  # ｘとyの最大公約数

x_y = input()
print(gcd(x_y))


### FIXED CODE ###

def gcd(x, y):
    if x < y:
        tmp = x
        x = y
        y = tmp
    while y > 0:
        r = x % y
        x = y
        y = r

    return print(x)

x_y = input()
tmp = list(map(int, x_y.split()))
x = tmp[0]
y = tmp[1]
gcd(x, y)
### BUGGY CODE ###

N=int(input())
a=list(map(int,input().split()))
s=set(a)
ans=0
for i in s:
    j=a.count(i)
    if j<i:
        ans+=j
    else:
        ans+=j-i
print(ans)

### FIXED CODE ###

N=int(input())
a=list(map(int,input().split()))
a.sort()
C=[0]
s=[a[0]]
for i in a:
    if(s[-1]==i):
        C[-1]+=1
    else:
        C.append(1)
        s.append(i)
ans=0
for i in range(len(s)):
    if C[i]<s[i]:
        ans+=C[i]
    else:
        ans+=C[i]-s[i]
print(ans)
### BUGGY CODE ###

from collections import deque

h,w = map(int,input().split())
sy,sx = map(int,input().split())
gy,gx = map(int,input().split())
a = [list(input())for _ in range(h)]

sx -= 1
sy -= 1
gx -= 1
gy -= 1

dx=[1,0,-1,0,  2,1,0,-1,-2,  2,1,-1,-2,  2,-2,  2,1,-1,-2,  2,1,0,-1,-2]
dy=[0,1,0,-1,  2,2,2,2,2,  1,1,1,1,  0,0,  -1,-1,-1,-1,  -2,-2,-2,-2,-2]
m = len(dx)

def bfs():
    d = [[float("inf")]*w for _ in range(h)]
    q = deque([])
    q.append((sx,sy))
    d[sy][sx] = 0 #warp回数
    goal = False

    while q:
        p = q.pop()
        #print((p[0],p[1]),d[p[1]][p[0]])
        if p[0] == gx and p[1] == gy:
            goal = True

        for i in range(m):
            nx = p[0]+dx[i]
            ny = p[1]+dy[i]
            if i < 4:
                if 0<=nx<w and 0<=ny<h and a[ny][nx] != "#" and d[p[1]][p[0]] < d[ny][nx]:
                    q.append((nx,ny))
                    d[ny][nx] = d[p[1]][p[0]]
            else:
                if 0<=nx<w and 0<=ny<h and a[ny][nx] != "#" and d[p[1]][p[0]] < d[ny][nx]:
                    q.append((nx,ny))
                    d[ny][nx] = d[p[1]][p[0]] + 1

    if goal == False:
        return -1
    else:
        return d[gy][gx]
        
print(bfs())

### FIXED CODE ###

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

h,w = map(int,input().rstrip().split())
sy,sx = map(int,input().rstrip().split())
gy,gx = map(int,input().rstrip().split())
a = [list(input().rstrip())for _ in range(h)]

sx -= 1
sy -= 1
gx -= 1
gy -= 1

dx=[1,0,-1,0]
dy=[0,1,0,-1]

def bfs():
    d = [[float("inf")]*w for _ in range(h)]
    q = deque([])
    q.append((sx,sy))
    d[sy][sx] = 0 #warp回数
    goal = False
    local_area = deque([])

    while q:
        p = q.popleft()
        local_area.append((p[0],p[1]))
        if p[0] == gx and p[1] == gy:
            goal = True
            break

        for i in range(4):
            nx = p[0]+dx[i]
            ny = p[1]+dy[i]
            if 0<=nx<w and 0<=ny<h and a[ny][nx] != "#" and d[ny][nx] == float("inf"):
                q.append((nx,ny))
                d[ny][nx] = d[p[1]][p[0]]
        if len(q) == 0 and goal == False:
            while local_area:
                p = local_area.popleft()
                for i in range(-2,3):
                    for j in range(-2,3):
                        nx = p[0]+i 
                        ny = p[1]+j
                        if 0<=nx<w and 0<=ny<h and a[ny][nx] != "#" and d[ny][nx] == float("inf"):
                            q.append((nx,ny))
                            d[ny][nx] = d[p[1]][p[0]] + 1                        

    if goal == False:
        return -1
    else:
        return d[gy][gx]
        
print(bfs())
### BUGGY CODE ###

def gcd_cnt(t):
    a = 0
    kosuu = n//t
    a=kosuu*(2*t + (kosuu-1)*t)//2
    return a

n = int(input())
sub = 0
#約数でそのままアクセス可能
kosuu_ls = [0]*(n+1)
for t in range(1,n+1):
    sub+=gcd_cnt(t)
print(sub)


### FIXED CODE ###

def gcd_cnt(n):
    sub = 0
    for i in range(1, n+1):
        kosuu = n//i
        sub+=kosuu*(2*i + (kosuu-1)*i)//2
    return sub

n = int(input())
sub = gcd_cnt(n)
print(sub)
### BUGGY CODE ###

N = int(input())
a = list(map(int, input().split()))
A = []
for i in range(N):
  A.append(a[i]-1)
  A.append(a[i])
  A.append(a[i]+1)
ans = 0
for a in A:
  if ans < A.count(a):
    ans = A.count(a)
print(ans)

### FIXED CODE ###

N = int(input())
a = list(map(int, input().split()))
a.sort()
oldi = 0
m = a[0]
M = 0
ans = 0
if N == 1:
  ans = 1
for i in range(1, N):
  M = a[i]
  while M - m > 2:
    oldi += 1
    m = a[oldi]
  if i - oldi + 1 > ans:
    ans = i - oldi + 1
print(ans)
### BUGGY CODE ###

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

s0=1
for i in range(1,K+1):
    s0=s0*A[K-i]


for i in range(N-K):
    s1=s0/A[K-K+i]*A[K+i]
    if s1>s0:
        print('Yes')
    else:
        print('No')
    s0=s1

### FIXED CODE ###

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


s0=A[0]


for i in range(N-K):
    s1=A[K+i]
    if s1>s0:
        print('Yes')
    else:
        print('No')
    s0=A[i+1]
### BUGGY CODE ###

import heapq
X,Y,Z,K=[int(s) for s in input().split()]
x=sorted([-int(s) for s in input().split()])
y=sorted([-int(s) for s in input().split()])
z=sorted([-int(s) for s in input().split()])
count=[[[0 for _ in range(X)]for _ in range(Y)]for _ in range(Z)]
count[0][0][0]=1
Q=[[x[0]+y[0]+z[0],0,0,0]]
heapq.heapify(Q)
X-=1
Y-=1
Z-=1
for i in range(K):
  cake,a,b,c=heapq.heappop(Q)
  print(-cake)
  if a<X and count[a+1][b][c]==0:
    heapq.heappush(Q,[x[a+1]+y[b]+z[c],a+1,b,c])
    count[a+1][b][c]=1
  if b<Y and count[a][b+1][c]==0:
    heapq.heappush(Q,[x[a]+y[b+1]+z[c],a,b+1,c])
    count[a][b+1][c]=1
  if c<Z and count[a][b][c+1]==0:
    heapq.heappush(Q,[x[a]+y[b]+z[c+1],a,b,c+1])
    count[a][b][c+1]=1

### FIXED CODE ###

X,Y,Z,K=[int(s) for s in input().split()]
xls=sorted([int(s) for s in input().split()],reverse=True)
yls=sorted([int(s) for s in input().split()],reverse=True)
zls=sorted([int(s) for s in input().split()],reverse=True)
xyls=[]
for x in xls[:K]:
  for y in yls[:K]:
    xyls.append(x+y)
xyls=sorted(xyls,reverse=True)
cake=[]
for xy in xyls[:K]:
  for z in zls[:K]:
    cake.append(xy+z)
cake=sorted(cake,reverse=True)
for i in range(K):
  print(cake[i])
### BUGGY CODE ###

N = int(input())
ans = 0
for i in range(1, N+1):
    ans += (i-1)
print(ans)


### FIXED CODE ###

N = int(input())
ans = ((N)*(N-1))//2
print(ans)
### BUGGY CODE ###

#coding: utf-8
from copy import deepcopy
def main():
	N, M = map(int, input().split())
	p_list = []
	p_dict = {}
	for i in range(M):
		p, y = map(int, input().split())
		p_list.append([p, y])
		if p not in p_dict.keys():
			p_dict[p] = [y]
		else:
			p_dict[p].append(y)
	for p in p_dict.keys():
		p_dict[p].sort()
	for i in range(M):
		s1 = p_list[i][0]	
		#s1 = str(p_list[i][0])
		s2 = p_dict[p_list[i][0]].index(p_list[i][1])
		print("{:06d}{:06d}".format(s1, s2+1))
		#print("0" * (6 - len(str(s1))) + str(s1) + "0" * (6 - len(str(s2))) + str(s2 + 1))
	#print(p_dict)
if __name__ == "__main__":
	main()

### FIXED CODE ###

#coding: utf-8
from copy import deepcopy


def main():
    N, M = map(int, input().split())
    p_dict = {}
    for i in range(M):
        p, y = map(int, input().split())
        if p not in p_dict.keys():
            p_dict[p] = [[y, p, i]]
        else:
            #yとp元の順番を入れとく
            p_dict[p].append([y, p, i])
    ans = []
    for p in p_dict.keys():
        p_dict[p].sort()
        for i in range(len(p_dict[p])):
            #昇順で並べたときの順番を入れとく
            p_dict[p][i].append(i+1)
            ans.append(p_dict[p][i])
    #ans = [y, p, input_index, sorted_index]
    ans.sort(key=lambda x: x[2])
    for y, p, oi, si in ans:
        print("{:06d}{:06d}".format(p, si))
if __name__ == "__main__":
    main()
### BUGGY CODE ###

import numpy as np
from collections import deque


def p_e():
    n, k = map(int, input().split())
    *a, = map(int, input().split())
    dp = np.array([0] * n)
    q = deque([-1] * n)
    ans = 0
    for i in range(n):
        q.appendleft(i + 1)
        q.pop()
        c = a[i] % k
        dp[:i + 1] += c
        dp[:i + 1] %= k
        ans += (dp == q).sum()
    print(ans)
    
p_e()

### FIXED CODE ###


from collections import deque
from collections import defaultdict


def p_e():
    n, k = map(int, input().split())
    a = [0] + list(map(int, input().split()))
    for i in range(n):
        a[i + 1] = (a[i + 1] + a[i] - 1) % k
    d = defaultdict(int)
    d[0] = 1
    q = deque()
    ans = 0
    for i in range(1, n + 1):
        if i - k >= 0:
            d[a[i - k]] -= 1
        ans += d[a[i]]
        d[a[i]] += 1
    print(ans)
    
p_e()