Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
import copy

inf = 10 ** 8


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

def tolist(n):
    nn = n
    ret = [0] * N
    for i in range(N):
        ret[i] = nn % 2
        nn //= 2
    return ret

def tonum(l):
    ret = 0
    for i in range(N):
        ret += l[i] * (2**i)
    return ret

def union(l1,l2):
    ret = [0] * N
    for i in range(N):
        ret[i] = min(l1[i] + l2[i],1) 
    return tonum(ret)



cost = [0] * M
data = [[0]*N for i in range(M)]

for i in range(M):
    a,b = map(int,input().split())
    cost[i] = a
    c = list(map(int,input().split()))
    for x in c:
        x -= 1
        data[i][x] = 1

dp = [inf]*(2**N)


for j in range(2**N):
    if union(tolist(j),data[0]) == tonum(data[0]):
        dp[j] = cost[0]

dp[0] = 0

for i in range(1,M):
    #print(dp)
    for j in range(2**N):
        #print(dp)
        ###このjは一つ前のiのものであることに注意
        l = tolist(j)
        dp[union(l,data[i])] = min(dp[union(l,data[i])], dp[j]+cost[i])
        

#print(dp)
if dp[2**N -1] == inf:
    print(-1)
else:
    print(dp[2**N -1])


Fixed submission:
### 提出 #10098255

##頭良すぎて草

##x | y    x と y のビット単位 論理和
##x ^ y    x と y のビット単位 排他的論理和
##x & y    x と y のビット単位 論理積
##x << n   x の n ビット左シフト
##x >> n   x の n ビット右シフト
##~x       x のビット反転

n,m=map(int,input().split())
p=2**n
inf=10**9
dp=[inf]*p
dp[0]=0
for i in range(m):
    a,b=map(int,input().split())
    c=sum([2**(j-1) for j in list(map(int,input().split()))])
    for k in range(p):
        if dp[k|c]>dp[k]+a:
            dp[k|c]=dp[k]+a
print(dp[-1] if dp[-1]!=inf else -1)

Buggy python submission (verdict: Time Limit Exceeded):
import copy

inf = 10 ** 8


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

def tolist(n):
    nn = n
    ret = [0] * N
    for i in range(N):
        ret[i] = nn % 2
        nn //= 2
    return ret

def tonum(l):
    ret = 0
    for i in range(N):
        ret += l[i] * (2**i)
    return ret

def union(l1,l2):
    ret = [0] * N
    for i in range(N):
        ret[i] = min(l1[i] + l2[i],1) 
    return tonum(ret)



cost = [0] * M
data = [[0]*N for i in range(M)]

for i in range(M):
    a,b = map(int,input().split())
    cost[i] = a
    c = list(map(int,input().split()))
    for x in c:
        x -= 1
        data[i][x] = 1

dp = [inf]*(2**N)


for j in range(2**N):
    if union(tolist(j),data[0]) == tonum(data[0]):
        dp[j] = cost[0]

dp[0] = 0

for i in range(1,M):
    #print(dp)
    for j in range(2**N):
        #print(dp)
        ###このjは一つ前のiのものであることに注意
        l = tolist(j)
        dp[union(l,data[i])] = min(dp[union(l,data[i])], dp[j]+cost[i])
        

#print(dp)
if dp[2**N -1] == inf:
    print(-1)
else:
    print(dp[2**N -1])


Fixed submission:
### 提出 #10098255

##頭良すぎて草

##x | y    x と y のビット単位 論理和
##x ^ y    x と y のビット単位 排他的論理和
##x & y    x と y のビット単位 論理積
##x << n   x の n ビット左シフト
##x >> n   x の n ビット右シフト
##~x       x のビット反転

n,m=map(int,input().split())
p=2**n
inf=10**9
dp=[inf]*p
dp[0]=0
for i in range(m):
    a,b=map(int,input().split())
    c=sum([2**(j-1) for j in list(map(int,input().split()))])
    for k in range(p):
        if dp[k|c]>dp[k]+a:
            dp[k|c]=dp[k]+a
print(dp[-1] if dp[-1]!=inf else -1)
Buggy python submission (verdict: Time Limit Exceeded):
import sys

