Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
n,m = map(int,input().split())

Q = []
P = [[] for _ in range(n)]
for i in range(m):
    p,y = map(int,input().split())
    Q.append([p,y])
    P[p-1].append(y)

P_1 = [sorted(l) for l in P]

for p,y in Q:
    a = str(p).zfill(6)
    b = str(P_1[p-1].index(y) + 1).zfill(6)
    print(a+b)

Fixed submission:
import bisect

n,m = map(int,input().split())

Q = []
P = [[] for _ in range(n)]
for i in range(m):
    p,y = map(int,input().split())
    Q.append([p,y])
    P[p-1].append(y)

P_1 = [sorted(l) for l in P]

for p,y in Q:
    a = str(p).zfill(6)
    b = str(bisect.bisect(P_1[p-1], y)).zfill(6)
    print(a+b)
Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
v=list(input().split())

even=[v[i] for i in range(n) if i%2 == 0]
odd=[v[i] for i in range(n) if i%2 == 1]
ans=0

e_n=max(even,key=even.count)
o_n=max(odd,key=odd.count)

if even==odd:
    print(even.count(even[0]))
else:
    ans=len(even)-even.count(e_n)+len(odd)-odd.count(o_n)
    print(ans)

Fixed submission:
import collections
n=int(input())
v=list(input().split())
ans=0

even=[v[i] for i in range(n) if i%2 == 0]
odd=[v[i] for i in range(n) if i%2 == 1]

ep=collections.Counter(even).most_common()
op=collections.Counter(odd).most_common()
ep.append((0,0))
op.append((0,0))

if ep[0] != op[0]:
    ans=n-(ep[0][1]+op[0][1])
else:
    if len(even)-ep[1][1]<len(odd)-op[1][1]:
        ans=n-ep[1][1]-op[0][1]
    else:
        ans=n-ep[0][1]-op[1][1]
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())

v=list(map(int,input().split()))

count=0

a=[v[i] for i in range(0,n,2)] 
b=max(a,key=lambda x:a.count(x))
c=[v[i] for i in range(1,n,2)] 
d=max(c,key=lambda x:c.count(x))

if a == c:
    print(min(len(a),len(c)))
    exit()

for i in a:
    if i != b:
        count +=1

for j in c:
    if j != d:
        count +=1
        

print(count)


Fixed submission:
import collections
n=int(input())
v=list(input().split())
ans=0

even=[v[i] for i in range(n) if i%2 == 0]
odd=[v[i] for i in range(n) if i%2 == 1]

ep=collections.Counter(even).most_common()
op=collections.Counter(odd).most_common()
ep.append((0,0))
op.append((0,0))

if ep[0] != op[0]:
    ans=n-(ep[0][1]+op[0][1])
else:
    if len(even)-ep[1][1]<len(odd)-op[1][1]:
        ans=n-ep[1][1]-op[0][1]
    else:
        ans=n-ep[0][1]-op[1][1]
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())

S = input()
w = [0]*N
e = [0]*N
ans = N
for i in range(N):
    if S[i] == "W":
        w[i] = 1
    else:
        e[i] = 1

for i in range(N):
    d = sum(w[:i]) + sum(e[i+1:])
    ans = min(ans,d)
    
print(ans)    

Fixed submission:
N = int(input())

S = input()

w = [0]*(N+1)
e = [0]*(N+1) 

for i in range(N):
    if S[i] == "W":
        w[i+1] = 1
    
    if S[i] == "E":
        e[i+1] = 1

for i in range(N):
    w[i+1] += w[i]
    e[i+1] += e[i]

ans = N
for i in range(1,N+1):
    d = w[i-1] + e[N]-e[i]
    ans = min(ans,d)

print(ans)
Buggy python submission (verdict: Runtime Error):
,B,X=map(int,input().split())

if A <=X  and A+B >= X:
    print('YES')
else:
    print('NO')
    

Fixed submission:
A,B,X=map(int,input().split())

if A <=X  and A+B >= X:
    print('YES')
else:
    print('NO')
Buggy python submission (verdict: Time Limit Exceeded):
a,b,k=map(int,input().split())

for i in range(a,b+1):
    if i <= a+k-1 or i >= b-k+1:
        print(i)

