Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
from collections import deque

H,W = list(map(int, input().split()))
S = [input() for _ in range(H)]
dist = [[0] * W for i in range(H)]
dist[0][0] = 1

whites = 0
for s in S:
    for w in s:
        if w == ".":
            whites += 1

# Pythonの再帰はおっっそい. 再帰が今回のケースだと使いにくい(探索打ち切り)
def BFS(cur):
    #global dist
    x_path = [-1,0,1,0]
    y_path = [0,-1,0,1]

    q = deque()
    q.append(cur)
    while True:
        cur = q.popleft()
        if cur == (H,W):
            break

        for x,y in zip(x_path, y_path):
            nex = (cur[0] + x, cur[1] + y)
            if nex[0] < 1 or nex[0] > H or nex[1] < 1 or nex[1] > W:
                continue
            if S[nex[0]-1][nex[1]-1] == "#":
                continue
            if dist[nex[0]-1][nex[1]-1] > 0:
                continue

            dist[nex[0]-1][nex[1]-1] = dist[cur[0]-1][cur[1]-1] + 1 
            q.append(nex)


BFS((1,1))

print(whites - dist[H-1][W-1])


Fixed submission:
from collections import deque

H,W = list(map(int, input().split()))
S = [input() for _ in range(H)]
dist = [[0] * W for i in range(H)]
dist[0][0] = 1

whites = 0
for s in S:
    for w in s:
        if w == ".":
            whites += 1

# Pythonの再帰はおっっそい. 再帰が今回のケースだと使いにくい(探索打ち切り)
def BFS(cur):
    #global dist
    x_path = [-1,0,1,0]
    y_path = [0,-1,0,1]

    q = deque()
    q.append(cur)
    while True:
        if len(q) == 0:
            break
        cur = q.popleft()
        if cur == (H,W):
            break

        for x,y in zip(x_path, y_path):
            nex = (cur[0] + x, cur[1] + y)
            if nex[0] < 1 or nex[0] > H or nex[1] < 1 or nex[1] > W:
                continue
            if S[nex[0]-1][nex[1]-1] == "#":
                continue
            if dist[nex[0]-1][nex[1]-1] > 0:
                continue

            dist[nex[0]-1][nex[1]-1] = dist[cur[0]-1][cur[1]-1] + 1 
            q.append(nex)


BFS((1,1))
if dist[H-1][W-1] == 0:
    print(-1)
else:
    print(whites - dist[H-1][W-1])
Buggy python submission (verdict: Time Limit Exceeded):

def main():
    N, H = list(map(int, input().split()))
    a_max = 0
    b_list = []

    for _ in range(N):
        a,b = list(map(int, input().split()))
        a_max = max(a, a_max)
        b_list.append(b)

    b_list = sorted(b_list)[::-1]
    
    cnt = 0
    while H > 0:
        H -= b_list.pop(0) if len(b_list) > 0 and b_list[0] > a_max else a_max
        cnt += 1
    print(cnt)

if __name__ == "__main__":
    main()


Fixed submission:
# ABC85 D 
import math

def main():
    N, H = list(map(int, input().split()))
    a_max = 0
    b_list = []

    for _ in range(N):
        a,b = list(map(int, input().split()))
        a_max = max(a, a_max)
        b_list.append(b)

    b_list = sorted(b_list)[::-1]
    
    cnt = 0
    for b in b_list:
        if b < a_max:
            break
        if H <= 0:
            break
        H -= b
        cnt += 1
    
    if H > 0:
        print(cnt + math.ceil(H / a_max))
    else:
        print(cnt)

if __name__ == "__main__":
    main()
Buggy python submission (verdict: Runtime Error):
N = int(input())
L0 = 2
L1 = 1
if N == 1:
    print(L1)

for i in range(1,N):
    res = L0 + L1
    L0 = L1
    L1 = res

print(res)

Fixed submission:
N = int(input())
L0 = 2
L1 = 1
if N == 1:
    print(L1)
    exit()

for i in range(1,N):
    res = L0 + L1
    L0 = L1
    L1 = res

