Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
import heapq
from collections import defaultdict

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


work = defaultdict(list)

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



# 終了日から１日前、２日前、...の順で仕事を選ぶ
current_work = []
ans = 0
for i in range(M):
    if i in work.keys():
        current_work.extend(work[i])

    if current_work:
        heapq.heapify(current_work)
        money = heapq.heappop(current_work)
        ans += -1 * money

print(ans)

Fixed submission:
import heapq

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

ab = {}

for i in range(N):
    a,b = map(int, input().split())
    if not a in ab:
        ab[a] = [-b]
    else:
        ab[a].append(-b)


q = []
ans = 0
for day in range(1, M+1):
    if day in ab:
        for i in ab[day]:
            heapq.heappush(q, i)

    if q != None and len(q) != 0:
        ans += -1 * heapq.heappop(q)

print(ans)

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

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

ab = [None] * N

for i in range(N):
    a,b = map(int, input().split())
    ab[i] = [a,-b]

q = []
ans = 0
for day in range(1, M+1):
    for i in range(N):
        if ab[i][0] == day:
            heapq.heappush(q, ab[i][1])

    if q != None and len(q) != 0:
        ans += -1 * heapq.heappop(q)

print(ans)

Fixed submission:
import heapq

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

ab = {}

for i in range(N):
    a,b = map(int, input().split())
    if not a in ab:
        ab[a] = [-b]
    else:
        ab[a].append(-b)


q = []
ans = 0
for day in range(1, M+1):
    if day in ab:
        for i in ab[day]:
            heapq.heappush(q, i)

    if q != None and len(q) != 0:
        ans += -1 * heapq.heappop(q)

print(ans)
Buggy python submission (verdict: Runtime Error):
N,M,P = map(int, input().split())

es = []

for i in range(M):
    a,b,c = map(int, input().split())
    es.append((a-1, b-1, c))

INF = float("inf")

d = [INF for _ in range(N)] 
d[0] = 0
"""
頂点Nに向かうまでに関係ない閉路に注意する

無限にコインを拾える場合、
・ある閉路を一周したときの得点と支払いの収支がプラス
・その閉路からゴールまで行ける
である。これがない場合、全てのノードを経由してゴールまで行く（N-1回移動）までにコインの枚数が最大になる
なので、一回ベルマンフォード法をやった後もう一回行って一回目と２回目でゴールまでのコイン枚数に変化があればゴ、
ールに行くまでの道に無限にコインをとれる閉路があるといえる

"""

def solve(start):
    for i in range(N):
        for a,b,c, in es:
            if d[a] != INF and d[a] + (-c) + P < d[b]:
                d[b] = d[a] + (-c) + P
                

                if i == N-1 and b == N-1:
                    return -1


    return max(-d[-1][0])


first=solve(0)
if first == -1:
    print(-1)
else:
    second=solve(0)
    if first == second:
        print(max(first, 0))
    else:
        print(-1)

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

es = []

for i in range(M):
    a,b,c = map(int, input().split())
    es.append((a-1, b-1, c))

INF = float("inf")

d = [INF for _ in range(N)] 
d[0] = 0
"""
頂点Nに向かうまでに関係ない閉路に注意する

無限にコインを拾える場合、
・ある閉路を一周したときの得点と支払いの収支がプラス
・その閉路からゴールまで行ける
である。これがない場合、全てのノードを経由してゴールまで行く（N-1回移動）までにコインの枚数が最大になる
なので、一回ベルマンフォード法をやった後もう一回行って一回目と２回目でゴールまでのコイン枚数に変化があればゴ、
ールに行くまでの道に無限にコインをとれる閉路があるといえる

"""

def solve(start, f):
    for i in range(N):
        for a,b,c, in es:
            if d[a] != INF and d[a] + (-c) + P < d[b]:
                # ２週目と区別する。２週目で更新される部分は-INFとか適当に置いておくと、ゴールまでの影響がわかる
                if f == 0:
                    d[b] = d[a] + (-c) + P
                else:
                    d[b] = -INF


    return d[-1]


