Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
import bisect
from collections import Counter
n=int(input())
strings=[]
for _ in range(n):
    s=input()
    s=sorted(s)
    s="".join(s)
    i=bisect.bisect_left(strings, s)
    strings.insert(i, s)
c=Counter(strings)
ans=0
for i,v in c.items():
    ans+=int(v*(v-1)*0.5)
print(ans)


Fixed submission:
from collections import Counter
n=int(input())
strings=[]
for _ in range(n):
    s=input()
    s=sorted(s)
    s="".join(s)
    strings.append(s)
c=Counter(strings)
ans=0
for i,v in c.items():
    ans+=int(v*(v-1)*0.5)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n,m=map(int,input().split())
day_pay=[0 for _ in range(m)]
hikae=[[] for _ in range(m)]
for _ in range(n):
    a,b=map(int,input().split())
    if a>m:
        continue
    if day_pay[a-1]<b:
        hikae[a-1].append(day_pay[a-1])
        day_pay[a-1]=b
    else:
        hikae[a-1].append(b)
for i in hikae:
    i.sort()

ans=0
for d in range(0, m):
    best=max(day_pay[:d+1])
    idx=day_pay[:d+1].index(best)
    try:
        day_pay[idx]=hikae[idx].pop()
    except:
        day_pay[idx]=0
    ans+=best
print(ans)
    


Fixed submission:
import heapq
N, M = map(int, input().split())

fee = [[] for _ in range(10**5+10)]  # i日後に収入がもらえるバイトの価値
for _ in range(N):
    a, b = map(int, input().split())
    fee[a].append(-b)

task = []
ans = 0

# 締め切り日からさかのぼっていって、できるバイトで最大の収入をもらえるやつを実行する感じ
for i in range(1, M + 1):
    for f in fee[i]:
        heapq.heappush(task, f)

    if task:
        ans -= heapq.heappop(task)

print(ans)

Buggy python submission (verdict: Runtime Error):
n,m=map(int,input().split())
day_pay=[[0] for _ in range(m)]
for _ in range(n):
    a,b=map(int,input().split())
    day_pay[a-1].append(b)
    day_pay[a-1].sort()

ans=0
for d in range(0, m):
    best=0
    idx=m+2
    for i in range(d+1):
        if day_pay[i][-1]>best:
            best=day_pay[i][-1]
            idx=i
    if idx<len(day_pay):
        day_pay[i].pop()
    ans+=best
print(ans)

Fixed submission:
import heapq
N, M = map(int, input().split())

fee = [[] for _ in range(10**5+10)]  # i日後に収入がもらえるバイトの価値
for _ in range(N):
    a, b = map(int, input().split())
    fee[a].append(-b)

task = []
ans = 0

# 締め切り日からさかのぼっていって、できるバイトで最大の収入をもらえるやつを実行する感じ
for i in range(1, M + 1):
    for f in fee[i]:
        heapq.heappush(task, f)

    if task:
        ans -= heapq.heappop(task)

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
n,m=map(int,input().split())
day_pay=[]
for _ in range(n):
    a,b=map(int,input().split())
    day_pay.append((a, b))
day_pay.sort()

ans=0
for d in range(m-1, -1, -1):
    nokori=m-d
    best=0
    idx=n+2
    for i in range(len(day_pay)):
        day, pay=day_pay[i]
        if day>nokori:
            break
        else:
            if pay>=best:
                best=pay
                idx=i
            else:
                continue
    if idx<=len(day_pay):
        del day_pay[idx]
    ans+=best

print(ans)

Fixed submission:
import heapq
N, M = map(int, input().split())

fee = [[] for _ in range(10**5+10)]  # i日後に収入がもらえるバイトの価値
for _ in range(N):
    a, b = map(int, input().split())
    fee[a].append(-b)

task = []
ans = 0

# 締め切り日からさかのぼっていって、できるバイトで最大の収入をもらえるやつを実行する感じ
for i in range(1, M + 1):
    for f in fee[i]:
        heapq.heappush(task, f)

    if task:
        ans -= heapq.heappop(task)

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)

N, M, P = map(int, input().split())
edge = [[] for _ in range(N + 1)]
ein = [[] for _ in range(N + 1)]
for _ in range(M):
    a, b, c = map(int, input().split())
    edge[a].append((b, P - c))
    ein[b].append(a)

