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

n,m,k=map(int,input().split())
A=list(map(int,input().split()))
B=list(map(int,input().split()))

a=[0]
b=[0]

for i in range(n):
    a.append(a[i]+A[i])
for i in range(m):
    b.append(b[i]+B[i])
    
c=0

for i in range(n+1):
    for j in range(m+1):
        if a[i]+b[m-j]>k:
            continue
        else:
            c=max(i+m-j,c)
            continue
else:
    print(c)

### FIXED CODE ###

n,m,k=map(int,input().split())
A=list(map(int,input().split()))
B=list(map(int,input().split()))

a=[0]
b=[0]

for i in range(n):
    a.append(a[i]+A[i])
for i in range(m):
    b.append(b[i]+B[i])
    
c=0
idx=m

for i in range(n+1):
    while 1:
        if idx<0:
            break
        if a[i]+b[idx]>k:
            idx-=1
            continue
        else:
            c=max(i+idx,c)
            break
else:
    print(c)
### BUGGY CODE ###

def lcs(x,y):
    x = " " + x
    y = " " + y
    c = [[0 for i in xrange(len(x))] for j in xrange(len(y))]
    for i in xrange (1,len(y)):
        for j in xrange (1,len(x)):
            if x[j] == y[i]:
                a = 1
            else:
                a = 0
            c[i][j] = max(c[i][j-1],c[i-1][j],c[i-1][j-1] + a)
    return max(max(c))
n = input() 
for i in xrange (n): 
    x = raw_input()
    y = raw_input() 
    print lcs(x,y)

### FIXED CODE ###

def lcs():
    x, y = raw_input(), raw_input()
    b1 = [0 for k in range(len(y)+1)]
    for i in xrange(len(x)):
        a = x[i]
        b2 = b1 + []
        for j in xrange(len(y)):
            if a == y[j]:
                b1[j+1] = b2[j] + 1
            elif b1[j+1] < b1[j]:
                b1[j+1] = b1[j]
    print max(b1)
 
n = input()
for i in xrange(n):
    lcs()
### BUGGY CODE ###

from collections import defaultdict
g = defaultdict(list)

n, m = map(int, input().split())
if m==0:
    print('Yes')
    exit()
for i in range(m):
    l, r, d = map(int, input().split())
    g[l].append((r, d))
    g[r].append((l, -1*d))
    
visited = {}
vv = {k:None for k in g.keys()}
def dfs(v):
    stack = []
    visited[v] = True
    stack.append((v,0))
    while len(stack)!= 0:
        v,w = stack.pop()
        vv[v] = w
        for c,d in g[v]:
            if not visited.get(c, False):
                visited[c] = True
                stack.append((c,w+d))

f = list(g.keys())[0]
not_visited = g.keys()
while True:
    dfs(f)
    not_visited = list(set(not_visited) - set(visited.keys()))
    if not_visited == []: break
    else: f = not_visited[0]

for k in g.keys():
    v = vv[k]
    for c,w in g[k]:
        if not v + w == vv[c]:
            print('No')
            exit()

print('Yes')

### FIXED CODE ###

from collections import defaultdict
g = defaultdict(list)

n, m = map(int, input().split())
if m==0:
    print('Yes')
    exit()
for i in range(m):
    l, r, d = map(int, input().split())
    g[l].append((r, d))
    g[r].append((l, -1*d))
    
visited = {}
vv = {k:None for k in g.keys()}
def dfs(v):
    stack = []
    visited[v] = True
    stack.append((v,0))
    while len(stack)!=0:
        v,w = stack.pop()
        vv[v] = w
        for c,d in g[v]:
            if not visited.get(c, False):
                visited[c] = True
                stack.append((c,w+d))

for f in g.keys():
    if not visited.get(f):
        dfs(f)

for k in g.keys():
    v = vv[k]
    for c,w in g[k]:
        if not v + w == vv[c]:
            print('No')
            exit()

print('Yes')
### BUGGY CODE ###

n,k=map(int,input().split())
h=list(map(int,input().split()))+[0]*(k+10)
dp=[(float("inf")) for i in range(n+k+10)]
dp[0]=0
#print(dp)
def main():
  for i in range(n-1):
      #print(i)
      for j in range(k):
          dp[i+j+1]=min(dp[i]+abs(h[i]-h[i+j+1]),dp[i+j+1])
      #print(dp,i)
  print(dp[n-1])
main()

### FIXED CODE ###