def z_algo(S):
    N = len(S)
    #print(N)
    A = [0]*N
    i = 1; j = 0
    A[0] = l = len(S)
    while i < l:
        while i+j < l and S[j] == S[i+j]:
            j += 1
        if not j:
            i += 1
            continue
        A[i] = j
        k = 1
        while l-i > k < j - A[k]:
            A[i+k] = A[k]
            k += 1
        i += k; j -= k
    #print(A)
    return A

#input = sys.stdin.readline

N = int(input())
S = list(input())
ans = 0

for t in range(N):
    L = z_algo(S[t:])
    for u in range(len(L)):
        if L[u] <= u:
            ans = max(ans,L[u])

print(ans)

Fixed submission:
import sys

def z_algo(S):
    N = len(S)
    #print(N)
    A = [0]*N
    i = 1; j = 0
    A[0] = l = len(S)
    while i < l:
        while i+j < l and S[j] == S[i+j]:
            j += 1
        if not j:
            i += 1
            continue
        A[i] = j
        k = 1
        while l-i > k < j - A[k]:
            A[i+k] = A[k]
            k += 1
        i += k; j -= k
    #print(A)
    return A

#input = sys.stdin.readline

N = int(input())
S = list(input())
ans = 0

for t in range(N):
    L = z_algo(S[t:])
    for u in range(len(L)):
        if L[u] <= u:
            ans = max(ans,L[u])

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
alpha = list("abcdefghijklmnopqrstuvwxyz")

s = list(str(input()))
t = list(str(input()))

info = [[0] * len(s) for _ in range(26)]

ss = s[:] * 2

for i in range(26):
    last = -1
    for j in range(len(ss)-1,-1,-1):
        info[i][j%(len(s))] = last
        if ss[j] ==  alpha[i]:
            last = j % (len(s))
#print(info)

count = 0
num = 0
place = -1

while num < len(t):
    x = info[alpha.index(t[num])][place]
    if x > place:
        count += x - place
    else:
        count += x - place + len(s)
    place = x
    num += 1

s_ = [0] * 26
t_ = [0] * 26
for lets in s:
    s_[alpha.index(lets)] = 1
for lett in t:
    t_[alpha.index(lett)] = 1
for i in range(26):
    if s_[i] < t_[i]:
        count = -1
        break

print(count)

Fixed submission:
alpha = list("abcdefghijklmnopqrstuvwxyz")

s = list(str(input()))
t = list(str(input()))

info = [[0] * len(s) for _ in range(26)]

ss = s[:] * 2

for i in range(26):
    last = -1
    for j in range(len(ss)-1,-1,-1):
        info[i][j%(len(s))] = last
        if ss[j] ==  alpha[i]:
            last = j % (len(s))
#print(info)

count = 0
num = 0
place = -1

while num < len(t):
    x = info[alpha.index(t[num])][place]
    if x > place:
        count += x - place
    else:
        count += x - place + len(s)
    place = x
    num += 1

s_ = [0] * 26
t_ = [0] * 26
for lets in s:
    s_[alpha.index(lets)] = 1
for lett in t:
    t_[alpha.index(lett)] = 1
for i in range(26):
    if s_[i] < t_[i]:
        count = -1
        break

print(count)
Buggy python submission (verdict: Runtime Error):
s = str(input())

l = list(s)

info = [0]

for i in range(1,len(l)):
    if l[i] == l[i-1]:
        info[-1] += 1
    else:
        info.append(1)