# 到達できる地点を決める
reach1 = [False] * (N + 1)
reach1[1] = True
node = [1]
while node:
    s = node.pop()
    for t, _ in edge[s]:
        if not reach1[t]:
            reach1[t] = True
            node.append(t)

reach2 = [False] * (N + 1)
reach2[N] = True
node = [N]
while node:
    s = node.pop()
    for t in ein[s]:
        if not reach2[t]:
            reach2[t] = True
            node.append(t)

can_go = []
Vertices = []
for i, (x, y) in enumerate(zip(reach1, reach2)):
    can_go.append(x & y)
    if x & y:
        Vertices.append(i)


inf = 10**18
cost = [inf] * (N + 1)
cost[1] = 0
for _ in range(M + 5):
    update = False
    for s in Vertices:
        now = cost[s]
        for t, c in edge[s]:
            if not can_go[t]:
                continue
            if cost[t] > now + c:
                cost[t] = now + c
                update = True


if update:
    print(-1)
else:
    print(max(0, -cost[N]))

Fixed submission:
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)

N, M, P = map(int, input().split())
edge = [[] for _ in range(N + 1)]
ein = [[] for _ in range(N + 1)]
for _ in range(M):
    a, b, c = map(int, input().split())
    edge[a].append((b, P - c))
    ein[b].append(a)

# 到達できる地点を決める
reach1 = [False] * (N + 1)
reach1[1] = True
node = [1]
while node:
    s = node.pop()
    for t, _ in edge[s]:
        if not reach1[t]:
            reach1[t] = True
            node.append(t)

reach2 = [False] * (N + 1)
reach2[N] = True
node = [N]
while node:
    s = node.pop()
    for t in ein[s]:
        if not reach2[t]:
            reach2[t] = True
            node.append(t)

can_go = []
Vertices = []
for i, (x, y) in enumerate(zip(reach1, reach2)):
    can_go.append(x & y)
    if x & y:
        Vertices.append(i)


inf = 10**18
cost = [inf] * (N + 1)
cost[1] = 0
for _ in range(M + 5):
    update = False
    for s in Vertices:
        now = cost[s]
        for t, c in edge[s]:
            if not can_go[t]:
                continue
            if cost[t] > now + c:
                cost[t] = now + c
                update = True


if update:
    print(-1)
else:
    print(max(0, -cost[N]))
Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
N=int(input())

lasts=deque([int(input())])
for _ in range(N-1):
    a=int(input())
    
    if a<=lasts[0]:
        lasts.appendleft(a)
    else:
        for i in range(len(lasts)-1, -1, -1):
            if lasts[i]<a:
                lasts[i]=a
                break

print(len(lasts))

Fixed submission:
import bisect
from collections import deque
N=int(input())
a=[int(input()) for _ in range(N)]
d=deque()

for i in range(N):
    p=bisect.bisect_left(d, a[i])
    #print(a[i], p, d)
    if p==0:
        d.appendleft(a[i])
    else:
        d[p-1]=a[i]
print(len(d))

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

lasts=[int(input())]
for _ in range(N-1):
    a=int(input())
    
    if a<=lasts[0]:
        lasts.insert(0, a)
    else:
        for i,val in enumerate(lasts[::-1]):
            if val<a:
                lasts[len(lasts)-1-i]=a
                break

print(len(lasts))

Fixed submission:
import bisect
from collections import deque
N=int(input())
a=[int(input()) for _ in range(N)]
d=deque()

for i in range(N):
    p=bisect.bisect_left(d, a[i])
    #print(a[i], p, d)
    if p==0:
        d.appendleft(a[i])
    else:
        d[p-1]=a[i]
print(len(d))

Buggy python submission (verdict: Runtime Error):
N=int(input())

lasts=[int(input())]
for _ in range(N-1):
    a=int(input())
    
    if a<=lasts[0]:
        lasts.insert(0, a)
    else:
        for i,val in enumerate(lasts[::-1]):
            if val<a:
                lasts[len(lasts)-1-i]=a
                break