first=solve(0,0)
second=solve(0, 1)
if first != second:
    print(-1)
else:
    print(max(-first, 0))
Buggy python submission (verdict: Time Limit Exceeded):
import bisect

N = int(input())
A = [int(input()) for _ in range(N)]


colors = []
for i in range(N):
    if i == 0:
        colors.append(A[i])
    else:
        # 上に積める色がないなら新しく追加
        if A[i] <= colors[0]:
            colors = [A[i]] + colors
        # 積む色がある場合
        else:
            idx = bisect.bisect_left(colors, A[i])
            colors[idx-1] = A[i]


print(len(colors))

Fixed submission:
import bisect

N = int(input())
A = [int(input()) for _ in range(N)]


colors = []

#後ろから見ていく
for i,n in enumerate(list(reversed(A))):
    # 一つ目はとりあえずなんか一色ぬる
    if i == 0:
        colors.append(n)
    else:
        #二つ目以降は、各色の最小値のなかで、今見ているのより小さいものがあればそれを置き換える
        #ここをbisect_leftにすると、colorsの中で同じ最小値があるときにinsertが必要なので遅い
        # 「各色の最小値集合の最小値と置き換える」を繰り返すので、最小値集合の最大より大きいなら最後に追加
        idx = bisect.bisect_right(colors, n)
        if idx == len(colors):
            colors.append(n)
        else:
            colors[idx] = n

print(len(colors))

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

N = int(input())
A = [int(input()) for _ in range(N)]


colors = []
for i in range(N):
    if i == 0:
        colors.append(A[i])
    else:
        # 上に積める色がないなら新しく追加
        if A[i] <= colors[0]:
            colors = [A[i]] + colors
        # 積む色がある場合
        else:
            idx = bisect.bisect_left(colors, A[i])
            colors[idx-1] = A[i]


print(len(colors))

Fixed submission:
import bisect

N = int(input())
A = [int(input()) for _ in range(N)]


colors = []

#後ろから見ていく
for i,n in enumerate(list(reversed(A))):
    # 一つ目はとりあえずなんか一色ぬる
    if i == 0:
        colors.append(n)
    else:
        #二つ目以降は、各色の最小値のなかで、今見ているのより小さいものがあればそれを置き換える
        #ここをbisect_leftにすると、colorsの中で同じ最小値があるときにinsertが必要なので遅い
        # 「各色の最小値集合の最小値と置き換える」を繰り返すので、最小値集合の最大より大きいなら最後に追加
        idx = bisect.bisect_right(colors, n)
        if idx == len(colors):
            colors.append(n)
        else:
            colors[idx] = n

print(len(colors))
Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np

n = int(input())

A = list(map(int, input().split()))
A = np.array(A)

d = [[0 for _ in range(n)] for _ in range(n)]

for i in range(n):
    if i != n-1:
        d[i][i] =0.5
        d[i][i+1]=0.5
    else:
        d[i][0] = 0.5
        d[i][i] = 0.5

d = np.array(d)

ans = np.dot(np.linalg.inv(d), A.T)
ans = np.array(ans, dtype="int")
ans = (ans.T).tolist()

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

Fixed submission:
n = int(input())
a = list(map(int, input().split()))
ans = [0 for _ in range(n)]
total_rain = sum(a)
tmp = total_rain

#一つ飛ばしで合計から引いていく。
#X1 = S − (X2 + ... + XN ) = S − 2(A2 + A4 + ... + AN−1)がtmp
for r in a[:-1:2]:
  tmp -= r*2
  

#tmp=XN+1なのでX1も漸化式から計算
ans[-1] = tmp
ans[0] = a[-1] * 2 - tmp

tmp = ans[0]
#Xi+1 = 2Ai − Xi で他を求める
#i=n-1の時に最後もちゃんと更新される
for i in range(1, n-1):
    ans[i] = 2 * a[i-1] - ans[i-1]