print(res)

Buggy python submission (verdict: Runtime Error):
N = int(input())
L0 = 2
L1 = 1

for i in range(1,N):
    res = L0 + L1
    L0 = L1
    L1 = res

print(res)

Fixed submission:
N = int(input())
L0 = 2
L1 = 1
if N == 1:
    print(L1)
    exit()

for i in range(1,N):
    res = L0 + L1
    L0 = L1
    L1 = res

print(res)
Buggy python submission (verdict: Runtime Error):
import bisect

N = int(input())
As = sorted(list(map(int, input().split())))
Bs = sorted(list(map(int, input().split())))
Cs = sorted(list(map(int, input().split())))

# BとCのセットだけ見てありえるパターンを出す
# B_Csは注目要素より右側の和
B_Cs = [0] * N

prev = N - bisect.bisect_left(Cs, Bs[-1])
B_Cs[-1] = prev
for i, b in enumerate(reversed(Bs)):
    if i == 0 :
        continue
    rev_i = N - i -1
    index = bisect.bisect_left(Cs, b+1)
    
    prev = (N - index) + prev
    B_Cs[rev_i] = prev

cnt = 0
for i, a in enumerate(As):
    index = bisect.bisect_left(Bs, a+1)
    cnt += B_Cs[index]
print(cnt)

Fixed submission:
import bisect

N = int(input())
As = sorted(list(map(int, input().split())))
Bs = sorted(list(map(int, input().split())))
Cs = sorted(list(map(int, input().split())))

cnt = 0
for b in Bs:
    a_b = bisect.bisect_left(As,b)
    b_c = N - bisect.bisect_right(Cs, b)
    
    cnt += a_b * b_c
print(cnt)

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

N = int(input())
As = sorted(list(map(int, input().split())))
Bs = sorted(list(map(int, input().split())))
Cs = sorted(list(map(int, input().split())))

# BとCのセットだけ見てありえるパターンを出す
B_Cs = [0] * N
for i, b in enumerate(Bs):
    index = bisect.bisect_left(Cs, b+1)
    B_Cs[i] = (N - index)

cumsum_BC =[sum(B_Cs[i:]) for i in range(N)]

cnt = 0
for i, a in enumerate(As):
    index = bisect.bisect_left(Bs, a+1)
    cnt += cumsum_BC[index]
print(cnt)

Fixed submission:
import bisect

N = int(input())
As = sorted(list(map(int, input().split())))
Bs = sorted(list(map(int, input().split())))
Cs = sorted(list(map(int, input().split())))

cnt = 0
for b in Bs:
    a_b = bisect.bisect_left(As,b)
    b_c = N - bisect.bisect_right(Cs, b)
    
    cnt += a_b * b_c
print(cnt)

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

N = int(input())
As = sorted(list(map(int, input().split())))
Bs = sorted(list(map(int, input().split())))
Cs = sorted(list(map(int, input().split())))

# BとCのセットだけ見てありえるパターンを出す
B_Cs = []
for b in Bs:
    index = bisect.bisect_left(Cs, b+1)
    B_Cs.append(N - index)

cnt = 0
for i, a in enumerate(As):
    index = bisect.bisect_left(Bs, a+1)
    cnt += sum(B_Cs[index:])
print(cnt)

Fixed submission:
import bisect

N = int(input())
As = sorted(list(map(int, input().split())))
Bs = sorted(list(map(int, input().split())))
Cs = sorted(list(map(int, input().split())))

cnt = 0
for b in Bs:
    a_b = bisect.bisect_left(As,b)
    b_c = N - bisect.bisect_right(Cs, b)
    
    cnt += a_b * b_c
print(cnt)
Buggy python submission (verdict: Runtime Error):
N, M = list(map(int, input().split()))
lines = [list(map(int, input().split())) for _ in range(M)]

graph = [[False] * N for _ in range(N)]
for a,b in lines:
    graph[a-1][b-1] = graph[b-1][a-1] = True

visited = [False for _ in range(N)]