Fixed submission:
a,b,k=map(int,input().split())

for i in range(a,min(b,a+k-1)+1):
    print(i)

for j in range(max(b-k+1,a+k),b+1):
    print(j)

Buggy python submission (verdict: Time Limit Exceeded):
a,b,k=map(int,input().split())

c=[i for i in range(a,b+1) if i<=(a+k-1) or i>=(b-k+1) ]

for j in c:
    print(j)

Fixed submission:
a,b,k=map(int,input().split())

for i in range(a,min(b,a+k-1)+1):
    print(i)

for j in range(max(b-k+1,a+k),b+1):
    print(j)
Buggy python submission (verdict: Runtime Error):
import itertools

n = int(input())

l = [0]*n
for i in range(n):
    s = input()
    if s[0] == "M":
        l[0] += 1
    if s[0] == "A":
        l[1] += 1
    if s[0] == "R":
        l[2] += 1
    if s[0] == "C":
        l[3] += 1
    if s[0] == "H":
        l[4] += 1 

ans = 0
for a,b,c in list(itertools.combinations(l,3)):
    ans += a*b*c

print(ans)    

Fixed submission:
import itertools

n = int(input())

l = [0]*5
for i in range(n):
    s = input()
    if s[0] == "M":
        l[0] += 1
    if s[0] == "A":
        l[1] += 1
    if s[0] == "R":
        l[2] += 1
    if s[0] == "C":
        l[3] += 1
    if s[0] == "H":
        l[4] += 1 

ans = 0
for a,b,c in itertools.combinations(l,3):
    ans += a*b*c

print(ans)

Buggy python submission (verdict: Runtime Error):
import itertools

n = int(input())

l = [0]*n
for i in range(n):
    s = input()
    if s[0] == "M":
        l[0] += 1
    if s[0] == "A":
        l[1] += 1
    if s[0] == "R":
        l[2] += 1
    if s[0] == "C":
        l[3] += 1
    if s[0] == "H":
        l[4] += 1 

ans = 0
for a in list(itertools.combinations(l,3)):
    c = 1
    for i in a:
        c *=i
    ans += c

print(ans)    

Fixed submission:
import itertools

n = int(input())

l = [0]*5
for i in range(n):
    s = input()
    if s[0] == "M":
        l[0] += 1
    if s[0] == "A":
        l[1] += 1
    if s[0] == "R":
        l[2] += 1
    if s[0] == "C":
        l[3] += 1
    if s[0] == "H":
        l[4] += 1 

ans = 0
for a,b,c in itertools.combinations(l,3):
    ans += a*b*c

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
def get_prime(x):
    if x <= 1:
        return []
    prime = [2]
    limit = int(x**0.5)
    
    data = [i + 1 for i in range(2, x, 2)]
    while limit > data[0]:
        prime.append(data[0])
        data = [j for j in data if j%data[0] != 0]
    
    return prime + data
    

q=int(input())
table = get_prime(100000)
for i in range(q):
    l,r = map(int,input().split())
    ans = 0
    for p in range(l,r+1,2):
        if p in table and (p+1)//2 in table:
            ans +=1
    print(ans)          

Fixed submission:
def get_prime(x):
    l = [True] * (x + 1)
    l[0] = False
    l[1] = False
    for i in range(2,int(x**0.5) + 1):
        if not l[i]:
            continue
        for j in range(i * 2, x + 1, i):
            l[j] = False
    return l        
q=int(input())
table = get_prime(100000)
s=[0]*(100001)

