Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
import collections
n = input()
s = [input() for _ in range(n)]
s = collections.Counter(s)
m = max(s.values())

a = []
for d in s.items():
    if d[1] == m:
        a.append(d[0])
for s in a:
    print(s)


Fixed submission:
from collections import Counter
n = int(input())
s = [input() for _ in range(n)]
s = Counter(s)
m = max(s.values())

a = []
for d in s.items():
    if d[1] == m:
        a.append(d[0])
for s in sorted(a):
    print(s)

Buggy python submission (verdict: Runtime Error):
from collections import Counter
n = input()
s = [input() for _ in range(n)]
s = Counter(s)
m = max(s.values())

a = []
for d in s.items():
    if d[1] == m:
        a.append(d[0])
for s in a:
    print(s)

Fixed submission:
from collections import Counter
n = int(input())
s = [input() for _ in range(n)]
s = Counter(s)
m = max(s.values())

a = []
for d in s.items():
    if d[1] == m:
        a.append(d[0])
for s in sorted(a):
    print(s)
Buggy python submission (verdict: Runtime Error):
s, t = map(str, input().split())
a. b = map(int, input().split())
u = input()

if s == u:
  print("{} {}".format(a-1, b))
else:
  print("{} {}".format(a, b-1))


Fixed submission:
s, t = input().split()
a, b = map(int, input().split())
u = input()

if s == u:
  print("{} {}".format(a-1, b))
else:
  print("{} {}".format(a, b-1))

Buggy python submission (verdict: Runtime Error):
s, t = input().split()
a. b = map(int, input().split())
u = input()

if s == u:
  print("{} {}".format(a-1, b))
else:
  print("{} {}".format(a, b-1))


Fixed submission:
s, t = input().split()
a, b = map(int, input().split())
u = input()

if s == u:
  print("{} {}".format(a-1, b))
else:
  print("{} {}".format(a, b-1))

Buggy python submission (verdict: Runtime Error):
s, t = input().split()
a. b = map(int, input().split())
u = input()

if s == u:
  print(a-1 b)
else:
  print(a b-1)


Fixed submission:
s, t = input().split()
a, b = map(int, input().split())
u = input()

if s == u:
  print("{} {}".format(a-1, b))
else:
  print("{} {}".format(a, b-1))
Buggy python submission (verdict: Runtime Error):
n = input()
a_list = list(map(int, input().split()))
a_set = set(a)

if len(a_list) == len(a_set):
  print("YES")
else:
  print("NO")

Fixed submission:
n = input()
a_list = list(map(int, input().split()))
a_set = set(a_list)

if len(a_list) == len(a_set):
  print("YES")
else:
  print("NO")

Buggy python submission (verdict: Runtime Error):
n = input()
a_list = list(map(int, input.split()))
a_set = set(a)

if len(a_list) == len(a_set):
  print("YES")
else:
  print("NO")

Fixed submission:
n = input()
a_list = list(map(int, input().split()))
a_set = set(a_list)

if len(a_list) == len(a_set):
  print("YES")
else:
  print("NO")
Buggy python submission (verdict: Runtime Error):
N, K = map(int, input().split())
p_list = list(map(int, input().split()))

#そのサイコロの期待値の合計
e_list = []
for i in range(N):
    e_list.append((1+p_list[i])/2.0)

#累積和
s_list = []
for i in range(N):
    s_list.append(sum(e_list[:i+1]))

#隣接するk個の和
for i in range(N-K+1):
    s_sum = s_list[i+K-1] - s_list[i]
    if dst < s_sum:
        dst = s_sum
print(dst)

Fixed submission:
N, K = map(int, input().split())
P = list(map(int, input().split()))

#期待値L
L = [0 for _ in range(N)]
for i in range(N):
    L[i] = (1+P[i])/2

#累積和S
S = [0 for i in range(N)]
S[0] = L[0]
for i in range(1, N):
    S[i] = S[i-1] + L[i]

total = S[K-1]
for i in range(N-K):
    tmp = S[i+K]-S[i]
    if total < tmp:
        total = tmp