print(*ans)
Buggy python submission (verdict: Runtime Error):
from operator import mul
from functools import reduce

def nCr(n,r):
    if n == r:
        return 1
    r = min(n-r,r)
    if r == 0: return 1
    # reduceは第一引数で与えた関数を第二引数のiterbleのそれぞれで実行した結果をもどす
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under



MOD = 10**9+7
N,K = map(int, input().split())

for i in range(1, K+1):
    blue = nCr(K-1, i-1)
    red = nCr(N-K+1, i)
    print(blue*red%MOD)

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

def nCr(n,r):
  if n < 0 or r < 0 or n < r: return 0
  if n - r < r: r = n - r
  if r == 0: return 1
  if r == 1: return n
  
  # 分子のn*(n-1)*...がr個分続くやつ
  numerator = [n-r+k+1 for k in range(r)]
  # 分母：r!=r*(r-1)*...*3*2の要素
  denominator = [k+1 for k in range(r)]
  
  # 分母の要素で割れる部分を割っていく部分
  for p in range(2, r+1):
    # 分母は1,2,3,...rのようになっており、1は意味がないのでスキップした形か
    pivot = denominator[p-1]
    if pivot > 1:
      # 分子のX番目と分母のX-offset番目が共通の約数を持つということだと思う。piv分ずれているのだから、pivの倍数というところか
      offset = (n-r) % p
      for k in range(p-1, r, p):
        # 約分できる要素について割る
        numerator[k - offset]  /= pivot
        denominator[k] /= pivot
        
  ret = 1
  for k in range(r):
    if numerator[k] > 1: ret *= int(numerator[k])
      
  return ret

def nPr(n,r):
    tmp = 1
    for i in range(n,n-r,-1):
        tmp *= i
    return tmp

for i in range(1, K+1):
    sukima = nCr(N-K+1, i)
    p = nPr(K-1, i-1) // nPr(i-1, i-1)
    print(sukima*p%(10**9+7))

Buggy python submission (verdict: Runtime Error):
from operator import mul
from functools import reduce