for i in range(100000):
    if table[i] and table[(i+1)//2]:
        s[i] = 1

for i in range(100000):        
    s[i+1] += s[i]

for i in range(q):
    l,r=map(int,input().split())
    print(s[r]-s[l-1])
Buggy python submission (verdict: Runtime Error):
import collections
n = int(input())

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

a = sorted(a)
b = list(set(a))
c=collections.Counter(a)

ans = 1
for i in range(1,n-1):
    cnt = 0
    if abs(b[i]-b[i-1]) <= 1 and abs(b[i]-b[i+1]) <= 1:
        cnt += c[b[i]] + c[b[i-1]] + c[b[i+1]]
        
    ans = max(ans,cnt)

print(ans)

Fixed submission:
n = int(input())

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

l = [0]*100005 

for i in a:
    l[i] += 1
    
ans = 0
for i in range(1,99999):
    ans = max(ans,l[i] + l[i-1] + l[i+1])

print(ans)
Buggy python submission (verdict: Runtime Error):
n=int(input())

max=0
for i in range(1,n+1):
    count=0
    x=i
    while i%2 == 0:
        count +=1
        i /=2
        
    if count > max:
        max=count
        ans=x
        
print(ans)   

Fixed submission:
n=int(input())

for i in range(8):
    if 2**i <= n:
        ans=2**i

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = list(map(int,input().split()))

ans = abs(a[0]-sum(a[1:]))
x = 0
for i in range(n-1):
    x +=a[i]
    y = sum(a) - x
    ans = min(ans,abs(x-y))
    
print(ans)

Fixed submission:
n = int(input())

a = list(map(int,input().split()))
total = sum(a)

ans = 10000000000000000000
x = 0
for i in range(n):
    x += a[i]
    if i  < n-1:
        ans = min(ans,abs(total-2*x))

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
a=[]
for i in range(n):
    b=int(input())
    a.append(b)

count=1
c=a[0]

while c != 2:
    c=a[c-1]
    if a[c-1] == b:
        print(-1)
        exit()
    b=c
    count +=1 

print(count)    

Fixed submission:
n=int(input())
a=[int(input()) for i in range(n)]

count=1

for i in range(n):
    if count == 2:
        print(i)
        exit()
    count=a[count-1]

print(-1)
Buggy python submission (verdict: Runtime Error):
n = int(input())

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

l = [0]*9

for i in a:
    
    l[i//400] +=1

b = [i for i in l[:8] if i > 0]

mx = len(b)+l[8]
mn = len(b)
print(mn,mx)

Fixed submission:
n = int(input())

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

l = [0]*9


for i in a:
    if i >= 3200:
        l[8] +=1
    else:    
        l[i//400] +=1

b = [i for i in l[:8] if i > 0]
mx = 0
mn = 0

if len(b) >= 1:
    mx = len(b)+l[8]
    mn = len(b)
else:
    mx = len(b)+l[8]
    mn = 1
    
print(mn,mx)
Buggy python submission (verdict: Time Limit Exceeded):
k,s=map(int,input().split())

count=0
for x in range(k+1):
    for y in range(k+1):
        for z in range(k+1):
            if x+y+z == s:
                count +=1
                
print(count)

Fixed submission:
k,s=map(int,input().split())

count=0
for x in range(k+1):
    for y in range(k+1):    
        if s-(x+y) <= k and  s-(x+y) >= 0: 
            count +=1
        
                
print(count)
Buggy python submission (verdict: Runtime Error):
n = int(input())
d = [list(map(int, input().split())) for _ in range(n)]
for i in range(n-3):
    exist = True
    for j in range(3):
        if not d[i+j][0] == d[i+j][1]:
            exist = False
    if exist:
        break
if exist:
    print('Yes')
else:
    print('No')

Fixed submission:
n = int(input())
d = [list(map(int, input().split())) for _ in range(n)]

exist = False
for i in range(n-2):
    for j in range(3):
        if d[i+j][0] != d[i+j][1]:
            break
    else:
        exist = True
if exist:
    print('Yes')
else:
    print('No')
Buggy python submission (verdict: Time Limit Exceeded):
import math

a, b, n = map(int, input().split())
ans = math.floor(a*n/b) - a*math.floor(n/b)
x = b-1
while x <= n:
    ans = max(ans, math.floor(a*x/b) - a*math.floor(x/b))
    x += b
print(ans)

Fixed submission:
import math
a, b, n = map(int, input().split())
x = min(b-1, n)
ans = math.floor(a*x/b) - a*math.floor(x/b)
print(ans)
Buggy python submission (verdict: Runtime Error):
l = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
k = int(input())
print(l[k+1])

Fixed submission:
l = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
k = int(input())
print(l[k-1])
Buggy python submission (verdict: Time Limit Exceeded):
import fractions
from functools import reduce

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

def lcm_base(x, y):
    return (x * y) // gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)


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

x = lcm(*A)
ans = 0
for b in [x//a for a in A]:
    ans = (ans + b) % mod
print(ans)

Fixed submission:
import fractions
from functools import reduce

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

def lcm_base(x, y):
    return (x * y) // gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

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

x = lcm(*A) % mod
ans = sum([x * pow(a, mod-2, mod) for a in A]) % mod
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import fractions
from functools import reduce

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

def lcm_base(x, y):
    return (x * y) // gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)


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

x = lcm(*A)
ans = sum([x//a for a in A]) % mod
print(ans)

Fixed submission:
import fractions
from functools import reduce

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

def lcm_base(x, y):
    return (x * y) // gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

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

x = lcm(*A) % mod
ans = sum([x * pow(a, mod-2, mod) for a in A]) % mod
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import copy

H, W = map(int, input().split())
S = [[0 if c == '.' else 1 for c in input()] for _ in range(H)]

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

def bfs(y, x):
    q = [[y,x,0]]
    ST = copy.deepcopy(S)
    res = -1
    while len(q):
        ST[y][x] = 1
        y, x, d = q.pop(0);
        res = max(res, d)
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if not (0 <= ny <= H-1 and 0 <= nx <= W-1): continue
            if ST[ny][nx] == 1: continue
            q.append([ny,nx,d+1])
    return res

ans = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == 1: continue
        ans = max(ans, bfs(i,j))
print(ans)

Fixed submission:
H, W = map(int, input().split())
S = [input() for _ in range(H)]

dy = [0, 1, 0, -1]
dx = [1, 0, -1, 0]
INF = 10**9 + 7

def bfs(y, x):
    res = 0
    q = [[y,x]]
    D = [[INF for _ in range(W)] for _ in range(H)]
    D[y][x] = 0
    while len(q):
        y, x = q.pop(0);
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if not (0 <= ny <= H-1 and 0 <= nx <= W-1): continue
            if S[ny][nx] == '#': continue
            if D[ny][nx] > D[y][x] + 1:
                D[ny][nx] = D[y][x] + 1
                q.append([ny,nx])
                res = max(res, D[ny][nx])
    return res

ans = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == '#': continue
        ans = max(ans, bfs(i,j))
print(ans)
Buggy python submission (verdict: Runtime Error):
import math

n = int(input())
x = [0] + list(map(int, input().split()))
mod = 10**9 + 7

f = [1] * (n+1)
for i in range(1,n+1):
    f[i] = f[i-1] * i % mod

s = [0] + [pow(i, mod-2, mod) for i in range(1,n+1)]
for i in range(n):
    s[i+1] = (s[i+1] + s[i]) % mod

ans = 0.0
for i in range(1,n):
    ans += ((x[i+1] - x[i]) * s[i]) % mod
ans = int(ans * math.factorial(n-1)) % mod
print(ans)

Fixed submission:
import math

n = int(input())
x = [0] + list(map(int, input().split()))
mod = 10**9 + 7

s = [pow(i, mod-2, mod) for i in range(0,n+1)]
for i in range(n):
    s[i+1] = (s[i+1] + s[i]) % mod

ans = 0
for i in range(1,n):
    ans += ((x[i+1] - x[i]) * s[i]) % mod
ans = int(ans * math.factorial(n-1)) % mod
print(ans)
Buggy python submission (verdict: Runtime Error):
import math
import fractions
from functools import reduce

def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

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

l = lcm(*[a // 2 for a in A])
if l <= 0 or any([(2*l / a - 1) % 2 != 0 and a % 2 == 0 for a in A]):
    print(0)
else:
    ans = math.floor((m + l) / (2*l))
    print(ans)

Fixed submission:
import math
import fractions
from functools import reduce

def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

def f(x):
    res = 0
    while x % 2 == 0:
        res += 1
        x /= 2
    return res

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

l = lcm(*[a // 2 for a in A])
ans = math.floor((m + l) / (2*l))
if len(set([f(a) for a in A])) != 1:
    print(0)
else:
    print(ans)

Buggy python submission (verdict: Runtime Error):
import math
import fractions
from functools import reduce

def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

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

l = lcm(*[a // 2 for a in A])
if l <= 0 or any([(2*l / a - 1) % 2 != 0 for a in A]):
    print(0)
else:
    ans = math.floor((m + l) / (2*l))
    print(ans)

Fixed submission:
import math
import fractions
from functools import reduce

def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

def f(x):
    res = 0
    while x % 2 == 0:
        res += 1
        x /= 2
    return res

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

l = lcm(*[a // 2 for a in A])
ans = math.floor((m + l) / (2*l))
if len(set([f(a) for a in A])) != 1:
    print(0)
else:
    print(ans)

Buggy python submission (verdict: Runtime Error):
import math
import fractions
from functools import reduce

def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

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

l = lcm(*[a // 2 for a in A])
ans = math.floor((m + l) / (2*l))
if any([(2*l / a - 1) % 2 != 0 for a in A]):
    print(0)
else:
    print(ans)

Fixed submission:
import math
import fractions
from functools import reduce

def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

def f(x):
    res = 0
    while x % 2 == 0:
        res += 1
        x /= 2
    return res

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

l = lcm(*[a // 2 for a in A])
ans = math.floor((m + l) / (2*l))
if len(set([f(a) for a in A])) != 1:
    print(0)
else:
    print(ans)
Buggy python submission (verdict: Runtime Error):
import math

def lcm(x, y):
    return (x * y) // math.gcd(x, y)

a, b = map(int, input().split())
print(lcm(a, b))

Fixed submission:
import fractions

def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)

a, b = map(int, input().split())
print(lcm(a, b))
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
s = input()

l = [30010] * 11
r = [-1] * 11
for i in range(n):
    c = int(s[i])
    r[c] = max(r[c], i)
    l[c] = min(l[c], i)
st = set([])
for i in range(n):
    c = int(s[i])
    for j in range(10):
        for k in range(10):
            if l[j] < i < r[k]:
                number = chr(j) + s[i] + chr(k)
                st.add(number)
print(len(st))

Fixed submission:
n = int(input())
s = input()

l = [30010] * 11
r = [-1] * 11
for i in range(n):
    c = int(s[i])
    r[c] = max(r[c], i)
    l[c] = min(l[c], i)
st = set([])
for i in range(n):
    c = int(s[i])
    for j in range(10):
        for k in range(10):
            if l[j] < i < r[k]:
                number = chr(j) + s[i] + chr(k)
                st.add(number)
print(len(st))

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
s = input()

l = [30010] * 11
r = [-1] * 11
for i in range(n):
    c = int(s[i])
    r[c] = max(r[c], i)
    l[c] = min(l[c], i)
st = set([])
for i in range(n):
    c = int(s[i])
    for j in range(10):
        for k in range(10):
            if l[j] < i < r[k]:
                number = chr(j) + s[i] + chr(k)
                st.add(number)
print(len(st))

Fixed submission:
n = int(input())
s = input()

l = [30010] * 11
r = [-1] * 11
for i in range(n):
    c = int(s[i])
    r[c] = max(r[c], i)
    l[c] = min(l[c], i)
st = set([])
for i in range(n):
    c = int(s[i])
    for j in range(10):
        for k in range(10):
            if l[j] < i < r[k]:
                number = chr(j) + s[i] + chr(k)
                st.add(number)
print(len(st))
Buggy python submission (verdict: Runtime Error):
n, k = map(int, input().split())
A = list(map(int, input().split()))
S = [0] * (n + 1)
for i in range(n):
    S[i+1] = S[i] + A[i]

f = lambda n: (S[n] - n) % k
C = [0] * k
ans = 0
for i in range(n):
    C[f(i)] += 1
    j = i - k + 1
    if 0 <= j:
        C[f(j)] -= 1
    ans += C[f(i+1)]
print(ans)

Fixed submission:
from collections import defaultdict

n, k = map(int, input().split())
A = list(map(int, input().split()))
S = [0] * (n + 1)
for i in range(n):
    S[i+1] = S[i] + A[i]

f = lambda n: (S[n] - n) % k
C = defaultdict(int)
ans = 0
for i in range(n):
    C[f(i)] += 1
    j = i - k + 1
    if 0 <= j:
        C[f(j)] -= 1
    ans += C[f(i+1)]
print(ans)

Buggy python submission (verdict: Runtime Error):
n, k = map(int, input().split())
A = list(map(int, input().split()))
S = [0] * (n + 1)
for i in range(n):
    S[i+1] = S[i] + A[i]

C = [0] * k
ans = 0
for i in range(n+1):
    j = i - k
    mi = (S[i] - i) % k
    if j >= 0:
        mj = (S[j] - j) % k
        C[mj] -= 1
    ans += C[mi]
    C[mi] += 1
print(ans)

Fixed submission:
from collections import defaultdict

n, k = map(int, input().split())
A = list(map(int, input().split()))
S = [0] * (n + 1)
for i in range(n):
    S[i+1] = S[i] + A[i]

f = lambda n: (S[n] - n) % k
C = defaultdict(int)
ans = 0
for i in range(n):
    C[f(i)] += 1
    j = i - k + 1
    if 0 <= j:
        C[f(j)] -= 1
    ans += C[f(i+1)]
print(ans)

Buggy python submission (verdict: Runtime Error):
n, k = map(int, input().split())
A = list(map(int, input().split()))
S = [0] * (n + 1)
for i in range(n):
    S[i+1] = S[i] + A[i]

C = [0] * k
ans = 0
for i in range(n+1):
    j = i - k
    mi = (S[i] - i) % k
    mj = (S[j] - j) % k
    if j >= 0:
        C[mj] -= 1
    ans += C[mi]
    C[mi] += 1
print(ans)

Fixed submission:
from collections import defaultdict

n, k = map(int, input().split())
A = list(map(int, input().split()))
S = [0] * (n + 1)
for i in range(n):
    S[i+1] = S[i] + A[i]

f = lambda n: (S[n] - n) % k
C = defaultdict(int)
ans = 0
for i in range(n):
    C[f(i)] += 1
    j = i - k + 1
    if 0 <= j:
        C[f(j)] -= 1
    ans += C[f(i+1)]
print(ans)

Buggy python submission (verdict: Runtime Error):
from collections import defaultdict

n, k = map(int, input().split())
A = list(map(int, input().split()))
S = [0] * (n + 1)
for i in range(n):
    S[i+1] = S[i] + A[i]

C = defaultdict(int)
ans = 0
for i in range(n+1):
    j = i - k
    mi = (S[i] - i) % k
    mj = (S[j] - j) % k
    if j >= 0:
        C[mj] -= 1
    ans += C[mi]
    C[mi] += 1

Fixed submission:
from collections import defaultdict

n, k = map(int, input().split())
A = list(map(int, input().split()))
S = [0] * (n + 1)
for i in range(n):
    S[i+1] = S[i] + A[i]

f = lambda n: (S[n] - n) % k
C = defaultdict(int)
ans = 0
for i in range(n):
    C[f(i)] += 1
    j = i - k + 1
    if 0 <= j:
        C[f(j)] -= 1
    ans += C[f(i+1)]
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
from functools import reduce
from itertools import combinations

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

n = int(input())
factor = [1] + prime_factorize(n)

ans = int(1e13)
for i in range(1, len(factor)//2 + 1):
    for c in combinations(factor, i):
        a = reduce(lambda x,y:x*y, c)
        b = n // a
        ans = min(ans, a + b - 2)
print(ans)

Fixed submission:
def factorize(n):
    a = []
    f = 2
    while f * f <= n:
        if n % f == 0:
            a.append((f, n//f))
        f += 1
    if not len(a):
        a.append((1, n))
    return a

n = int(input())
factor = factorize(n)

ans = int(1e13)
for fa in factor:
    a, b = fa
    ans = min(ans, a + b - 2)
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from functools import reduce
from itertools import combinations

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

n = int(input())
factor = [1] + prime_factorize(n)

ans = int(1e13)
for i in range(1, len(factor)//2 + 1):
    for c in combinations(factor, i):
        a = reduce(lambda x,y:x*y, c)
        b = n // a
        ans = min(ans, a + b - 2)
print(ans)

Fixed submission:
def factorize(n):
    a = []
    f = 2
    while f * f <= n:
        if n % f == 0:
            a.append((f, n//f))
        f += 1
    if not len(a):
        a.append((1, n))
    return a

n = int(input())
factor = factorize(n)

ans = int(1e13)
for fa in factor:
    a, b = fa
    ans = min(ans, a + b - 2)
print(ans)