def DFS(v):
    visited[v] = True
    for from_v in range(N):
        if not graph[v][from_v]:
            continue
        if visited[from_v]:
            continue
        DFS(from_v)
    
cnt = 0
for i in range(M):
    pass_a, pass_b = lines[i]
    pass_a -= 1
    pass_b -= 1
    graph[pass_a][pass_b] = graph[pass_b][pass_a] = False
    DFS(i)
    
    cnt += 1 if False in visited else 0
    
    visited = [False for _ in range(N)]
    graph[pass_a][pass_b] = graph[pass_b][pass_a] = True

print(cnt)

Fixed submission:
N, M = list(map(int, input().split()))
lines = [list(map(int, input().split())) for _ in range(M)]

graph = [[False] * N for _ in range(N)]
for a,b in lines:
    graph[a-1][b-1] = graph[b-1][a-1] = True

visited = [False for _ in range(N)]

def DFS(v):
    visited[v] = True
    for from_v in range(N):
        if not graph[v][from_v]:
            continue
        if visited[from_v]:
            continue
        DFS(from_v)
    
cnt = 0
for i in range(M):
    pass_a, pass_b = lines[i]
    pass_a -= 1
    pass_b -= 1
    graph[pass_a][pass_b] = graph[pass_b][pass_a] = False
    DFS(pass_a)
    
    cnt += 1 if False in visited else 0
    
    visited = [False for _ in range(N)]
    graph[pass_a][pass_b] = graph[pass_b][pass_a] = True

print(cnt)
Buggy python submission (verdict: Runtime Error):
s=map(int, input().split())
print("Yes" if s[0]==s[-1] else "No")

Fixed submission:
s= input()
print("Yes" if s[0]==s[-1] else "No")
Buggy python submission (verdict: Runtime Error):
# a < b
def gcd(a,b):
    if b % a == 0:
        return a
    return gcd(b % a, a)

def lcm(a,b):
    return int(a*b/gcd(a,b))

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

ret = 1
for t in T:
    ret = lcm(ret, t)
print(ret)

Fixed submission:
# a < b
def gcd(a,b):
    if b % a == 0:
        return a
    return gcd(b % a, a)

def lcm(a,b):
    return a*b//gcd(a,b)

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

ret = 1
for t in T:
    ret = lcm(ret, t)
print(ret)
Buggy python submission (verdict: Time Limit Exceeded):
from scipy.sparse.csgraph import dijkstra, csgraph_from_dense, floyd_warshall
xs,ys,xg,yg = map(int, input().split())
N = int(input())
xyr = [(xs,ys,0)]
xyr.extend([list(map(int, input().split())) for i in range(N)])
xyr.append((xg,yg,0))
graph = [[0] * (N+2) for _ in range(N+2)]

max_val = 10**9

for i in range(N+2):
    graph[i][i] = max_val

for i in range(N+2):
    for j in range(i+1,N+2):
        x1,y1,r1 = xyr[i]
        x2,y2,r2 = xyr[j]
        d = max(0, ((x1-x2)**2 + (y1-y2)**2) ** 0.5 - r1 - r2)
        graph[i][j] = graph[j][i] = d

g = csgraph_from_dense(graph,null_value=max_val)
dij = dijkstra(g)
print(dij[0][-1])

Fixed submission:
from scipy.sparse.csgraph import dijkstra, csgraph_from_dense
xs,ys,xg,yg = map(int, input().split())
N = int(input())
xyr = [(xs,ys,0)]
xyr.extend([list(map(int, input().split())) for i in range(N)])
xyr.append((xg,yg,0))
graph = [[0] * (N+2) for _ in range(N+2)]

max_val = 10**9

for i in range(N+2):
    graph[i][i] = max_val

for i in range(N+2):
    for j in range(i+1,N+2):
        x1,y1,r1 = xyr[i]
        x2,y2,r2 = xyr[j]
        d = max(0, ((x1-x2)**2 + (y1-y2)**2) ** 0.5 - r1 - r2)
        graph[i][j] = graph[j][i] = d