def nCr(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    # reduceは第一引数で与えた関数を第二引数のiterbleのそれぞれで実行した結果をもどす
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under



MOD = 10**9+7
N,K = map(int, input().split())

for i in range(1, K+1):
    blue = nCr(K-1, i-1)
    red = nCr(N-K+1, i)
    print(blue*red%MOD)

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

def nCr(n,r):
  if n < 0 or r < 0 or n < r: return 0
  if n - r < r: r = n - r
  if r == 0: return 1
  if r == 1: return n
  
  # 分子のn*(n-1)*...がr個分続くやつ
  numerator = [n-r+k+1 for k in range(r)]
  # 分母：r!=r*(r-1)*...*3*2の要素
  denominator = [k+1 for k in range(r)]
  
  # 分母の要素で割れる部分を割っていく部分
  for p in range(2, r+1):
    # 分母は1,2,3,...rのようになっており、1は意味がないのでスキップした形か
    pivot = denominator[p-1]
    if pivot > 1:
      # 分子のX番目と分母のX-offset番目が共通の約数を持つということだと思う。piv分ずれているのだから、pivの倍数というところか
      offset = (n-r) % p
      for k in range(p-1, r, p):
        # 約分できる要素について割る
        numerator[k - offset]  /= pivot
        denominator[k] /= pivot
        
  ret = 1
  for k in range(r):
    if numerator[k] > 1: ret *= int(numerator[k])
      
  return ret

def nPr(n,r):
    tmp = 1
    for i in range(n,n-r,-1):
        tmp *= i
    return tmp

for i in range(1, K+1):
    sukima = nCr(N-K+1, i)
    p = nPr(K-1, i-1) // nPr(i-1, i-1)
    print(sukima*p%(10**9+7))
Buggy python submission (verdict: Runtime Error):


w,h,x,y = map(int, input().split())


if y/x == h/w:
    num = 1
else:
    num = 0

print(h*w/2, num)

Fixed submission:
w,h,x,y = map(int, input().split())


if w == 0 or h == 0:
    print(0,0)

if x == 0 or y == 0:
    print(h*w/2, 0)
else:
    if y/x == h/w:
        if x != w and y != h:
            num = 1
        else:
            num = 0
    else:
        num = 0

    print(h*w/2, num)
Buggy python submission (verdict: Runtime Error):



"""
・あるボールから（p,q）の移動で別のボールに移れるならコストが０、そうでなければ１
　→あるボールの位置(x,y) + (p,q) の位置にボールがあるかどうか、全てのボールについて確認する。なければコスト＋１
・p,qの選び方は、全ボールの間隔を試すと行けそう(N <= 50 なので間に合いそう)

"""



N = int(input())
xy = [tuple(map(int, input().split())) for _ in range(N)]

pq = []
for i in range(N):
    for j in range(N):
        if i != j:
            pq.append((xy[i][0] - xy[j][0], xy[i][1] - xy[j][1]))


ans = N
for p,q in pq:
    cost = 0
    for x,y in xy:
        if  (x+p, y+q) not in xy:
            cost += 1

    ans = min(ans, cost)

print(cost)

Fixed submission:


N = int(input())
xy = [tuple(map(int, input().split())) for _ in range(N)]

pq = []
for i in range(N):
    for j in range(N):
        if i != j:
            pq.append((xy[i][0] - xy[j][0], xy[i][1] - xy[j][1]))


ans = N
for p,q in pq:
    cost = 0
    for x,y in xy:
        if  (x+p, y+q) not in xy:
            cost += 1

    ans = min(ans, cost)

print(ans)

Buggy python submission (verdict: Runtime Error):



N = int(input())
xy = [tuple(map(int, input().split())) for _ in range(N)]

"""
・あるボールから（p,q）の移動で別のボールに移れるならコストが０、そうでなければ１
　→あるボールの位置(x,y) + (p,q) の位置にボールがあるかどうか、全てのボールについて確認する。なければコスト＋１
・p,qの選び方は、全ボールの間隔を試すと行けそう(N <= 50 なので間に合いそう)

"""


pq = []
for i in range(N):
    for j in range(N):
        if i != j:
            # 同じ間隔（同じp,qのパターン）が起こりうるのでdictで管理するほうがいいかも
            pq.append((xy[i][0] - xy[j][0], xy[i][1] - xy[j][1]))

set_xy = set(xy)
ans = N
for p,q in pq:
    cost = 0
    for x,y in xy:
        if  (x+p, y+q) not in set_xy:
            cost += 1

    ans = min(ans, cost)

print(cost)

Fixed submission:


N = int(input())
xy = [tuple(map(int, input().split())) for _ in range(N)]

pq = []
for i in range(N):
    for j in range(N):
        if i != j:
            pq.append((xy[i][0] - xy[j][0], xy[i][1] - xy[j][1]))


ans = N
for p,q in pq:
    cost = 0
    for x,y in xy:
        if  (x+p, y+q) not in xy:
            cost += 1

    ans = min(ans, cost)

print(ans)
Buggy python submission (verdict: Runtime Error):

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

s = input()

#すぬけ君のゴールがふぬけ君より右にある場合
if c > d:
  #ゴールより左かつふぬけ君の右に岩のない部分が3つ連続していれば、すぬけ君はふぬけ君を追い越すことができる
  if s[a:c].count("##") == 0 and s[b:d].count("##") == 0:
    if s[b-1:d+1].count("...") >= 1:
      print("Yes")
    else:
      print("No")
  else:
    print("No")
else:
  s[a:c].count("##") == 0 and s[b:d].count("##") == 0:
    print("Yes")
  else:
    print("No")

Fixed submission:
n,a,b,c,d = map(int, input().split())
a -= 1
b -= 1
s = input()
ans = "No"
snk = s[a:c].count("##")
fnk = s[b:d].count("##")
if snk == 0 and fnk == 0:
  if c > d:
    if s[b-1:d+1].count("...") >= 1:
      ans = "Yes"
  else:
    ans = "Yes"
    
print(ans)

Buggy python submission (verdict: Runtime Error):
n,a,b,c,d = map(int, input().split())
​
s = input()
​
​
#すぬけ君のゴールがふぬけ君より右にある場合
if c > d:
  #ゴールより左かつふぬけ君の右に岩のない部分が3つ連続していれば、すぬけ君はふぬけ君を追い越すことができる
  if s[a:].count("##") == 0:
    if s[b-1:d+1].count("...") >= 1:
      print("Yes")
    else:
      print("No")
  else:
    print("No")
else:
  if s[a:].count("##") == 0:
    print("Yes")
  else:
    print("No")

Fixed submission:
n,a,b,c,d = map(int, input().split())
a -= 1
b -= 1
s = input()
ans = "No"
snk = s[a:c].count("##")
fnk = s[b:d].count("##")
if snk == 0 and fnk == 0:
  if c > d:
    if s[b-1:d+1].count("...") >= 1:
      ans = "Yes"
  else:
    ans = "Yes"
    
print(ans)
Buggy python submission (verdict: Runtime Error):
N,K = map(int, input().split())
V = list(map(int, input().split()))

ans = 0
nums = min(N, K)
for i in range(nums+1): # 左端から取り出す回数
    for j in range(nums+1-i): # 右端から取り出す回数
        for k in range(nums+1-i-j): # Dに戻す個数
            L = V[:i]
            R = V[N-j:]
            #print(L, R, i, j, k)
            if L == []: L = [0]
            if R == []: R = [0]
            LR = L + R
            LR.sort()
            cnt = 0
            while cnt < k:
                if LR[cnt] < 0:
                    cnt += 1
                else:
                    break
            ans = max(ans, sum(LR[cnt:]))

print(ans)

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

ans = 0

for i in range(N+1): # 左端から取り出す回数
    for j in range(N+1-i): # 右端から取り出す回数
        L = V[:i]
        if j == 0:
            R = []
        else:
            R = V[-j:]
        LR = L + R
        if len(LR) > K:
            continue
        num_drop = min(len(LR), K-i-j)
        LR.sort()
        total = sum(LR)
        idx = 0
        while idx < num_drop:
            if LR[idx] < 0:
                total -= LR[idx]
                idx += 1
            else:
                break
        ans = max(ans, total)


print(ans)

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

ans = 0
nums = min(N, K)
for i in range(nums): # 左端から取り出す回数
    for j in range(nums-i): # 右端から取り出す回数
        for k in range(nums-i-j): # Dに戻す個数
            L = V[:i]
            R = V[N-j:]
            if L == []: L = [0]
            if R == []: R = [0]
            LR = L + R
            LR.sort()
            cnt = 0
            while cnt <= k:
                if LR[cnt] < 0:
                    cnt += 1
                else:
                    break
            ans = max(ans, sum(LR[cnt:]))

print(ans)

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

ans = 0

for i in range(N+1): # 左端から取り出す回数
    for j in range(N+1-i): # 右端から取り出す回数
        L = V[:i]
        if j == 0:
            R = []
        else:
            R = V[-j:]
        LR = L + R
        if len(LR) > K:
            continue
        num_drop = min(len(LR), K-i-j)
        LR.sort()
        total = sum(LR)
        idx = 0
        while idx < num_drop:
            if LR[idx] < 0:
                total -= LR[idx]
                idx += 1
            else:
                break
        ans = max(ans, total)


print(ans)
Buggy python submission (verdict: Runtime Error):



N = int(input())
es = [[] for _ in range(N)]

for i in range(N-1):
    u,v,w = map(int, input().split())
    u,v = u-1, v-1
    es[u].append((v,w))
    es[v].append((u,w))


ans = [-1] * N

def dfs(node, c):

    ans[node] = c
    for next,w in es[node]:
        # 未着色であれば
        if ans[next] == -1:
            if w % 2 == 0:
                # 距離が偶数なら同じ色
                dfs(next, c)
            else:
                # 距離が異なるなら違う色
                if c == 0:
                    dfs(next, 1)
                else:
                    dfs(next, 0)

dfs(0,0)

print(*ans, sep="\n")



Fixed submission:
N = int(input())

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

for i in range(N-1):
    u,v,w = map(int, input().split())

    es[u-1].append((v-1,w))
    es[v-1].append((u-1,w))

ans = [-1] * N

ans[0] = 0

queue = [0]

while len(queue) > 0:
    next_queue = []
    for curr in queue:
        for next,w in es[curr]:
            if ans[next] == -1:
                    next_queue.append(next)
                    if w % 2 == 0:
                        ans[next] = ans[curr]
                    else:
                        ans[next] = 1 if ans[curr] == 0 else 0

    if len(next_queue) > 0:
        queue = next_queue
    else:
        queue = []

print(*ans, sep="\n")

Buggy python submission (verdict: Runtime Error):



N = int(input())
es = [[] for _ in range(N)]

for i in range(N-1):
    u,v,w = map(int, input().split())
    u,v = u-1, v-1
    es[u].append((v,w))
    es[v].append((u,w))


ans = [-1] * N

def dfs(node, c):

    ans[node] = c
    for next,w in es[node]:
        # 未着色であれば
        if ans[next] == -1:
            if w % 2 == 0:
                # 距離が偶数なら同じ色
                dfs(next, c)
            else:
                # 距離が異なるなら違う色
                if c == 0:
                    dfs(next, 1)
                else:
                    dfs(next, 0)

dfs(0,0)

print(ans, sep="\n")



Fixed submission:
N = int(input())

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

for i in range(N-1):
    u,v,w = map(int, input().split())

    es[u-1].append((v-1,w))
    es[v-1].append((u-1,w))

ans = [-1] * N

ans[0] = 0

queue = [0]

while len(queue) > 0:
    next_queue = []
    for curr in queue:
        for next,w in es[curr]:
            if ans[next] == -1:
                    next_queue.append(next)
                    if w % 2 == 0:
                        ans[next] = ans[curr]
                    else:
                        ans[next] = 1 if ans[curr] == 0 else 0

    if len(next_queue) > 0:
        queue = next_queue
    else:
        queue = []

print(*ans, sep="\n")
Buggy python submission (verdict: Runtime Error):

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

print(n-l+1)

Fixed submission:

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

print(n-k+1)
Buggy python submission (verdict: Time Limit Exceeded):

from functools import reduce

def gcd(a,b):
  x = max([a,b])
  y = min([a,b])
  while y:
    x, y = y, x % y
  return x

def gcd_list(nums):
  return reduce(gcd, nums)

n = int(input())

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


ans = 0
for i in range(n):
      tmp_list = a[:i] + (a[i+1:])
      #print(tmp_list)
      tmp = gcd_list(tmp_list)
      if ans < tmp:
            ans = tmp

print(ans)


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


def gcd(a,b):
  x = max([a,b])
  y = min([a,b])
  while y:
    x, y = y, x % y
  return x

L = [0]
R = [0]

for i in range(N):
    L.append(gcd(L[-1], A[i]))
    
for i in reversed(range(N)):
    R.append(gcd(R[-1], A[i]))

R = list(reversed(R))


ans = 1
for i in range(N-1):
    ans = max(ans, gcd(L[i], R[i+1]))

ans = max(ans, R[1])
ans = max(ans, L[-2])

print(ans)
#print(R)
#print(L)
Buggy python submission (verdict: Time Limit Exceeded):

n = int(input())

s = list(input())
b = 0
w = 0

for i in range(n-1):
  if s[i] == "#" and s[i+1] == ".":
    b = max(b, s[:i+1].count("#"))
    w = max(w, s[i+1:].count("."))

print(min(b,w))
   

Fixed submission:
N = int(input())
S = input()

cum_lw = [0] * N
cum_rw = [0] * N

if S[0] == ".":
    cum_lw[0] = 1

if S[-1] == ".":
    cum_rw[-1] = 1 

for i in range(1,N):
    if S[i] == ".":
        cum_lw[i] = cum_lw[i-1] + 1
    else:
        cum_lw[i] = cum_lw[i-1]

    if S[N-1-i] == ".":
        cum_rw[N-1-i] = cum_rw[N-i] + 1
    else:
         cum_rw[N-1-i] = cum_rw[N-i]

ans = N
for i in range(N):
    if i != N-1:
        bb = cum_lw[i] + cum_rw[i+1]
        wb = (i+1)-cum_lw[i] + cum_rw[i+1]
        ww = (i+1)-cum_lw[i] + (N-1-i)-cum_rw[i+1]
    else:
        bb = cum_lw[i]
        wb = (i+1)-cum_lw[i]
        ww = (i+1)-cum_lw[i]
    ans = min([ans, bb, wb, ww])

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)