print(total)

Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int, input().split())
p_list = list(map(int, input().split()))

dst = 0.0

for i in range(N-K+1):
    p_sum = 0.0
    for j in range(K):
        p = p_list[i+j]
        p_sum += ( p/2 * (1+p)) / p
    if p_sum > dst:
        dst = p_sum
    
print(dst)

Fixed submission:
N, K = map(int, input().split())
P = list(map(int, input().split()))

#期待値L
L = [0 for _ in range(N)]
for i in range(N):
    L[i] = (1+P[i])/2

#累積和S
S = [0 for i in range(N)]
S[0] = L[0]
for i in range(1, N):
    S[i] = S[i-1] + L[i]

total = S[K-1]
for i in range(N-K):
    tmp = S[i+K]-S[i]
    if total < tmp:
        total = tmp

print(total)

Buggy python submission (verdict: Runtime Error):
N, K = map(int, A.split())
p_list = list(map(int, B.split()))

dst = 0

for i in range(N-K+1):
    print("i : {}".format(i))
    p_sum = 0
    for j in range(K):
        p = p_list[i+j]
        print("p : {}".format(p))
        p_sum += ( p/2 * (1+p)) / p
    if p_sum > dst:
        dst = p_sum
    
print(dst)

Fixed submission:
N, K = map(int, input().split())
P = list(map(int, input().split()))

#期待値L
L = [0 for _ in range(N)]
for i in range(N):
    L[i] = (1+P[i])/2

#累積和S
S = [0 for i in range(N)]
S[0] = L[0]
for i in range(1, N):
    S[i] = S[i-1] + L[i]

total = S[K-1]
for i in range(N-K):
    tmp = S[i+K]-S[i]
    if total < tmp:
        total = tmp

print(total)

Buggy python submission (verdict: Runtime Error):
N, K = map(int, input().split())
p_list = len(map(int, input().split()))

dst = 0

for i in range(N-K+1):
  p_sum = 0
  for j in range(K):
    p = p[j]
    p_sum += p/2 * (1+p)
  if p_sum > dst:
    dst = p_sum
    
print(dst)

Fixed submission:
N, K = map(int, input().split())
P = list(map(int, input().split()))

#期待値L
L = [0 for _ in range(N)]
for i in range(N):
    L[i] = (1+P[i])/2

#累積和S
S = [0 for i in range(N)]
S[0] = L[0]
for i in range(1, N):
    S[i] = S[i-1] + L[i]

total = S[K-1]
for i in range(N-K):
    tmp = S[i+K]-S[i]
    if total < tmp:
        total = tmp

print(total)
Buggy python submission (verdict: Runtime Error):
n = input()
k = input()
nl = len(n)

dp = [[[0]*(k+1) for _ in range(2)]for _ in range(nl+1)]
#dp[i][j][k] i:上からの桁数、j:smaller flag、k:0以外の数字の個数
dp[0][0][0] = 1

for i in range(nl):
  for j in range(2):
    for l in range(k+1):
      c = int(n[i])
      if j == 1:
        dp[i+1][j][l] += dp[i][j][l]
        if l < k:
          dp[i+1][j][l+1] += dp[i][j][l]*9
      else:
        if c == 0:#0しか選べない上にsmallを確定できない
          dp[i+1][0][l] += dp[i][j][l]
        else:
          dp[i+1][1][l] += dp[i][j][l]#cより確実に小さい0を使う。small確定
          if l < k:
            dp[i+1][1][l+1] += dp[i][j][l]*(c-1) #c以下の数字を使えばsmall確定
            dp[i+1][0][l+1] += dp[i][j][l] #cを使ったらsmall確定できない
            
print(dp[nl][0][k]+dp[nl][1][k])
          



Fixed submission:
n = input()
k = int(input())
nl = len(n)#桁数
dp = [[[0] * (k + 1) for i in range(2)] for i in range(nl + 1)]
dp[0][0][0] = 1# 初期条件