def main():
  n,k=map(int,input().split())
  h=list(map(int,input().split()))+[0]*(k+10)
  dp=[(float("inf")) for i in range(n+k+10)]
  dp[0]=0
  for i in range(n-1):
    for j in range(k):
      dp[i+j+1]=min(dp[i]+abs(h[i]-h[i+j+1]),dp[i+j+1])
  return (dp[n-1])
print(main())
### BUGGY CODE ###

N = int(input())
S = [[] for i in range(10)]
count = 0
for i in range(N):
  string = input()
  if not string in S[len(string)-1]:
    S[len(string)-1].append(string)
    count += 1
print(count)

### FIXED CODE ###

N = int(input())
S = []
for i in range(N):
  string = input()
  S.append(string)
S = sorted(S)
count = N
for i in range(N-1):
  if S[i] == S[i+1]:
    count -= 1
print(count)
### BUGGY CODE ###

N = int(input())
A = [list(map(int, input().split()))[::-1] for _ in range(N)]
day = 0
while True:
    flag = True
    Done = [False] * N
    for i, a in enumerate(A):
        if len(a) == 0:
            continue
        if Done[i]:
            continue
        x = a[-1] - 1
        if A[x] and (not Done[x]) and (A[x][-1] - 1 == i):
            A[i].pop()
            A[x].pop()
            Done[i] = True
            Done[x] = True
            flag = False
    if flag:
        break
    day += 1
F = False
for a in A:
    if len(a) != 0:
        F = True
        break
if F:
    print(-1)
else:
    print(day)

### FIXED CODE ###

import sys
# input = sys.stdin.buffer.readline


N = int(input())
A = [list(map(int, input().split()))[::-1] for _ in range(N)]
day = 0
cnt = N
Last = set([i for i in range(N)])
while cnt:
    flag = True
    Done = [False] * N
    L = set()
    for i in Last:
        if len(A[i]) == 0:
            continue
        if Done[i]:
            continue
        x = A[i][-1] - 1
        if A[x] and (not Done[x]) and (A[x][-1] - 1 == i):
            A[i].pop()
            A[x].pop()
            Done[i] = True
            Done[x] = True
            L.add(i)
            L.add(x)
            flag = False
            if not A[i]:
                cnt -= 1
            if not A[x]:
                cnt -= 1
    Last = L
    if flag:
        break
    day += 1
if cnt:
    print(-1)
else:
    print(day)
### BUGGY CODE ###

from collections import defaultdict
N, = map(int, input().split())
dd = defaultdict(int)
ss = []
for _ in range(N):
    a, b, c, d = map(int, input().split())
    dd[(a,b,c,d)] += 1
    dd[(b,c,d,a)] += 1
    dd[(c,d,a,b)] += 1
    dd[(d,a,b,c)] += 1
    ss.append((a,b,c,d))
def icr(x):
    a, b, c, d = x
    for faf in [(b,c,d,a), (c,d,a,b), (d,a,b,c), (a,b,c,d)]:
        dd[faf] += 1
def dcr(x):
    a, b, c, d = x
    for faf in [(b,c,d,a), (c,d,a,b), (d,a,b,c), (a,b,c,d)]:
        dd[faf] -= 1

def f(ff, gg):
    a,b,c,d=ff
    e, h, g, f = gg
    tl = [(a,e,f,b), (b,f,g,c), (c,g,h,d), (d,h,e,a)]
    r = 1
    for cp in tl:
        r *= dd[cp]
        dcr(cp)
    for cp in tl:
        icr(cp)
    return r

r = 0
for i in range(N):
    a,b,c,d = ss[i]
    ff = (a,b,c,d)
    dcr(ff)
    for j in range(N):
        if i == j:
            continue
        x, y, z, w = ss[j]
        sl = [(x,y,z,w), (y,z,w,x), (z,w,x,y), (w,x,y,z)]
        for s in sl:
            dcr(s)
            r += f(ff,s)
            icr(s)
    icr(ff)