"""
愚直解
X*Y*Z全部作って上から順にK個書き出す。普通に間に合わない
愚直解のいけてない部分として、X*Yを作った段階で、他のX*Yよりずっと小さいときに、Zとの積を見るまでもなくK番目までに入らないケースがある。
なんというか、　X*Y*Z　を　W*Z (W=X*Y)と置き換えたときに、Wの中で順位が低いものとZとの積を計算して他と比較する意味がない。
W = [9,8,7,6,5,4,3]
Z = [6,4,3,2,1]
K = 5
とかで考えると、Wが3や4のものは見る必要がない。
というのも、それより大きいWがK個以上あることが分かっているので、W*ZもK個以上大きいものが存在するといえるので。

なので、先にX*Yを計算して、その中で上位K個とZの積をとってさらにK個選べばいけそう


"""
W = []
for a in A:
    for b in B:
        W.append(a+b)

W.sort(reverse=True)
if len(W) > K:
    W = W[:K]
ans = []
for w in W:
    for c in C:
        ans.append(w+c)

ans.sort(reverse=True)
print(*ans[:K], sep="\n")

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)

abc = []

for i in range (x):
      for j in range(y):
            for(k) in range(z):
                  if (i+1)*(j+1)*(k+1) <= K:
                        abc.append(a[i]+b[j]+c[k])
                  else:
                        break