# dp[i][j][k] i:桁数 j:smallフラグ 1はsmall確定、0はnと同じ値 k:ゼロ以外の数字を使った回数
for i in range(nl):
    for j in range(2):
        for l in range(k + 1): # lはK+1(つまりk)までの範囲にしても問題なし。下でl<kするから
            c = int(n[i])# 今調べている桁の数
            if j == 1:  # small確定の場合
                dp[i + 1][j][l] += dp[i][j][l]  # kの値が等しいので次の桁で0が来なければいけない
                if l < k:  # まだ0でない数の個数がkより少ない場合   ※比較する変数注意！
                    dp[i + 1][j][l + 1] += dp[i][j][l] * 9  # 次の桁で1~9を使う
            else:  # j==0のとき つまり現在まで調べている桁数の部分がnと一致している。
                if c == 0:
                    # cが0のときは0しか選べなく、small確定できない
                    dp[i + 1][0][l] += dp[i][j][l]
                else:
                    dp[i + 1][1][l] += dp[i][j][l]  # Cより小さい0を使う→small確定
                    if l < k: #※比較する変数注意！
                        dp[i + 1][1][l + 1] += dp[i][j][l] * (c - 1)  # c以外の数字を使う、small確定
                        dp[i + 1][0][l + 1] += dp[i][j][l]  # cを使う、small確定できない
print(dp[nl][1][k]+dp[nl][0][k])
Buggy python submission (verdict: Runtime Error):
n, k = map(int, input().split())
h = list(map(int, input().split()))
h = h.sort()

if k >= n:
  print(0)
  
else:
  print(sum(h[:n-k]))

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

if k >= n:
  print(0)
  
else:
  print(sum(h[:n-k]))
Buggy python submission (verdict: Runtime Error):
h = int(input())
a = 0
while h > 0:
    h = h//2
    a += 1

f[0] = h
  
print(2**a-1)

Fixed submission:
h = int(input())
a = 0
while h > 0:
    h = h//2
    a += 1
  
print(2**a-1)
Buggy python submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-

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

if d >= 22:
  print('bust')