ans = 0
for j in range(0,len(info)):
    if info[j] % 3 == 0:
        ans += 2*(info[j]//3)
    elif info[j] % 3 == 1:
        ans += 2*(info[j]//3) + 1
    else:
        if j < len(info):
            ans += 2*(info[j]//3) + 2
            info[j+1] -= 1
        else:
            ans += 2*(info[j]//3) + 1

print(ans)

Fixed submission:
s = str(input())

l = list(s)

info = [1]

for i in range(1,len(l)):
    if l[i] == l[i-1]:
        info[-1] += 1
    else:
        info.append(1)

ans = 0
for j in range(0,len(info)):
    if info[j] % 3 == 0:
        ans += 2*(info[j]//3)
    elif info[j] % 3 == 1:
        ans += 2*(info[j]//3) + 1
    else:
        if j < len(info)-1:
            ans += 2*(info[j]//3) + 2
            info[j+1] -= 1
        else:
            ans += 2*(info[j]//3) + 1

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

info = [0] * (n+1)

for i in range(0,n):
    count = 0
    for j in range(n-i,n+1):
        count += info[j]
    if count != a[n-i]:
        info[n-i] = 1

ans = []

for k in range(1,n+1):
    if info[k] == 1:
        ans.append(k)

print(len(ans))
if ans != []:
    print(" ".join(map(str,ans)))

Fixed submission:
n = int(input())
a = [0] + list(map(int,input().split()))

info = [0] * (n+1)

for i in range(0,n):
    count = 0
    for j in range(2,n//(n-i) + 1):
        count += info[(n-i)*j]
    if count % 2 != a[n-i]:
        info[n-i] = 1

ans = []

for k in range(1,n+1):
    if info[k] == 1:
        ans.append(k)

print(len(ans))
print(" ".join(map(str,ans)))

Buggy python submission (verdict: Runtime Error):
n = int(input().split())
a = [0] + list(map(int,input().split()))

info = [0] * (n+1)

for i in range(0,n):
    count = 0
    for j in range(n-i,n+1):
        count += info[j]
    if count != a[n-i]:
        info[n-i] = 1

ans = []

for k in range(1,n+1):
    if info[k] == 1:
        ans.append(k)

print(len(ans))
print(ans)

Fixed submission:
n = int(input())
a = [0] + list(map(int,input().split()))

info = [0] * (n+1)

for i in range(0,n):
    count = 0
    for j in range(2,n//(n-i) + 1):
        count += info[(n-i)*j]
    if count % 2 != a[n-i]:
        info[n-i] = 1

ans = []

for k in range(1,n+1):
    if info[k] == 1:
        ans.append(k)

print(len(ans))
print(" ".join(map(str,ans)))

Buggy python submission (verdict: Runtime Error):
n = int(input().split())
a = [0] + list(map(int,input().split()))

info = [0] * (n+1)

for i in range(0,n):
    count = 0
    for j in range(n-i,n+1):
        count += info[j]
    if count != a[n-i]:
        info[n-i] = 1

ans = []

for k in range(1,n+1):
    if info[k] == 1:
        ans.append(k)

print(len(ans))
print(ans)

Fixed submission:
n = int(input())
a = [0] + list(map(int,input().split()))

info = [0] * (n+1)

for i in range(0,n):
    count = 0
    for j in range(2,n//(n-i) + 1):
        count += info[(n-i)*j]
    if count % 2 != a[n-i]:
        info[n-i] = 1

ans = []

for k in range(1,n+1):
    if info[k] == 1:
        ans.append(k)

print(len(ans))
print(" ".join(map(str,ans)))
Buggy python submission (verdict: Time Limit Exceeded):
MOD = 10 ** 9 + 7

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

perm = [0] * (10**5)
perm[0] = 1
for l in range(1,10 ** 5):
    perm[l] = (perm[l-1] * (K-l-1)) % MOD

info = [[] for _ in range(N)]

def intminus(t):
    return int(t)-1

for i in range(N-1):
    a,b = map(intminus,input().split())
    info[a].append(b)
    info[b].append(a)

count = 1

for j in range(1+len(info[0])):
    count = (count * (K-j)) % MOD

stack = info[0][:]
visited = [0] * N
visited[0] = 1

while stack:
    x = stack.pop(-1)
    if visited[x] == 1:
        continue
    count = (count * perm[len(info[x])-1]) % MOD
    stack = stack + info[x]
    visited[x] = 1
    #print(stack,count)

print(count)

Fixed submission:
MOD = 10 ** 9 + 7

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

perm = [0] * (10**5)
perm[0] = 1
for l in range(1,10 ** 5):
    perm[l] = (perm[l-1] * (K-l-1)) % MOD

info = [[] for _ in range(N)]

def intminus(t):
    return int(t)-1

for i in range(N-1):
    a,b = map(intminus,input().split())
    info[a].append(b)
    info[b].append(a)

count = 1

for j in range(1+len(info[0])):
    count = (count * (K-j)) % MOD

stack = []
for p in info[0]:
    stack.append([0,p])

while stack:
    x = stack.pop(-1)
    count = (count * perm[len(info[x[1]])-1]) % MOD
    for xx in info[x[1]]:
        if xx == x[0]:continue
        stack.append([x[1],xx])

print(count)

Buggy python submission (verdict: Time Limit Exceeded):
MOD = 10 ** 9 + 7

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

perm = [0] * (10**5)
perm[0] = 1
for l in range(1,10 ** 5):
    perm[l] = (perm[l-1] * (K-l-1)) % MOD

info = [[] for _ in range(N)]

def intminus(t):
    return int(t)-1

for i in range(N-1):
    a,b = map(intminus,input().split())
    info[a].append(b)
    info[b].append(a)

count = 1

for j in range(1+len(info[0])):
    count = (count * (K-j)) % MOD

stack = info[0][:]
visited = [0] * N
visited[0] = 1

while stack:
    x = stack.pop(-1)
    if visited[x] == 1:
        continue
    count = (count * perm[len(info[x])-1]) % MOD
    stack = stack + info[x]
    visited[x] = 1
    #print(stack,count)

print(count)

Fixed submission:
MOD = 10 ** 9 + 7

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

perm = [0] * (10**5)
perm[0] = 1
for l in range(1,10 ** 5):
    perm[l] = (perm[l-1] * (K-l-1)) % MOD

info = [[] for _ in range(N)]

def intminus(t):
    return int(t)-1

for i in range(N-1):
    a,b = map(intminus,input().split())
    info[a].append(b)
    info[b].append(a)

count = 1

for j in range(1+len(info[0])):
    count = (count * (K-j)) % MOD

stack = []
for p in info[0]:
    stack.append([0,p])

while stack:
    x = stack.pop(-1)
    count = (count * perm[len(info[x[1]])-1]) % MOD
    for xx in info[x[1]]:
        if xx == x[0]:continue
        stack.append([x[1],xx])

print(count)
Buggy python submission (verdict: Runtime Error):
import math

def antidiv(x,l,c,d):
    if x == l:
        return l - (l // c) - (l // d) + 1
    else:
        return x - (x // c) - (x // d) 

a,b,c,d = map(int,input().split())

l = (c*d)//math.gcd(c,d)


aq = a // l
ar = a % l
bq = b // l
br = b % l

qq = bq - aq - 1
r1 = antidiv(l,l,c,d) - antidiv(ar-1,l,c,d)
r2 = antidiv(br,l,c,d)

ans = qq * antidiv(l,l,c,d) + r1 + r2

print(ans)


Fixed submission:
import fractions

def antidiv(x,l,c,d):
    if x == l or x < 0:
        return l - (l // c) - (l // d) + 1
    else:
        return x - (x // c) - (x // d) 

a,b,c,d = map(int,input().split())

l = (c*d)//fractions.gcd(c,d)


aq = a // l
ar = a % l
bq = b // l
br = b % l
#print(br)

qq = bq - aq - 1
r1 = antidiv(l,l,c,d) - antidiv(ar-1,l,c,d)
r2 = antidiv(br,l,c,d)

if ar!=0:
    ans = qq * antidiv(l,l,c,d) + r1 + r2
else:
    ans = (qq+1) * antidiv(l,l,c,d) + r1 + r2


print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
l = int(input())

lst = list(str(l))
lin = list(map(int,lst[:]))

#print(l)
#print(lst)
#print(lin)

le = len(lin)

dp1 = [0] * le#A+BがL以下だとわかっている
dp2 = [0] * le#A+BがL以下だとわかっていない

dp1[0] = 1
dp2[0] = 2

for i in range(1,le):
    if lin[i] == 0:
        dp1[i] = (dp1[i-1] * 3)%(10**9+7)
        dp2[i] = dp2[i-1]
    else:
        dp1[i] = (dp1[i-1] * 3 + dp2[i-1])%(10**9+7)
        dp2[i] = dp2[i-1] * 2

print((dp1[-1]+dp2[-1])%(10**9+7))



Fixed submission:
L = list(map(int,list(input())))
num = len(L)
mod = 10 ** 9 + 7

dp1 = [0] * num
#AおよびBの値の上からk桁目(k>=0)までを確定させ、その時点で
#既にA+BがL以下であることが分かっているような値組(A, B)の個数
dp2 = [0] * num
#AおよびBの値の上からk桁目(k>=0)までを確定させ、その時点では
#まだA+BがL以下になるかどうか分かっていないような値組 (A, B) の個数

dp1[0] = 1 #(A,B)=(0,0)
dp2[0] = 2 #(A,B)=(1,0),(0,1)

for i in range(1,num):
    if L[i] == 1:
        dp1[i] = dp1[i-1] * 3 + dp2[i-1]
        dp2[i] = dp2[i-1] * 2
    else:
        dp1[i] = dp1[i-1] * 3
        dp2[i] = dp2[i-1]
    dp1[i] %= mod
    dp2[i] %= mod

print((dp1[num-1] + dp2[num-1])%mod)

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

lst = list(str(l))
lin = list(map(int,lst[:]))

#print(l)
#print(lst)
#print(lin)

le = len(lin)

dp1 = [0] * le#A+BがL以下だとわかっている
dp2 = [0] * le#A+BがL以下だとわかっていない

dp1[0] = 1
dp2[0] = 2

for i in range(1,le):
    if lin[i] == 0:
        dp1[i] = (dp1[i-1] * 3)%(10**9+7)
        dp2[i] = dp2[i-1]
    else:
        dp1[i] = (dp1[i-1] * 3 + dp2[i-1])%(10**9+7)
        dp2[i] = dp2[i-1] * 2

print((dp1[-1]+dp2[-1])%(10**9+7))


Fixed submission:
L = list(map(int,list(input())))
num = len(L)
mod = 10 ** 9 + 7

dp1 = [0] * num
#AおよびBの値の上からk桁目(k>=0)までを確定させ、その時点で
#既にA+BがL以下であることが分かっているような値組(A, B)の個数
dp2 = [0] * num
#AおよびBの値の上からk桁目(k>=0)までを確定させ、その時点では
#まだA+BがL以下になるかどうか分かっていないような値組 (A, B) の個数

dp1[0] = 1 #(A,B)=(0,0)
dp2[0] = 2 #(A,B)=(1,0),(0,1)

for i in range(1,num):
    if L[i] == 1:
        dp1[i] = dp1[i-1] * 3 + dp2[i-1]
        dp2[i] = dp2[i-1] * 2
    else:
        dp1[i] = dp1[i-1] * 3
        dp2[i] = dp2[i-1]
    dp1[i] %= mod
    dp2[i] %= mod

print((dp1[num-1] + dp2[num-1])%mod)

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

lst = list(str(l))
lin = list(map(int,lst[:]))

#print(l)
#print(lst)
#print(lin)

le = len(lin)

dp1 = [0] * le#A+BがL以下だとわかっている
dp2 = [0] * le#A+BがL以下だとわかっていない

dp1[0] = 1
dp2[0] = 2

for i in range(1,le):
    if lin[i] == 0:
        dp1[i] = dp1[i-1] * 3
        dp2[i] = dp2[i-1]
    else:
        dp1[i] = dp1[i-1] * 3 + dp2[i-1]
        dp2[i] = dp2[i-1] * 2

print((dp1[-1]+dp2[-1])%(10**9+7))



Fixed submission:
L = list(map(int,list(input())))
num = len(L)
mod = 10 ** 9 + 7

dp1 = [0] * num
#AおよびBの値の上からk桁目(k>=0)までを確定させ、その時点で
#既にA+BがL以下であることが分かっているような値組(A, B)の個数
dp2 = [0] * num
#AおよびBの値の上からk桁目(k>=0)までを確定させ、その時点では
#まだA+BがL以下になるかどうか分かっていないような値組 (A, B) の個数

dp1[0] = 1 #(A,B)=(0,0)
dp2[0] = 2 #(A,B)=(1,0),(0,1)

for i in range(1,num):
    if L[i] == 1:
        dp1[i] = dp1[i-1] * 3 + dp2[i-1]
        dp2[i] = dp2[i-1] * 2
    else:
        dp1[i] = dp1[i-1] * 3
        dp2[i] = dp2[i-1]
    dp1[i] %= mod
    dp2[i] %= mod

print((dp1[num-1] + dp2[num-1])%mod)
Buggy python submission (verdict: Runtime Error):
import fraction

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

left = [0] * N
right = [0] * N

left[0] = A[0]
for i in range(1,N):
    left[i] = fraction.gcd(left[i-1],A[i])

right[N-1] = A[N-1]
for j in range(N-2,0,-1):
    right[j] = fraction.gcd(A[j],right[j+1])

can = [0] * N
can[0] = right[1]
for k in range(1,N-1):
    can[k] = fraction.gcd(left[k-1],right[k+1])
can[N-1] = left[N-2]

print(max(can))

Fixed submission:
import fractions

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

left = [0] * N
right = [0] * N

left[0] = A[0]
for i in range(1,N):
    left[i] = fractions.gcd(left[i-1],A[i])

right[N-1] = A[N-1]
for j in range(N-2,0,-1):
    right[j] = fractions.gcd(A[j],right[j+1])

can = [0] * N
can[0] = right[1]
for k in range(1,N-1):
    can[k] = fractions.gcd(left[k-1],right[k+1])
can[N-1] = left[N-2]

print(max(can))
Buggy python submission (verdict: Time Limit Exceeded):
n, k = map(int,input().split())
s = list(map(int,list((input()))))

#print(s)

status = s[0]
count = 1
info = []

for i in range(1,n):
    if s[i] == status:
        count = count + 1
    else:
        info.append([status,count])
        count = 1
        status = s[i]

info.append([status,count])

#print(info)

c = 0
for x in range(0,len(info)):
    if info[x][0] == 0:
        c = c + 1

#print(c)

if c <= k:
    print(n)

else:
    p = 0
    l = []

    if s[0] == 0:
        while 2*(p+k-1) < len(info):
            w = 0
            for q in range(2*p-1,2*(p+k)):
                if q >= 0 and q < len(info):
                    w += info[q][1]
            l.append(w)
            p += 1

    else:
        while 2*(p+k-1)+1 < len(info):
            w = 0
            for q in range(2*p,2*(p+k)+1):
                if q >= 0 and q < len(info):
                    w += info[q][1]
            l.append(w)
            p += 1
    print(max(l))


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

l = [0]

for i in range(0,n-1):
    if s[i] != s[i+1]:
        l.append(i+1)

t = len(l)

for x in range(0,2*k+1):
    l.append(n)

#print(l)

can = []

for j in range(0,t):
    if s[l[j]] == 0:
        can.append(l[j+2*k]-l[j])
    elif s[l[j]] == 1:
        can.append(l[j+2*k+1]-l[j])
    else:
        break

#print(can)
print(max(can))
Buggy python submission (verdict: Runtime Error):
import heapq

x,y,z,k = map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
c = list(map(int,input().split()))

a.sort(reverse = True)
b.sort(reverse = True)
c.sort(reverse = True)

l = []

for p in range(0,x):
    for q in range(0,y):
        for r in range(0,z):
            if a[p]+b[q]+c[r] <= l[0]:
                break
            elif len(l) > k:
                heapq.heappushpop(l,a[p]+b[q]+c[r])
            else:
                heapq.heappush(l,a[p]+b[q]+c[r])

l.sort()

for i in range(1,k+1):
    print(l[-i])

Fixed submission:
import heapq

x,y,z,k = map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
c = list(map(int,input().split()))

a.sort(reverse = True)
b.sort(reverse = True)
c.sort(reverse = True)

l = []

for p in range(0,x):
    for q in range(0,y):
        for r in range(0,z):
            if len(l) > k and a[p]+b[q]+c[r] <= l[0]:
                break
            elif len(l) > k:
                heapq.heappushpop(l,a[p]+b[q]+c[r])
            else:
                heapq.heappush(l,a[p]+b[q]+c[r])

l.sort()

for i in range(1,k+1):
    print(l[-i])

Buggy python submission (verdict: Time Limit Exceeded):
import heapq

x,y,z,k = map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
c = list(map(int,input().split()))

l = []

for p in range(0,x):
    for q in range(0,y):
        for r in range(0,z):
            if len(l) > k:
                heapq.heappushpop(l,a[p]+b[q]+c[r])
            else:
                heapq.heappush(l,a[p]+b[q]+c[r])

l.sort()

for i in range(1,k+1):
    print(l[-i])

Fixed submission:
import heapq

x,y,z,k = map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
c = list(map(int,input().split()))

a.sort(reverse = True)
b.sort(reverse = True)
c.sort(reverse = True)

l = []

for p in range(0,x):
    for q in range(0,y):
        for r in range(0,z):
            if len(l) > k and a[p]+b[q]+c[r] <= l[0]:
                break
            elif len(l) > k:
                heapq.heappushpop(l,a[p]+b[q]+c[r])
            else:
                heapq.heappush(l,a[p]+b[q]+c[r])

l.sort()

for i in range(1,k+1):
    print(l[-i])
Buggy python submission (verdict: Time Limit Exceeded):
n, q = map(int,input().split())
s = input()

l = [0] * q
r = [0] * q

for i in range(0,q):
    l[i], r[i] = map(int,input().split())
    l[i] = l[i] -1
    r[i] = r[i] -1

s_list = list(s)

ac_list = []

for i in range(0,n-1):
    if s_list[i] == "A" and s_list[i+1] == "C":
        ac_list.append(i)

#print(ac_list)

for i in range(0,q):
    count = 0
    for j in range(l[i],r[i]):
        if j in ac_list:
            count = count + 1
    print(count)

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

l = [0] * q
r = [0] * q

for i in range(0,q):
    l[i], r[i] = map(int,input().split())
    l[i] = l[i] -1
    r[i] = r[i] -1

s_list = list(s)

ac_list = [0] * (n-1)

for i in range(0,n-1):
    if s_list[i] == "A" and s_list[i+1] == "C":
        ac_list[i] = 1

#print(ac_list)

w = [0] * (n-1)

w[0] = ac_list[0]

for i in range(1,n-1):
    w[i] = w[i-1] + ac_list[i]

#print(w)

for i in range(0,q):
    if l[i] == 0:
        print(w[r[i]-1])
    else:
        print(w[r[i]-1]-w[l[i]-1])

Buggy python submission (verdict: Time Limit Exceeded):
n, q = map(int,input().split())
s = input()

l = [0] * q
r = [0] * q

for i in range(0,q):
    l[i], r[i] = map(int,input().split())
    l[i] = l[i] -1
    r[i] = r[i] -1

s_list = list(s)

ac_list = [0] * (n-1)

for i in range(0,n-1):
    if s_list[i] == "A" and s_list[i+1] == "C":
        ac_list[i] = 1

for i in range(0,q):
    print(sum(ac_list[l[i]:r[i]]))

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

l = [0] * q
r = [0] * q

for i in range(0,q):
    l[i], r[i] = map(int,input().split())
    l[i] = l[i] -1
    r[i] = r[i] -1

s_list = list(s)

ac_list = [0] * (n-1)

for i in range(0,n-1):
    if s_list[i] == "A" and s_list[i+1] == "C":
        ac_list[i] = 1

#print(ac_list)

w = [0] * (n-1)

w[0] = ac_list[0]

for i in range(1,n-1):
    w[i] = w[i-1] + ac_list[i]

#print(w)

for i in range(0,q):
    if l[i] == 0:
        print(w[r[i]-1])
    else:
        print(w[r[i]-1]-w[l[i]-1])

Buggy python submission (verdict: Runtime Error):
n, q = map(int,input().split())
s = input()

l = [0] * q
r = [0] * q

for i in range(0,q):
    l[i], r[i] = map(int,input().split())
    l[i] = l[i] -1
    r[i] = r[i] -1

s_list = list(s)

ac_list = [0] * (n-1)

for i in range(0,n-1):
    if s_list[i] == "A" and s_list[i+1] == "C":
        ac_list[i] = 1

for i in range(0,q):

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

l = [0] * q
r = [0] * q

for i in range(0,q):
    l[i], r[i] = map(int,input().split())
    l[i] = l[i] -1
    r[i] = r[i] -1

s_list = list(s)

ac_list = [0] * (n-1)

for i in range(0,n-1):
    if s_list[i] == "A" and s_list[i+1] == "C":
        ac_list[i] = 1

#print(ac_list)

w = [0] * (n-1)

w[0] = ac_list[0]

for i in range(1,n-1):
    w[i] = w[i-1] + ac_list[i]

#print(w)

for i in range(0,q):
    if l[i] == 0:
        print(w[r[i]-1])
    else:
        print(w[r[i]-1]-w[l[i]-1])