g = csgraph_from_dense(graph,null_value=max_val)
print(dijkstra(g,indices=0)[-1])

Buggy python submission (verdict: Time Limit Exceeded):
from scipy.sparse.csgraph import dijkstra, csgraph_from_dense, floyd_warshall
xs,ys,xg,yg = map(int, input().split())
N = int(input())
xyr = [(xs,ys,0)]
xyr.extend([list(map(int, input().split())) for i in range(N)])
xyr.append((xg,yg,0))
graph = [[0] * (N+2) for _ in range(N+2)]

max_val = 10**9

for i in range(N+2):
    graph[i][i] = max_val

for i in range(N+2):
    for j in range(i+1,N+2):
        x1,y1,r1 = xyr[i]
        x2,y2,r2 = xyr[j]
        d = max(0, ((x1-x2)**2 + (y1-y2)**2) ** 0.5 - r1 - r2)
        graph[i][j] = graph[j][i] = d


g = csgraph_from_dense(graph,null_value=max_val)

dij = dijkstra(g)
flo = floyd_warshall(g)
print(dij[0][-1])

Fixed submission:
from scipy.sparse.csgraph import dijkstra, csgraph_from_dense
xs,ys,xg,yg = map(int, input().split())
N = int(input())
xyr = [(xs,ys,0)]
xyr.extend([list(map(int, input().split())) for i in range(N)])
xyr.append((xg,yg,0))
graph = [[0] * (N+2) for _ in range(N+2)]

max_val = 10**9

for i in range(N+2):
    graph[i][i] = max_val

for i in range(N+2):
    for j in range(i+1,N+2):
        x1,y1,r1 = xyr[i]
        x2,y2,r2 = xyr[j]
        d = max(0, ((x1-x2)**2 + (y1-y2)**2) ** 0.5 - r1 - r2)
        graph[i][j] = graph[j][i] = d

g = csgraph_from_dense(graph,null_value=max_val)
print(dijkstra(g,indices=0)[-1])
Buggy python submission (verdict: Runtime Error):
S = input()
K = int(input())
z = ord('z') + 1

res = ""
flg = False
for i,c in enumerate(S):
    if z - ord(c) <= K:
        res += 'a'
        K -= z-ord(c)
    else:
        res += chr(ord(c))

res = res[:-1] + chr(ord(res[-1]) + K)
print(res)


Fixed submission:
S = input()
K = int(input())
z = ord('z') + 1

res = ""
flg = False
for i,c in enumerate(S):
    if c == 'a':
        res += 'a'
        continue
    elif z - ord(c) <= K:
        res += 'a'
        K -= z-ord(c)
    else:
        res += chr(ord(c))

res = res[:-1] + chr((ord(res[-1])-ord('a') + K) % 26 + ord('a'))
print(res)
Buggy python submission (verdict: Runtime Error):
from itertools import accumulate

S = int(input())
mod = 10**9 + 7
dp = [0] * (S + 1)
dp[0] = 1
ans = 0
for i in range(S):
    cum = list(accumulate(dp))
    for j in range(S, 2, -1):
        dp[j] = cum[j-3] % mod
    dp[0] = dp[1] = dp[2] = 0
    ans = (ans + dp[S]) % mod
print(ans)

Fixed submission:
from itertools import accumulate

S = int(input())
mod = 10**9 + 7
if S == 1 or S == 2:
    print(0)
    exit()
dp = [0] * (S + 1)
dp[0] = 1
ans = 0
for i in range(S):
    cum = list(accumulate(dp))
    for j in range(S, 2, -1):
        dp[j] = cum[j-3] % mod
    dp[0] = dp[1] = dp[2] = 0
    ans = (ans + dp[S]) % mod
print(ans)
Buggy python submission (verdict: Runtime Error):
from collections import deque
import sys
input = sys.stdin.readline

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
cntA = [0] * (N + 1)
cntB = [0] * (N + 1)
for i in range(N):
    cntA[A[i]] += 1
    cntB[B[i]] += 1