print(len(lasts)

Fixed submission:
import bisect
from collections import deque
N=int(input())
a=[int(input()) for _ in range(N)]
d=deque()

for i in range(N):
    p=bisect.bisect_left(d, a[i])
    #print(a[i], p, d)
    if p==0:
        d.appendleft(a[i])
    else:
        d[p-1]=a[i]
print(len(d))
Buggy python submission (verdict: Time Limit Exceeded):
from scipy.sparse import lil_matrix, csr_matrix
from scipy.sparse.linalg import spsolve
import numpy as np

N = int(input())
A = np.array(input().split(), dtype=int)

mat = lil_matrix((N, N))
for i in range(N):
    j = (i + 1) % N
    mat[i, i] = 1
    mat[i, j] = 1
mat = csr_matrix(mat)

ans = (spsolve(mat, A) * 2).astype(int)
print(*ans)


Fixed submission:
from collections import deque
n=int(input())
a=deque(list(map(int,input().split())))
c=deque([1 if i%2==0 else -1 for i in range(n)])

ans=[]
for loop in range(n):
    if loop==0:
        t=sum([i*j for i,j in zip(a,c)])
    else:
        t=2*a[loop-1]-t
    ans.append(str(t))


print(" ".join(ans))

Buggy python submission (verdict: Time Limit Exceeded):
from scipy.sparse import lil_matrix, csr_matrix
from scipy.sparse.linalg import spsolve
import numpy as np

N = int(input())
A = np.array(input().split(), dtype=int)

mat = lil_matrix((N, N))
for i in range(N):
    j = (i + 1) % N
    mat[i, i] = 1
    mat[i, j] = 1
mat = csr_matrix(mat)

ans = spsolve(mat, A) * 2
ans = list(map(int, ans))
print(*ans)


Fixed submission:
from collections import deque
n=int(input())
a=deque(list(map(int,input().split())))
c=deque([1 if i%2==0 else -1 for i in range(n)])

ans=[]
for loop in range(n):
    if loop==0:
        t=sum([i*j for i,j in zip(a,c)])
    else:
        t=2*a[loop-1]-t
    ans.append(str(t))


print(" ".join(ans))

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
n=int(input())
a=deque(list(map(int,input().split())))
c=deque([1 if i%2==0 else -1 for i in range(n)])

ans=[]
for loop in range(n):
    t=sum([i*j for i,j in zip(a,c)])
    ans.append(str(t))
    c.rotate(1)


print(" ".join(ans))

Fixed submission:
from collections import deque
n=int(input())
a=deque(list(map(int,input().split())))
c=deque([1 if i%2==0 else -1 for i in range(n)])

ans=[]
for loop in range(n):
    if loop==0:
        t=sum([i*j for i,j in zip(a,c)])
    else:
        t=2*a[loop-1]-t
    ans.append(str(t))


print(" ".join(ans))

Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np
from collections import deque
n=int(input())
a=deque(list(map(int,input().split())))
c=np.array([1 if i%2==0 else -1 for i in range(n)])

ans=[]
for _ in range(n):
    rain=sum([i*j for i,j in zip(a,c)])
    tmp=a.popleft()
    a.append(tmp)
    ans.append(str(rain))
    


print(" ".join(ans))

Fixed submission:
from collections import deque
n=int(input())
a=deque(list(map(int,input().split())))
c=deque([1 if i%2==0 else -1 for i in range(n)])

ans=[]
for loop in range(n):
    if loop==0:
        t=sum([i*j for i,j in zip(a,c)])
    else:
        t=2*a[loop-1]-t
    ans.append(str(t))


print(" ".join(ans))
Buggy python submission (verdict: Runtime Error):
from math import gcd
a,b,c,d=map(int,input().split())
e=int(c*d/gcd(c,d))

rng=b-a+1
x=b//c-(a-1)//c
y=b//d-(a-1)//d
z=b//e-(a-1)//e
print(rng-x-y+z)

Fixed submission:
def gcd(x,y):
    x,y=max(x,y),min(x,y)
    if y==0:
        return x
    return gcd(y, x%y)


a,b,c,d=map(int,input().split())
e=int(c*d/gcd(c,d))

rng=b-a+1
x=b//c-(a-1)//c
y=b//d-(a-1)//d
z=b//e-(a-1)//e
print(rng-x-y+z)
Buggy python submission (verdict: Runtime Error):
mod = 10 ** 9 + 7

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

dp = [[0] * (N + 2) for _ in range(M + 2)]
for i in range(N+1):
    dp[i][0] = 1
for j in range(M+1):
    dp[0][j] = 1

for i, s in enumerate(S, 1):
    for j, t in enumerate(T, 1):
        dp[i][j] += dp[i - 1][j]
        dp[i][j] += dp[i][j - 1]
        if s == t:
            dp[i][j] += dp[i - 1][j - 1]
        dp[i][j] -= dp[i - 1][j - 1]
        dp[i][j] += mod
        dp[i][j] %= mod

print(dp[N][M])

Fixed submission:
mod = 10 ** 9 + 7

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

dp = [[0] * (M + 2) for _ in range(N + 2)]
for i in range(N+1):
    dp[i][0] = 1
for j in range(M+1):
    dp[0][j] = 1

for i, s in enumerate(S, 1):
    for j, t in enumerate(T, 1):
        dp[i][j] += dp[i - 1][j]
        dp[i][j] += dp[i][j - 1]
        if s == t:
            dp[i][j] += dp[i - 1][j - 1]
        dp[i][j] -= dp[i - 1][j - 1]
        dp[i][j] += mod
        dp[i][j] %= mod

print(dp[N][M])

Buggy python submission (verdict: Runtime Error):
N, M = map(int, input().split())
S = list(map(int, input().split())) + [0]
T = list(map(int, input().split())) + [0]
mod = 10 ** 9 + 7

dp0 = [[0]*(N+5) for _ in range(M+5)]  # i方向に進める
dp1 = [[0]*(N+5) for _ in range(M+5)]  # j方向に進める
dp0[0][0] = 1

for i in range(N + 1):
    for j in range(M + 1):
        dp0[i + 1][j] = (dp0[i + 1][j] + dp0[i][j]) % mod
        dp1[i][j] = (dp1[i][j] + dp0[i][j]) % mod
        dp1[i][j + 1] = (dp1[i][j + 1] + dp1[i][j]) % mod
        if S[i] == T[j]:
            dp0[i + 1][j + 1] = (dp0[i + 1][j + 1] + dp1[i][j]) % mod

ans = dp1[N][M]
print(ans)


Fixed submission:
mod = 10 ** 9 + 7

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

dp = [[0] * (M + 2) for _ in range(N + 2)]
for i in range(N+1):
    dp[i][0] = 1
for j in range(M+1):
    dp[0][j] = 1

for i, s in enumerate(S, 1):
    for j, t in enumerate(T, 1):
        dp[i][j] += dp[i - 1][j]
        dp[i][j] += dp[i][j - 1]
        if s == t:
            dp[i][j] += dp[i - 1][j - 1]
        dp[i][j] -= dp[i - 1][j - 1]
        dp[i][j] += mod
        dp[i][j] %= mod

print(dp[N][M])
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
U = 5000 * 5000 + 10

inf = 10 ** 18
dp1 = [-inf] * U
dp1[0] = N
for a, b in zip(A, B):
    for i in range(N - a + 1):
        dp1[i + a] = max(dp1[i + a], dp1[i] + b - a)

for i in range(N + 1):
    N = max(N, dp1[i])

dp2 = [-inf] * U
dp2[0] = N
for a, b in zip(A, B):
    for i in range(N - b + 1):
        dp2[i + b] = max(dp2[i + b], dp2[i] + a - b)

for i in range(N + 1):
    N = max(N, dp2[i])

print(N)

Fixed submission:
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
U = 5000 * 5000 + 10

inf = 10 ** 18
dp1 = [-inf] * U
dp1[0] = N
for a, b in zip(A, B):
    for i in range(N - a + 1):
        dp1[i + a] = max(dp1[i + a], dp1[i] + b - a)

for i in range(N + 1):
    N = max(N, dp1[i])

dp2 = [-inf] * U
dp2[0] = N
for a, b in zip(A, B):
    for i in range(N - b + 1):
        dp2[i + b] = max(dp2[i + b], dp2[i] + a - b)

for i in range(N + 1):
    N = max(N, dp2[i])

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

ans = 0
while "ABC" in s:
    ans += len(s.split("ABC"))-1
    s = s.replace("ABC", "BCA")

print(ans)


Fixed submission:
s = input()
n = len(s)
s += "???"

i = 0
ans = 0

while i < n:
    abc = []
    if s[i] == "A":
        i += 1
        abc.append(0)
        while True:
            if s[i] == "A":
                i += 1
                abc.append(0)
            elif s[i:i+2] == "BC":
                i += 2
                ans += len(abc)
            else:
                break
    i += 1

print(ans)

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

ans=0
while "ABC" in s:
    ans+=len(s.split("ABC"))-1
    s=s.replace("ABC", "BCA")

print(ans)

Fixed submission:
s = input()
n = len(s)
s += "???"

i = 0
ans = 0

while i < n:
    abc = []
    if s[i] == "A":
        i += 1
        abc.append(0)
        while True:
            if s[i] == "A":
                i += 1
                abc.append(0)
            elif s[i:i+2] == "BC":
                i += 2
                ans += len(abc)
            else:
                break
    i += 1

print(ans)
Buggy python submission (verdict: Runtime Error):
from collections import defaultdict
n=int(input())

def guidebook(n):
    SPlist=defaultdict(list)
    for i in range(n):
        s,p=input().split()
        SPlist[s].append((int(p), i+1))

    if n==1:
        print(1)
        return

    ans=[]
    SPlist=[(k, v) for k, v in SPlist.items()]
    SPlist.sort()
    ans=[]
    count=1
    for sp in SPlist:
        p=sp[1]
        if len(p)>1:
            p.sort(reverse=True)
            for i in p:
                ans.append((count, i[1]))
                count+=1
        else:
            ans.append((count, p[1]))

    for i in ans:
        print(i[1])
    return

guidebook(n)


Fixed submission:
n=int(input())
sp=[]
for i in range(1, n+1):
    s,p=input().split()
    sp.append((s, -int(p), i))

sp.sort()
for s,p,i in sp:
    print(i)

Buggy python submission (verdict: Runtime Error):
from collections import defaultdict
n=int(input())

SPlist=defaultdict(list)
for i in range(n):
    s,p=input().split()
    SPlist[s].append((int(p), i+1))

ans=[]
SPlist=[(k, v) for k, v in SPlist.items()]
SPlist.sort()
ans=[]
count=1
for sp in SPlist:
    p=sp[1]
    if len(p)>1:
        p.sort(reverse=True)
        for i in p:
            ans.append((count, i[1]))
            count+=1
    else:
        ans.append((count, p[1]))

for i in ans:
    print(i[1])


Fixed submission:
n=int(input())
sp=[]
for i in range(1, n+1):
    s,p=input().split()
    sp.append((s, -int(p), i))

sp.sort()
for s,p,i in sp:
    print(i)
Buggy python submission (verdict: Time Limit Exceeded):
from heapq import heappushpop, heapify

n,m=map(int,input().split())
a=list(map(int,input().split()))
heapify(a)
gomi=a[0]

bc=[]
for _ in range(m):
    b,c=map(int,input().split())
    bc.append((c,b))
bc.sort(reverse=True)

for i in bc:
    c,b=i
    if gomi>c:
        break
    for i in range(b):
        heappushpop(a, c)
    gomi=a[0]
print(sum(a))

Fixed submission:
import heapq
n, m = map(int, input().split())
a = list(map(int, input().split()))
heapq.heapify(a)
CB=[]
for _ in range(m):
    b, c = map(int, input().split())
    CB.append((c, b))
CB.sort(reverse=True)

for c, b in CB:
    if a[0] >= c:
        break
    for _ in range(b):
        if a[0] >= c:
            break
        heapq.heappushpop(a, c)

print(sum(a))

Buggy python submission (verdict: Time Limit Exceeded):
from heapq import heappushpop, heapify

n,m=map(int,input().split())
a=list(map(int,input().split()))
heapify(a)
gomi=a[0]
for _ in range(m):
    b,c=map(int,input().split())
    if gomi<c:
        for i in range(b):
            heappushpop(a, c)
        gomi=a[0]
print(sum(a))

Fixed submission:
import heapq
n, m = map(int, input().split())
a = list(map(int, input().split()))
heapq.heapify(a)
CB=[]
for _ in range(m):
    b, c = map(int, input().split())
    CB.append((c, b))
CB.sort(reverse=True)

for c, b in CB:
    if a[0] >= c:
        break
    for _ in range(b):
        if a[0] >= c:
            break
        heapq.heappushpop(a, c)

print(sum(a))

Buggy python submission (verdict: Time Limit Exceeded):
from heapq import heappushpop, heapify

n,m=map(int,input().split())
a=list(map(int,input().split()))
heapify(a)
gomi=a[0]
for _ in range(m):
    b,c=map(int,input().split())
    if gomi<c:
        for i in range(b):
            heappushpop(a, c)
        gomi=a[0]
print(sum(a))

Fixed submission:
import heapq
n, m = map(int, input().split())
a = list(map(int, input().split()))
heapq.heapify(a)
CB=[]
for _ in range(m):
    b, c = map(int, input().split())
    CB.append((c, b))
CB.sort(reverse=True)

for c, b in CB:
    if a[0] >= c:
        break
    for _ in range(b):
        if a[0] >= c:
            break
        heapq.heappushpop(a, c)

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

memo = []

for i, s in enumerate(S):
    if i == 0:
        now = s
        cnt = 1
        continue

    if s == now:
        cnt += 1
    else:
        if now == "0":
            memo.append(-cnt)
        else:
            memo.append(cnt)
        now = s
        cnt = 1
else:
    if now == "0":
        memo.append(-cnt)
    else:
        memo.append(cnt)

if memo[0] < 0:
    memo = [0] + memo
if memo[-1] < 0:
    memo += [0]

stand = memo[0::2]
handstand = memo[1::2]

if len(handstand) <= k:
    ans = sum(stand) - sum(handstand)
else:
    ans = 0
    for i in range(len(handstand)-k+1):
        tmp = sum(stand[i: i + k + 1]) - sum(handstand[i: i + k])
        ans = max(ans, tmp)

print(ans)


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

memo = []
for i, s in enumerate(S):
    if i == 0:
        now = s
        cnt = 1
        continue
    if s == now:
        cnt += 1
    else:
        memo.append(cnt)
        now = s
        cnt = 1
memo.append(cnt)

if S[-1] == "0":
    memo += [0]
if S[0] == "0":
    memo = [0]+memo

if len(S) <= 2 * k + 1:
    ans = sum(memo)
else:
    k = 2*k+1
    stand = sum(memo[0:k])
    cnt = (len(memo) - k) // 2

    ans = stand
    for i in range(cnt):
        stand -= memo[i * 2]
        stand -= memo[i * 2 + 1]
        stand += memo[k + i * 2]
        stand += memo[k + i * 2 + 1]
        ans = max(ans, stand)

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
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)