print(r//6)


### FIXED CODE ###

from collections import defaultdict
N, = map(int, input().split())

def normal(xs):
    mnx = min(xs)
    xi = xs.index(mnx)
    if xs[(xi+3)%4] == mnx:
        if xs[(xi+2)%4] == mnx:
            xi = (xi+2)%4
        else:
            xi = (xi+3)%4
    if xs[(xi+1)%4] > xs[(xi+3)%4]:
        xi = (xi+2)%4
    return (xs[xi%4], xs[(xi+1)%4], xs[(xi+2)%4], xs[(xi+3)%4])
#x = (0,2,2,0)
#print(normal(x))

dd = defaultdict(int)
ss = []
for _ in range(N):
    a, b, c, d = map(int, input().split())
    x = normal([a,b,c,d])
    n=1
    if x[0] == x[2] and x[1] == x[3]:
        n *= 2
        if x[0] == x[1]:
            n *= 2
    dd[x] += n
    ss.append(x)

def icr(x):
    n = 1
    if x[0] == x[2] and x[1] == x[3]:
        n *= 2
        if x[0] == x[1]:
            n *= 2
    dd[x] += n

def dcr(x):
    n = 1
    if x[0] == x[2] and x[1] == x[3]:
        n *= 2
        if x[0] == x[1]:
            n *= 2
    dd[x] -= n

def f(ff, gg):
    #print(dd)
    a,b,c,d=ff
    e,h,g,f=gg
    tl = list(map(normal, [(a,e,f,b), (b,f,g,c), (c,g,h,d), (d,h,e,a)]))
    r = 1
    for cp in tl:
        if cp not in dd:
            r = 0
            break
        r *= dd[cp]
        dcr(cp)
    for cp in tl:
        if cp not in dd:
            break
        icr(cp)
    return r

r = 0
for i in range(N):
    ff = ss[i]
    dcr(ff)
    for j in range(i+1, N):
        sl = ss[j]
        dcr(sl)
        x, y, z, w = sl
        sls = [(x,y,z,w), (y,z,w,x), (z,w,x,y), (w,x,y,z)]
        for s in sls:
            r += f(ff, s)
        icr(sl)
    icr(ff)
print(r//3)
### BUGGY CODE ###

x,y,z,k=map(int,input().split())
*a,=map(int,input().split())
*b,=map(int,input().split())
*c,=map(int,input().split())
l=[0]*3000
r=[0]*3000
def merge_sort(array):
    if len(array) <= 1:
        return array
    cnt=len(array)//2
    left=array[:cnt]
    right=array[cnt:]
    left = merge_sort(left)
    right = merge_sort(right)
    return merge(left, right)


def merge(left, right):
    array = [0]*3000
    l,r,ind=0,0,0
    while l < len(left) and r < len(right):
        if left[l] >= right[r]:
            array[ind]=left[l]
            l+=1
            ind+=1
        else:
            array[ind]=right[r]
            r+=1
            ind+=1
        if ind>=3000:
            return array
    if l < len(left):
        return array[:ind]+left[l:]
    if r < len(right):
        return array[:ind]+right[r:]

a=merge_sort(a)
b=merge_sort(b)
c=merge_sort(c)
for i in range(y):
    l=merge(l,list(map(lambda w:w+b[i],a)))
for i in range(z):
    r=merge(r,list(map(lambda w:w+c[i],l)))
for i in range(k):
    print(r[i])

### FIXED CODE ###

x,y,z,q=map(int,input().split())
a=sorted(map(int,input().split()),reverse=True)
b=sorted(map(int,input().split()),reverse=True)
c=sorted(map(int,input().split()),reverse=True)
 
def bisect(l,r):
  cnt=(l+r)//2
  if cnt==l:
    return l-1+judge(l)
  if judge(cnt):
    return bisect(cnt+1,r)
  else:
    return bisect(l,cnt)
def judge(thr):
  m=0
  for i in range(x):
    for j in range(y):
      if i*j>q:
        break
      for k in range(z):
        if i*j*k>q or a[i]+b[j]+c[k]<thr:
          break
        m+=1
        if m>=q:
          return True
  return False
def make(thr):
  m=0
  l=[]
  for i in a:
    for j in b:
      for k in c:
        n=i+j+k
        if n<thr+1:
          break
        m+=1
        l+=[n]
  l.sort(reverse=True)
  return l+[thr]*(q-len(l))
thr=bisect(0,a[0]+b[0]+c[0]+1)
ans=make(thr)
for w in ans:
  print(w)
### BUGGY CODE ###

n = int(input())
k = [[int(input())]]
cou = 1
for i in range(n-1):
    now = int(input())
    flag = False
    for i in range(cou):
        if now == k[i][-1]+1:
            k[i].append(now)
            flag = True
    if not flag:
        k.append([now])
        cou += 1
p = 0
for i in range(cou):
    p = max(p,len(k[i]))
print(n-p)

### FIXED CODE ###

from bisect import bisect_left,bisect
 
n = int(input())
cou = [0 for i in range(n+1)]
for i in range(n):
    now = int(input())
    cou[now] = cou[now-1] + 1  

print(n-max(cou))
### BUGGY CODE ###

def main():
    X = input()

    ans = part(X)
    print(ans)


def part(X):
    while True:
        n = len(X)
        for i in range(n-1):
            if X[i:i+2] == "ST":
                X = X[:i] + X[i+2:]
                break

        if n == len(X):
            break

    return len(X)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    X = input()

    #ans = part(X)
    ans = editorial(X)
    print(ans)


def test_ans():
    X_ans = [
        ("TSTTSS", 4),
        ("SSTTST", 0),
        ("TSSTTTSS", 4),
    ]
    for X, ans in X_ans:
        assert part(X) == editorial(X) == ans


def editorial(X):
    stack = [X[0]]
    ans = len(X)
    for c in X[1:]:
        if stack and stack[-1] == "S" and c == "T":
            ans -= 2
            stack.pop()
        else:
            stack.append(c)

    return ans


def part(X):
    while True:
        n = len(X)
        for i in range(n-1):
            if X[i:i+2] == "ST":
                X = X[:i] + X[i+2:]
                break

        if n == len(X):
            break

    return len(X)


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

N = int(input())
D = [int(input()) for i in range(N)]
a = D[:]
b = [0 for k in range(N)]
for i in range(N):
    a[i] = 0
    print(max(a))
    a = D[:]

### FIXED CODE ###

N = int(input())
d = [int(input()) for i in range(N)]

M = max(d)
D = d[:]
d.remove(M)
m = max(d)

for j in range(N):
    if D[j]==M:
        print(m)
    else:
        print(M)
### BUGGY CODE ###

n, m, k = map(int, input().split())
ans = [0] * n
p = [{'T':[], 'B':[]} for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    p[a-1]['T'].append(b)
    p[b-1]['T'].append(a)
    
for _ in range(k):
    c, d = map(int, input().split())
    p[c-1]['B'].append(d)
    p[d-1]['B'].append(c)

fl = []

for i, dt in enumerate(p):
    isContinue = False
    for f in fl:
        if i+1 in f:
            isContinue = True
            break
    if isContinue:
        continue
    tmp_fl = [i+1] + dt['T']
    rmn = [t for t in dt['T']]
    alr = [i+1]
    while not len(rmn) == 0:
        r = rmn.pop(0)
        alr.append(r)
        new_fl = p[r-1]['T']
        for nf in new_fl:
            if not nf in tmp_fl:
                tmp_fl.append(nf)
            if not nf in rmn and not nf in alr:
                rmn.append(nf)
    fl.append(tmp_fl)
    
for i, dt in enumerate(p):
    for f in fl:
        if i+1 in f:
            for s in f:
                if not s in [i+1]+ dt['T'] + dt['B']:
                    ans[i] += 1

print(' '.join(map(str, ans)))

### FIXED CODE ###

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

def main():
    N,M,K = map(int,input().split())
    friend = [[] for _ in range(N)]
    for _ in range(M):
        a,b = map(int,input().split())
        friend[a-1].append(b-1)
        friend[b-1].append(a-1)
        
    brock = [[] for _ in range(N)]
    for _ in range(K):
        c,d = map(int,input().split())
        brock[c-1].append(d-1)
        brock[d-1].append(c-1)
        
    parent = [-1 for _ in range(N)]
    group = [0 for _ in range(N)]
    
    for i in range(N):
        put = []
        if parent[i] == -1:
            q = deque([i])
            parent[i] = i
            while q:
                now = q.pop()
                put.append(now)
                for fol in friend[now]:
                    if parent[fol] == -1:
                        parent[fol] = i
                        q.append(fol)
            l = len(put)
            for num in put:
                group[num] = l-1
                
        else:
            continue

    for i in range(N):
        group[i] -= len(friend[i])
        for dis in brock[i]:
            if parent[i] == parent[dis]:
                group[i] -= 1
    
    print(*group)
    
if __name__ == "__main__":
    main()
### BUGGY CODE ###

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

x_list = [0, ]
v_list = [0, ]
x_oa = [0, ]
x_2oa = [0, ]
max_a = {0: 0}
max_2a = {0: 0}

tmp_v = 0

for i in range(N):
    x, v = map(int, input().split())

    tmp_v += v

    x_list.append(x)
    v_list.append(v)
    x_oa.append(tmp_v - x)
    x_2oa.append(tmp_v - 2 * x)
    max_a[i + 1] = max(x_oa)
    max_2a[i + 1] = max(x_2oa)

x_list.append(C)
v_list.append(0)

tmp_v = 0
ans = 0
for i in reversed(range(1, N + 2)):

    x = x_list[i]
    v = v_list[i]
    tmp_v += v
    # print(x, v, i)

    tmp_oa = tmp_v - 2 * (C - x) + max_a[i - 1]
    tmp_2oa = tmp_v - C + x + max_2a[i - 1]
    ans = max(ans, tmp_oa, tmp_2oa)

print(ans)

### FIXED CODE ###

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

x_list = [0, ]
v_list = [0, ]
x_oa = 0
x_2oa = 0
max_a = {0: 0}
max_2a = {0: 0}

tmp_v = 0

for i in range(N):
    x, v = map(int, input().split())

    tmp_v += v

    x_list.append(x)
    v_list.append(v)
    x_oa = max(tmp_v - x, x_oa)
    x_2oa = max(tmp_v - 2 * x, x_2oa)
    max_a[i + 1] = x_oa
    max_2a[i + 1] = x_2oa

x_list.append(C)
v_list.append(0)

tmp_v = 0
ans = 0
for i in reversed(range(1, N + 2)):

    x = x_list[i]
    v = v_list[i]
    tmp_v += v
    # print(x, v, i)

    tmp_oa = tmp_v - 2 * (C - x) + max_a[i - 1]
    tmp_2oa = tmp_v - C + x + max_2a[i - 1]
    ans = max(ans, tmp_oa, tmp_2oa)

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



import numpy as np
N,K=map(int,input().split())
A=list(map(int,input().split()))

A=np.array(A)

A_pos=np.sort(A[A>0])
A_neg=np.sort(A[A<0])
A_neg2=np.sort(-A_neg)

np=len(A_pos)
nn=len(A_neg)
nz=N-np-nn
n_post=np*(np-1)//2+(nn*(nn-1))//2
n_zero=nz*(np+nn)+nz*(nz-1)//2
n_neg=np*nn

#array内で積がx未満になるペアの数
def syakutori_pos1(x):
    res=0
    j=np-1
    for i in range(np):
        tmp=0
#         j=n-1
        y=-(-x//A_pos[i])
        while j!=-1:
            
            if A_pos[j]>=y:
                j-=1
            else:
                break
        
        tmp+=j+1
        if A_pos[i]**2<x:
            tmp-=1

        res+=tmp
    res=res//2
    return res

def syakutori_pos2(x):
    res=0
    j=nn-1
    for i in range(nn):
        tmp=0
#         j=n-1
        y=-(-x//A_neg2[i])
        while j!=-1:
            
            if A_neg2[j]>=y:
                j-=1
            else:
                break
        
        tmp+=j+1
        if A_neg2[i]**2<x:
            tmp-=1

        res+=tmp
    res=res//2
    return res


#array内で積がx未満になるペアの数
def syakutori_neg(x):
    y=x//A_neg
#     print(A_pos,y)
    res=0
    i=0
    j=np-1
    for z in reversed(y):
        while(j!=-1):
            if z<A_pos[j]:
                j-=1
            else:
                break
#         print(z,j+1)
        res+=j+1
    return np*nn-res



def syakutori(x):
    if x>0:
        return syakutori_pos1(x)+syakutori_pos2(x)+n_neg+n_zero
    elif x==0:
        return n_neg
    else:
        return syakutori_neg(x)




r=10**18
l=-10**18
while(r-l>1):
    mid=(l+r)//2
    z=syakutori(mid)
#     z= count_pair(mid)
#     print(l,r)
    if z < K:
        l=mid
    else:
        r=mid
print(l)

### FIXED CODE ###

import numpy as np
N,K=map(int,input().split())
A=list(map(int,input().split()))

A=np.array(A)

A_pos=np.sort(A[A>0])
A_neg=np.sort(A[A<0])
A_neg2=-A_neg[::-1]
n_pos=len(A_pos)
n_neg=len(A_neg)
n_zero=N-n_pos-n_neg

def position_in_neg(x):
    y=n_pos-np.searchsorted(A_pos,x//A_neg,side='right')
    return y.sum()

def position_in_pos(x):
    z=np.searchsorted(A_pos,-(-x//A_pos),side='left')
    w=np.searchsorted(A_neg2,-(-x//A_neg2),side='left')
    tmp=len(A_pos[A_pos**2<x])+len(A_neg2[A_neg2**2<x])
    return (z.sum()+w.sum()-tmp)//2

def position(x):
    if x<0:
        return position_in_neg(x)
    elif x==0:
        return n_pos*n_neg
    else:
        return position_in_pos(x)+n_pos*n_neg+(n_pos+n_neg)*n_zero+n_zero*(n_zero-1)//2

l=-pow(10,18)
r=pow(10,18)
while(r-l>1):
    mid=(l+r)//2
    if position(mid)<K:
        l=mid
    else:
        r=mid
print(l)
### BUGGY CODE ###

from collections import deque
import random
N=int(input())
A=[int(i) for i in input().split()]
B=[int(i) for i in input().split()]
if 0:
    N=2*10**5
    A=[random.randrange(1,N+1) for i in range(N)]
    B=[random.randrange(1,N+1) for i in range(N)]
    A.sort()
    B.sort()
a=[0 for i in range(N+1)]
b=[0 for i in range(N+1)]
for i in range(N):
    a[A[i]]+=1
    b[B[i]]+=1
if max([a[i]+b[i] for i in range(1,N+1)])>N:
    print("No")
    exit()
print("Yes")
ans0=[0 for i in range(N)]
ans1=[0 for i in range(N)]
flag0=1
flag1=1
q=deque([])
for i in range(N):
    q.append(B[i])
for i in range(N):
    if q[0]==q[-1] and q[0]==A[i]:
        flag0=0    
        break
    if q[-1]==A[i]:
        ans0[i]=q.popleft()
    else:
        ans0[i]=q.pop()
q=deque([])
for i in range(N):
    q.append(B[i])
for i in range(N):
    if q[0]==q[-1] and q[0]==A[i]:
        flag1=0    
        break
    if q[0]==A[i]:
        ans1[i]=q.pop()
    else:
        ans1[i]=q.popleft()
if flag0:
    print(*ans0)
elif flag1:
    print(*ans1)
else:
    while(1):
        ans2=[0 for i in range(N)]
        flag2=1
        q=deque([])
        for i in range(N):
            q.append(B[i])
        for i in range(N):
            if q[0]==q[-1] and q[0]==A[i]:
                flag2=0    
                break
            if q[0]==A[i]:
                ans2[i]=q.pop()
            elif q[-1]==A[i]:
                ans2[i]=q.popleft()
            else:
                if random.randrange(2):
                    ans2[i]=q.pop()
                else:
                    ans2[i]=q.popleft()
        if flag2:
            print(*ans2)
            exit()




### FIXED CODE ###

import random
N=int(input())
A=[int(i) for i in input().split()]
B=[int(i) for i in input().split()]
a=[0 for i in range(N+1)]
b=[0 for i in range(N+1)]
for i in range(N):
    a[A[i]]+=1
    b[B[i]]+=1
if max([a[i]+b[i] for i in range(1,N+1)])<=N:
    print("Yes")
else:
    print("No")
    exit()
B=B[::-1]
point=0
for i in range(N):
    if A[i]==B[i]:
        point+=1
while(point>0):
    x=random.randrange(N)
    y=random.randrange(N)
    if x==y:
        continue
    before=0
    after=0
    if A[x]==B[x]:
        before+=1
    if A[y]==B[y]:
        before+=1
    if A[x]==B[y]:
        after+=1
    if A[y]==B[x]:
        after+=1
    if before>after:
        B[x],B[y]=B[y],B[x]
        point=point+after-before
print(*B)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
import numpy as np
from collections import defaultdict

N,K = map(int,input().split())
A = [0] + list(map(int,input().split()))
S = np.cumsum(A)

answer = 0
for j in range(N):
    for i in range(j+1,min(N+1, K+j)):
        if (S[i]- S[j]) % K == (i-j):
            answer += 1

print(answer)

### FIXED CODE ###

import sys
input = sys.stdin.readline
import numpy as np
from collections import defaultdict

N,K = map(int,input().split())
A = [0] + [int(i)-1 for i in input().split()]
Acum = np.cumsum(A)
Acum = [i%K for i in Acum]

counter = defaultdict(int)
answer = 0
for i,x in enumerate(Acum):
    answer += counter[x]
    counter[x] += 1
    if i-K+1 >= 0:
        counter[Acum[i-K+1]] -= 1
  
print(answer)