nums = [(cntA[i], cntB[i], i) for i in range(1, N+1)]
nums.sort(key=lambda p: p[0] + p[1], reverse=True)
a = deque()
b = deque()
c = deque(list(range(N)))
ansa = [0] * N
ansb = [0] * N
for x, y, n in nums:
    if x == y == 0:
        break
    if x + y > len(a) + len(b) + len(c):
        print('No')
        exit()
    if x + y <= len(c):
        for i in range(x):
            ansa[c[0]] = n
            b.append(c[0])
            c.popleft()
        for i in range(y):
            ansb[c[0]] = n
            a.append(c[0])
            c.popleft()
    else:
        m = x - len(a)
        if m > 0:
            for i in range(m):
                ansa[c[0]] = n
                b.append(c[0])
                c.popleft()
            x -= m
        m = len(c)
        for i in range(m):
            ansb[c[0]] = n
            a.append(c[0])
            c.popleft()
        y -= m
        for i in range(x):
            ansa[a[0]] = n
            a.popleft()
        for i in range(y):
            ansb[b[0]] = n
            b.popleft()
ans = []
for i in range(N):
    ans.append((ansa[i], ansb[i]))
ans.sort()
print('Yes')
print(*[p[1] for p in ans])

Fixed submission:
from collections import deque
import sys
input = sys.stdin.readline

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
cntA = [0] * (N + 1)
cntB = [0] * (N + 1)
for i in range(N):
    cntA[A[i]] += 1
    cntB[B[i]] += 1
nums = [(cntA[i], cntB[i], i) for i in range(1, N+1)]
nums.sort(key=lambda p: p[0] + p[1], reverse=True)
a = deque()
b = deque()
c = deque(list(range(N)))
ansa = [0] * N
ansb = [0] * N
for x, y, n in nums:
    if x == y == 0:
        break
    if x + y > len(a) + len(b) + len(c):
        print('No')
        exit()
    if x + y <= len(c):
        for i in range(x):
            ansa[c[0]] = n
            b.append(c[0])
            c.popleft()
        for i in range(y):
            ansb[c[0]] = n
            a.append(c[0])
            c.popleft()
    else:
        ra = x - len(a)
        rb = y - len(b)
        if ra > 0:
            for i in range(ra):
                ansa[c[0]] = n
                b.append(c[0])
                c.popleft()
            x -= ra
        if rb > 0:
            for i in range(rb):
                ansb[c[0]] = n
                a.append(c[0])
                c.popleft()
            y -= rb
        while len(c):
            if x:
                ansa[c[0]] = n
                b.append(c[0])
                x -= 1
            else:
                ansb[c[0]] = n
                a.append(c[0])
                y -= 1
            c.popleft()
        for i in range(x):
            ansa[a[0]] = n
            a.popleft()
        for i in range(y):
            ansb[b[0]] = n
            b.popleft()
ans = []
for i in range(N):
    ans.append((ansa[i], ansb[i]))
ans.sort()
print('Yes')
print(*[p[1] for p in ans])
Buggy python submission (verdict: Time Limit Exceeded):
from heapq import heappush, heappop
import sys
input = sys.stdin.readline

H, W = map(int, input().split())
Ch, Cw = map(lambda x: int(x) - 1, input().split())
Dh, Dw = map(lambda x: int(x) - 1, input().split())
S = [input().rstrip() for _ in range(H)]
visited = [[False] * W for _ in range(H)]
heap = [(0, Ch, Cw)]
while heap:
    d, i, j = heappop(heap)
    if (i, j) == (Dh, Dw):
        print(d)
        exit()
    if visited[i][j]:
        continue
    visited[i][j] = True
    for di, dj in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
        ni, nj = i + di, j + dj
        if 0 <= ni < H and 0 <= nj < W and S[ni][nj] == '.':
            heappush(heap, (d, ni, nj))
    for di in range(-2, 3):
        for dj in range(-2, 3):
            if di == dj == 0:
                continue
            ni, nj = i + di, j + dj
            if 0 <= ni < H and 0 <= nj < W and S[ni][nj] == '.' and not visited[ni][nj]:
                heappush(heap, (d + 1, ni, nj))