tmp=[]
for i in range(x):
    for j in range(y):
        tmp.append(a[i]+b[j])
tmp.sort(reverse=True)
ans=[]
for i in tmp[:3000]:
    for j in range(z):
        ans.append(i+c[j])
ans.sort(reverse=True)
for i in range(K):
    print(ans[i])

Fixed submission:
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)
ans=[]
for i in range(x):
    for j in range(y):
        if (i+1)*(j+1)>K:
            break
        for k in range(z):
            if (i+1)*(j+1)*(k+1)>K:
                break
            ans.append(a[i]+b[j]+c[k])
ans.sort(reverse=True)
for i in range(K):
    print(ans[i])

Buggy python submission (verdict: Time Limit Exceeded):
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)

tmp=[]
for i in range(x):
    for j in range(y):
        tmp.append(a[i]+b[j])
tmp.sort(reverse=True)
ans=[]
for i in tmp:
    for j in range(z):
        ans.append(i+c[j])
ans.sort(reverse=True)
for i in range(K):
    print(ans[i])

Fixed submission:
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)
ans=[]
for i in range(x):
    for j in range(y):
        if (i+1)*(j+1)>K:
            break
        for k in range(z):
            if (i+1)*(j+1)*(k+1)>K:
                break
            ans.append(a[i]+b[j]+c[k])