else:
  print('win)

Fixed submission:
# -*- coding: utf-8 -*-

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

if d >= 22:
  print('bust')
else:
  print('win')
Buggy python submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-

s = input()
s_list = list(s)
s_len = len(s_list)

hag = 0

for i in range(s_len//2):
  if s_list[i] != s_list[(s_len-1)-i]:
    s_list[s_len-i] = s_list[i]
    hag += 1
  
print(hag)

Fixed submission:
# -*- coding: utf-8 -*-

s = input()
s_list = list(s)
s_len = len(s_list)

hag = 0

for i in range(s_len//2):
  if s_list[i] != s_list[(s_len-1)-i]:
    s_list[(s_len-1)-i] = s_list[i]
    hag += 1
  
print(hag)
Buggy python submission (verdict: Runtime Error):
import numpy as np
 
stdin = open(0)
data = np.fromstring(stdin.read(), np.int32, sep=' ')
N = data[0]
A = data[1]

flag = True
for a in A:
  if a%2 == 0:
    if a%3 != 0 or a%5 != 0:
      flag = False

if flag:
  print('APPROVED')
else:
  print('DENIED')  

Fixed submission:
N = int(input())
A = [int(i) for i in input().split()]
 
flag = True
for a in A:
  if a%2 == 0:
    if a%3 != 0 and a%5 != 0:
      flag = False
 
if flag:
  print('APPROVED')
else:
  print('DENIED')
Buggy python submission (verdict: Runtime Error):
N = int(input())

Sdict = dict()
for _ in range(N):
    s = input()
    if s in Sdict:
        Sdict[s] += 1
    else:
        Sdict[s] = 0
    
print(Sdict)
maxi = 0
lis = []
for k,v in Sdict.itens():
	if v > maxi:
        lis = [k]
        maxi = v
    if v == maxi:
		lis.append(k)

print(lis.sort())

Fixed submission:
N = int(input())

Sdict = dict()
max = 0
for _ in range(N):
    s = input()
    if s in Sdict:
        Sdict[s] += 1
    else:
        Sdict[s] = 0
    
maxi = 0
lis = []
for k,v in Sdict.items():
    if v > maxi:
        lis = [k]
        maxi = v
    elif v == maxi:
        lis.append(k)
lis.sort()
for k in lis:
    print(k)

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

S = []
Sdict = dict()
for _ in range(N):
    s = input()
    if s in S:
        Sdict[s] += 1
    else:
        S.append(s)
        Sdict[s] = 0
    
maxi = max(Sdict.values())

def get_keys_from_value(d, val):
	return [k for k, v in d.items() if v == val]

for k in sorted(get_keys_from_value(Sdict,maxi)):
	print(k)

Fixed submission:
N = int(input())

Sdict = dict()
max = 0
for _ in range(N):
    s = input()
    if s in Sdict:
        Sdict[s] += 1
    else:
        Sdict[s] = 0
    
maxi = 0
lis = []
for k,v in Sdict.items():
    if v > maxi:
        lis = [k]
        maxi = v
    elif v == maxi:
        lis.append(k)
lis.sort()
for k in lis:
    print(k)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
P = [int(i) for i in input().split()]

ans = 0
for l in range(N-1):
    for r in range(l+1,N):
        ans += sorted(P[l:r+1])[-2]

print(ans)

Fixed submission:
N = int(input())
P = [int(i) for i in input().split()]

ind = [0]*(N+1)
for i in range(N):
    ind[P[i]] = i+1

ans = 0
l = [0] + [f for f in range(N+1)]
r = [f + 1 for f in range((N+1))] + [N+1]

for j in range(1,N+1):
    f = ind[j]

    l1 = l[f]
    l2 = l[l1]
    r1 = r[f]
    r2 = r[r1]
    ans += ((l1-l2)*(r1-f) + (f-l1)*(r2-r1))*j

    l[r1] = l1
    r[l1] = r1

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
s = input()
for n in range(len(s)):
    if s[n:n+2] == 'BC':
        s = s[:n]+'D'+s[n+2:]
#print(s)
ans = 0
cnta = 0
for n in range(len(s)):
    if s[n] == 'A':
        cnta += 1
    elif s[n] == 'D':
        ans += cnta
    elif s[n] == 'B' or s[n] == 'C':
        cnta = 0

print(ans)

Fixed submission:
s = input()
s = s.replace('BC','D')

ans = 0
cnta = 0
for n in range(len(s)):
    if s[n] == 'A':
        cnta += 1
    elif s[n] == 'D':
        ans += cnta
    elif s[n] == 'B' or s[n] == 'C':
        cnta = 0

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
s = input()
for n in range(len(s)):
    if s[n:n+2] == 'BC':
        s = s[:n]+'D'+s[n+2:]
#print(s)
ans = 0
cnta = 0
for n in range(len(s)):
    if s[n] == 'A':
        cnta += 1
    elif s[n] == 'D':
        ans += cnta
    elif s[n] == 'B' or s[n] == 'C':
        cnta = 0

print(ans)

Fixed submission:
s = input()
s = s.replace('BC','D')

ans = 0
cnta = 0
for n in range(len(s)):
    if s[n] == 'A':
        cnta += 1
    elif s[n] == 'D':
        ans += cnta
    elif s[n] == 'B' or s[n] == 'C':
        cnta = 0

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
s = input()
for n in range(len(s)):
    if s[n:n+2] == 'BC':
        s = s[:n]+'D'+s[n+2:]
#print(s)
ans = 0
cnta = []
for n in range(len(s)):
    if s[n] == 'A':
        cnta.append(0)
    elif s[n] == 'D':
        cnta = list(map(lambda x: x+1, cnta))
    elif s[n] == 'B' or s[n] == 'C':
        ans += sum(cnta)
        cnta = []

ans += sum(cnta)

print(ans)

Fixed submission:
s = input()
s = s.replace('BC','D')

ans = 0
cnta = 0
for n in range(len(s)):
    if s[n] == 'A':
        cnta += 1
    elif s[n] == 'D':
        ans += cnta
    elif s[n] == 'B' or s[n] == 'C':
        cnta = 0

print(ans)
Buggy python submission (verdict: Runtime Error):
N,M = map(int, input().split())
ks = [[int(i) for i in input().split()] for j in range(M)]
p = [int(i) for i in input().split()] 

l = max(max(ks))

lis_swi = s = [[] for i in range(l)]

for m in range(M):
    for s in ks[m][1:]:
        lis_swi[s-1].append(m)


ans = 0

for i in range(1 << l):
    cnt_on = [0]*M
    for j in range(l):
        if ((i >> j) & 1) == 1:
            for m in lis_swi[j]:
                cnt_on[m] +=1

    f = True
    for m in range(M):
        if cnt_on[m]%2 != p[m]:
            f = False
            break
    
    if f:
        ans += 1


print(ans)

Fixed submission:
N,M = map(int, input().split())
ks = [[int(i) for i in input().split()] for j in range(M)]
p = [int(i) for i in input().split()] 

ans = 0

for i in range(1 << N):
    cnt_on = [0]*M
    for j in range(N):
        if ((i >> j) & 1) == 1:
            for m in range(M):
                cnt_on[m] += ks[m][1:].count(j+1)

    c = 0
    for m in range(M):
        if cnt_on[m]%2 == p[m]:
            c += 1
    
    if c == M:
        ans += 1


print(ans)
Buggy python submission (verdict: Runtime Error):
H,W,N = map(int, input().split())
now = [int(i) for i in input().split()]
S = input()
T = input()
flag = True
SM = [now[0],now[1]]
TM = [now[0],now[1]]

for n in range(N):
    if S[n] == 'L':
            SM[1] -= 1
    if S[n] == 'R':
            SM[1] += 1 
    if S[n] == 'U':
            SM[0] -= 1 
    if S[n] == 'D':
            SM[0] += 1
    if T[n] == 'L':
            TM[1] -= 1
    if T[n] == 'R':
            TM[1] += 1 
    if T[n] == 'U':
            TM[0] -= 1 
    if T[n] == 'D':
            TM[0] += 1

sm = [0,0,0,0]
if W-SM[1] >= SM[1]-1:
    sm[0] = 1
if W-SM[1] < SM[1]-1:
    sm[1] = 1
if H-SM[0] <= SM[0]-1:
    sm[2] = 1
if H-SM[0] < SM[0]-1:
    sm[3] = 1

tm = [0,0,0,0]
if W-TM[1] >= TM[1]-1:
    tm[0] = 1
if W-TM[1] <= TM[1]-1:
    tm[1] = 1
if H-TM[0] <= TM[0]-1:
    tm[2] = 1
if H-TM[0] <= TM[0]-1:
    tm[3] = 1

for n in range(N):
    if S[n] == 'L':
        if sm[0] == 1:
            now[1] -= 1
    if S[n] == 'R':
        if sm[1] == 1:
            now[1] += 1 
    if S[n] == 'U':
        if sm[3] == 1:
            now[0] -= 1 
    if S[n] == 'D':
        if sm[4] == 1:
            now[0] += 1
    #print(now)

    if now[0]*now[1] == 0 or now[0] == H+1 or now[1] == W+1 :
        flag = False
        break
    
    if T[n] == 'L':
        if tm[1] == 0:
            now[1] -= 1
    if T[n] == 'R':
        if tm[2] == 0:
            now[1] += 1 
    if T[n] == 'U':
        if tm[3] == 0:
            now[0] -= 1 
    if T[n] == 'D':
        if tm[4] == 0:
            now[0] += 1
    #print(now)

    if now[0]*now[1] == 0 or now[0] == H+1 or now[1] == W+1 :
        flag = False
        break

if flag:
    print('YES')
else:
    print('NO')

Fixed submission:
H,W,N = map(int, input().split())
st = [int(i) for i in input().split()]
S = input()
T = input()


def simu(dim1):
    now = [st[0],st[1]]

    if dim1 == 'U':
        dim2,L,step,dim = 'D',H,1,0
    if dim1 == 'D':
        dim2,L,step,dim = 'U',H,-1,0
    if dim1 == 'L':
        dim2,L,step,dim = 'R',W,1,1
    if dim1 == 'R':
        dim2,L,step,dim = 'L',W,-1,1

    for i in range(N):
        if S[i] == dim1:
            now[dim] -= step
        if now[dim] < 1 or now[dim] >= L+1:
            return True
        if T[i] == dim2:
            if step == 1:
                if now[dim] < L:
                    now[dim] += step
            else:
                if now[dim] > 1:
                    now[dim] += step
    return False
        
Dim = ['U','D','R','L']
for d in Dim:
    if simu(d):
        print('NO')
        exit()
print('YES')
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
V = [int(i) for i in input().split()] 
C = [int(i) for i in input().split()] 

ans = []

for i in range(1<<N):
    X = 0
    Y = 0
    for j in range(N):
        if ((i >> j) & 1) == 1:
            X += V[j]
            Y += C[j]
    ans.append(X-Y)

print(max(ans))

Fixed submission:
N = int(input())
V = [int(i) for i in input().split()] 
C = [int(i) for i in input().split()] 

ans = []

for i in range(1<<N):
    X = 0
    Y = 0
    for j in range(N):
        if ((i >> j) & 1) == 1:
            X += V[j]
            Y += C[j]
    ans.append(X-Y)

print(max(ans))
Buggy python submission (verdict: Runtime Error):
N = int(input())
a = [int(input()) for _ in range(N)]

s = sum(a)
mod = 998244353

dp1 = [0] * (s+1)
dp2 = [0] * (s+1)
dp1[0] = 1
dp2[0] = 1
sum_ = 0


ans = 0
for n in range(N):
    for i in reversed(range(sum_+1)):
        dp1[i] %= mod
        dp2[i] %= mod
        dp1[i+a[n]] += dp1[i]
        dp1[i] <<= 1
        dp2[i+a[n]] += dp2[i]
    print(dp1,dp2)
    sum_ += a[n]

ans = (3 ** N)%mod
for i in range(s+1):
    if i*2 >= s:
        ans -= dp1[i]*3 + mod*3
        ans %= mod
    if i*2 == s:
        ans += dp2[i]*3
        ans %= mod

print(ans)

Fixed submission:
N = int(input())
a = [int(input()) for _ in range(N)]

s = sum(a)
mod = 998244353

dp1 = [0] * (s+1)
dp2 = [0] * (s+1)
dp1[0] = 1
dp2[0] = 1
sum_ = 0


ans = 0
for n in range(N):
    for i in reversed(range(sum_+1)):
        dp1[i] %= mod
        dp2[i] %= mod
        dp1[i+a[n]] += dp1[i]
        dp1[i] <<= 1
        dp2[i+a[n]] += dp2[i]
    #print(dp1,dp2)
    sum_ += a[n]

ans = (3 ** N)%mod
for i in range(s+1):
    if i*2 >= s:
        ans -= dp1[i]*3 + mod*3
        ans %= mod
    if i*2 == s:
        ans += dp2[i]*3
        ans %= mod

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
X,Y,Z,K = map(int, input().split())
A = [int(i) for i in input().split()] 
B = [int(i) for i in input().split()] 
C = [int(i) for i in input().split()] 

A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)

def solve(P):
    cnt = 0
    for x in range(X):
        for y in range(Y):
            for z in range(Z):
                if A[x]+B[y]+C[z] >= P:
                    cnt+=1
                if cnt >= K:
                    return False
    return True

t = True
P = A[0]+B[0]+C[0]
while t:
    t = solve(P)
    P -= 1


ans = []
cnt = 0
for x in range(X):
        for y in range(Y):
            for z in range(Z):
                if A[x]+B[y]+C[z] >= P+1:
                    ans.append(A[x]+B[y]+C[z])
                    cnt+=1
                if cnt >= K:
                    ans.sort(reverse=True)
                    for k in range(K):
                        print(ans[k])
                    exit()

Fixed submission:
X,Y,Z,K = map(int, input().split())
A = [int(i) for i in input().split()] 
B = [int(i) for i in input().split()] 
C = [int(i) for i in input().split()] 

ans = []
for x in range(X):
    for y in range(Y):
        ans.append(A[x]+B[y])

ans.sort(reverse=True)
C.sort(reverse=True)
ans2 = []
for k in range(min(K,X*Y)):
    for z in range(min(Z,K)):
        ans2.append(ans[k]+C[z])
ans2.sort(reverse=True)

for k in range(K):
    print(ans2[k])

Buggy python submission (verdict: Time Limit Exceeded):
X,Y,Z,K = map(int, input().split())
A = [int(i) for i in input().split()] 
B = [int(i) for i in input().split()] 
C = [int(i) for i in input().split()] 

ans = []
for x in range(X):
    for y in range(Y):
        for z in range(Z):
            ans.append(A[x]+B[y]+C[z])
ans.sort(reverse=True)
for k in range(K):
    print(ans[k])

Fixed submission:
X,Y,Z,K = map(int, input().split())
A = [int(i) for i in input().split()] 
B = [int(i) for i in input().split()] 
C = [int(i) for i in input().split()] 

ans = []
for x in range(X):
    for y in range(Y):
        ans.append(A[x]+B[y])

ans.sort(reverse=True)
C.sort(reverse=True)
ans2 = []
for k in range(min(K,X*Y)):
    for z in range(min(Z,K)):
        ans2.append(ans[k]+C[z])
ans2.sort(reverse=True)

for k in range(K):
    print(ans2[k])
Buggy python submission (verdict: Time Limit Exceeded):
N,Q = map(int,input().split())
S = input()
l = [0]*Q
r = [0]*Q
for q in range(Q):
    l[q],r[q] = map(int,input().split())

for q in range(Q):
    cnt = 0
    for i in range((l[q]-1),r[q]-1):
        if S[i:i+2] == 'AC':
            cnt +=1
    print(cnt)

Fixed submission:
N,Q = map(int,input().split())
S = input()

cnt = [0]*(N+1)
for i in range(N):
    if S[i:i+2] == 'AC':
        cnt[i+1] = cnt[i]+1
    else:
        cnt[i+1] = cnt[i]
    
#print(cnt)

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

Buggy python submission (verdict: Time Limit Exceeded):
N,Q = map(int,input().split())
S = input()
l = [0]*Q
r = [0]*Q
for q in range(Q):
    l[q],r[q] = map(int,input().split())

for q in range(Q):
    cnt = 0
    for i in range((l[q]-1),r[q]-1):
        if S[i:i+2] == 'AC':
            cnt +=1
    print(cnt)

Fixed submission:
N,Q = map(int,input().split())
S = input()

cnt = [0]*(N+1)
for i in range(N):
    if S[i:i+2] == 'AC':
        cnt[i+1] = cnt[i]+1
    else:
        cnt[i+1] = cnt[i]
    
#print(cnt)

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

Buggy python submission (verdict: Time Limit Exceeded):
N,Q = map(int,input().split())
S = input()
l = [0]*Q
r = [0]*Q
for q in range(Q):
    l[q],r[q] = map(int,input().split())

for q in range(Q):
    s = S[l[q]-1:r[q]]
    #print(s)
    cnt = 0
    for i in range(len(s)-1):
        if s[i:i+2] == 'AC':
            cnt +=1
            #print('y')
    print(cnt)

Fixed submission:
N,Q = map(int,input().split())
S = input()

cnt = [0]*(N+1)
for i in range(N):
    if S[i:i+2] == 'AC':
        cnt[i+1] = cnt[i]+1
    else:
        cnt[i+1] = cnt[i]
    
#print(cnt)

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