print(-1)



Fixed submission:
from collections import deque
import sys
input = sys.stdin.readline

H, W = map(int, input().split())
Ch, Cw = map(lambda x: int(x) - 1, input().split())
Dh, Dw = map(lambda x: int(x) - 1, input().split())
S = [input().rstrip() for _ in range(H)]
visited = [[False] * W for _ in range(H)]
dq = deque([(0, Ch, Cw)])
while dq:
    d, i, j = dq.popleft()
    if (i, j) == (Dh, Dw):
        print(d)
        exit()
    if visited[i][j]:
        continue
    visited[i][j] = True
    for di, dj in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
        ni, nj = i + di, j + dj
        if 0 <= ni < H and 0 <= nj < W and S[ni][nj] == '.':
            dq.appendleft((d, ni, nj))
    for di in range(-2, 3):
        for dj in range(-2, 3):
            if di == dj == 0:
                continue
            ni, nj = i + di, j + dj
            if 0 <= ni < H and 0 <= nj < W and S[ni][nj] == '.' and not visited[ni][nj]:
                dq.append((d + 1, ni, nj))
print(-1)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

R, C, K = map(int, input().split())
INF = 10**18
dp = [[[-INF] * 4 for _ in range(C+1)] for _ in range(R+1)]
items = [[0] * (C+1) for _ in range(R+1)]
dp[1][0][0] = dp[0][1][0] = 0
for _ in range(K):
    r, c, v = map(int, input().split())
    items[r][c] = v
for i in range(1, R+1):
    for j in range(1, C+1):
        for k in range(4):
            dp[i][j][0] = max(dp[i][j][0], dp[i-1][j][k])
            if items[i][j]:
                dp[i][j][1] = max(dp[i][j][1], dp[i-1][j][k] + items[i][j])
            dp[i][j][k] = max(dp[i][j][k], dp[i][j-1][k])
            if items[i][j] and k:
                dp[i][j][k] = max(dp[i][j][k], dp[i][j-1][k-1] + items[i][j])
ans = max(dp[R][C])
print(ans)

Fixed submission:
import sys
input = sys.stdin.readline

R, C, K = map(int, input().split())
items = [[0] * (C+1) for _ in range(R+1)]
for _ in range(K):
    r, c, v = map(int, input().split())
    items[r][c] = v
dp = [[0] * 4 for _ in range(C+1)]
for i in range(1, R+1):
    ndp = [[0] * 4 for _ in range(C+1)]
    for j in range(1, C+1):
        for k in range(4):
            ndp[j][0] = max(ndp[j][0], dp[j][k])
            ndp[j][k] = max(ndp[j][k], ndp[j-1][k])
        if items[i][j]:
            for k in range(3, 0, -1):
                ndp[j][k] = max(ndp[j][k], ndp[j][k-1] + items[i][j])
    dp = ndp
print(max(dp[C]))
Buggy python submission (verdict: Time Limit Exceeded):
import networkx as nx
import sys
input = sys.stdin.readline

T = int(input())
for _ in range(T):
    N = int(input())
    G = nx.MultiDiGraph()
    # s: source t: sink
    # 0 ... N-1: camel
    # N ... 2*N-1: loc1
    # 2*N ... 3*N-1: loc2
    G.add_node('s', demand=-N)
    G.add_node('t', demand=N)
    for i in range(N):
        G.add_edge('s', i, weight=0, capacity=1)
    for i in range(N-1):
        G.add_edge(N+i, N+i+1, weight=0, capacity=i+1)
    for i in range(N-1):
        G.add_edge(2*N+i+1, 2*N+i, weight=0, capacity=N-i-1)
    G.add_edge(2*N-1, 't', weight=0, capacity=N)
    G.add_edge(2*N, 't', weight=0, capacity=N)
    for i in range(N):
        K, L, R = map(int, input().split())
        K -= 1
        G.add_edge(i, N+K, weight=-L, capacity=1)
        if K < N - 1:
            G.add_edge(i, 2*N+K+1, weight=-R, capacity=1)
    print(-nx.min_cost_flow_cost(G))