ans.sort(reverse=True)
for i in range(K):
    print(ans[i])

Buggy python submission (verdict: Time Limit Exceeded):
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()))

oisisa=[]
for i in range(x):
    for j in range(y):
        for k in range(z):
            val=a[i]+b[j]+c[k]
            oisisa.append(val)
oisisa.sort(reverse=True)
for i in range(K):
    print(oisisa[i])


Fixed submission:
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)
ans=[]
for i in range(x):
    for j in range(y):
        if (i+1)*(j+1)>K:
            break
        for k in range(z):
            if (i+1)*(j+1)*(k+1)>K:
                break
            ans.append(a[i]+b[j]+c[k])
ans.sort(reverse=True)
for i in range(K):
    print(ans[i])
Buggy python submission (verdict: Runtime Error):
n,q=map(int,input().split())
s=input()
ind=[]
z=0
for i,j in zip(s[:-1],s[1:]):
    if i+j=="AC":
        ind.append(z)
    z+=1

aa=len(ind)
for i in range(q):
    l,r=map(int,input().split())
    l-=1
    r-=1
    for ii,jj in enumerate(ind):
        if jj>=l:
            start=ii
            break
    for ii,jj in enumerate(ind[::-1]):
        if jj<r:
            end=ii
            break
    print(max(0,aa-(start+end)))

Fixed submission:
n,q=map(int,input().split())
S=input()
cnt=[0]*n

for i in range(1, n):
    s=S[i-1]+S[i]
    if s=="AC":
        cnt[i]+=1

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

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