abc.sort(reverse=True)
for i in abc[:K]:
      print(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)
E = [0] * x*y

total = [0] * (x*y + z*k)
idx = 0
for i in range(x):
      for j in range(y):
            E[idx] = a[i] + b[j]
            idx += 1
E.sort(reverse=True)
idx = 0
for i in range(min(x*y,k)):
      for j in range(min(z,k)):
            total[idx] = E[i] + c[j]
            idx += 1

total.sort(reverse=True)
for i in range(k):
      print(total[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)

abc = []

for i in range (x):
      for j in range(y):
            for(k) in range(z):
                  if (i+1)*(j+1)*(k+1) <= K:
                        abc.append(a[i]+b[j]+c[k])
                  else:
                        break

abc.sort(reverse=True)
for i in abc[:K]:
      print(i)
Buggy python submission (verdict: Time Limit Exceeded):
n,q = map(int, input().split())
s = input()


num_ac = [0] * n

for i in range(n):
    num_ac[i] = s[:i+1].count("AC")

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

for a in ans:
    print(a)



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


num_ac = [0] * n
num_ac[0] = 0
if s[0] == "A" and s[1] == "C":
    num_ac[1] = 1


for i in range(2,n):
    if s[i-1] == "A" and s[i] == "C":
        num_ac[i] = num_ac[i-1] + 1
    else:
        num_ac[i] = num_ac[i-1]

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

for a in ans:
    print(a)