Fixed submission:
from collections import deque
from heapq import heappush, heappushpop
import sys
input = sys.stdin.readline

def calc(camels):
    camels = deque(sorted(camels, key=lambda x: x[0]))
    N = len(camels)
    heap = []
    while camels and camels[0][0] == 0:
        camels.popleft()
    for i in range(1, N+1):
        while camels and camels[0][0] == i:
            _, x = camels.popleft()
            if len(heap) < i:
                heappush(heap, x)
            elif heap[0] < x:
                heappushpop(heap, x)
    for _, x in camels:
        if len(heap) < N:
            heappush(heap, x)
        elif heap[0] < x:
            heappushpop(heap, x)
    return sum(heap)

T = int(input())
for _ in range(T):
    N = int(input())
    s = 0
    ans = 0
    first = []
    second = []
    for i in range(N):
        K, L, R = map(int, input().split())
        if L >= R:
            first.append((K, L - R))
            ans += R
        else:
            second.append((N - K, R - L))
            ans += L
    ans += calc(first) + calc(second)
    print(ans)
Buggy python submission (verdict: Runtime Error):
from collections import deque
import sys
input = sys.stdin.readline

N, K = map(int, input().split())
A = list(map(int, input().split()))
pos = []
neg = []
for a in A:
    if a >= 0:
        pos.append(a)
    else:
        neg.append(-a)
pos = deque(sorted(pos))
neg = deque(sorted(neg))
mod = 10**9 + 7
ans = 1
sign = 1
if K % 2 == 1:
    if len(pos) > 0:
        ans = ans * pos.pop() % mod
    else:
        ans = ans * neg.popleft() % mod
        sign *= -1
    K -= 1
while K > 0:
    if len(pos) == 1 and len(neg) == 1:
        ans = ans * -neg.pop() * pos.pop() % mod
    if sign == 1:
        if len(pos) < 2 or (len(neg) >= 2 and pos[-2] * pos[-1] < neg[-2] * neg[-1]):
            ans = ans * neg.pop() * neg.pop() % mod
        else:
            ans = ans * pos.pop() * pos.pop() % mod
    else:
        if len(pos) < 2 or (len(neg) >= 2 and pos[-2] * pos[-1] < neg[-2] * neg[-1]):
            ans = ans * neg.popleft() * neg.popleft() % mod
        else:
            ans = ans * pos.popleft() * pos.popleft() % mod
    K -= 2
ans = ans * sign % mod
print(ans)

Fixed submission:
from collections import deque
import sys
input = sys.stdin.readline

N, K = map(int, input().split())
A = list(map(int, input().split()))
pos = []
neg = []
for a in A:
    if a >= 0:
        pos.append(a)
    else:
        neg.append(-a)
pos = deque(sorted(pos))
neg = deque(sorted(neg))
mod = 10**9 + 7
ans = 1
sign = 1
if K % 2 == 1:
    if len(pos) > 0:
        ans = ans * pos.pop() % mod
    else:
        ans = ans * neg.popleft() % mod
        sign *= -1
    K -= 1
while K > 0:
    if len(pos) == 1 and len(neg) == 1:
        ans = ans * -neg.pop() * pos.pop() % mod
    elif sign == 1:
        if len(pos) < 2 or (len(neg) >= 2 and pos[-2] * pos[-1] < neg[-2] * neg[-1]):
            ans = ans * neg.pop() * neg.pop() % mod
        else:
            ans = ans * pos.pop() * pos.pop() % mod
    else:
        if len(pos) < 2 or (len(neg) >= 2 and pos[-2] * pos[-1] < neg[-2] * neg[-1]):
            ans = ans * neg.popleft() * neg.popleft() % mod
        else:
            ans = ans * pos.popleft() * pos.popleft() % mod
    K -= 2
ans = ans * sign % mod
print(ans)