Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
import numpy as np
from collections import defaultdict

def rec(start, p):
    if ans[start] != -1:
        return p
    ans[start] = C[p]
    p += 1
    for node in tree[start+1]:
        p = rec(node-1, p)
    return p

N = int(input())
tree = defaultdict(list)
degree = [0 for i in range(N)]
edges = [0 for i in range(N-1)]
for i in range(N-1):
    a, b = map(int, input().split())
    edges[i] = (a, b)
    tree[a].append(b)
    tree[b].append(a)
for k, v in tree.items():
    degree[k-1] = len(v)
# print(degree)
sort_i = np.argsort(degree)[::-1]
# max_di = sort_i[-1]
# print(sort_i)
C = list(map(int, input().split()))
C = sorted(C, reverse=True)
# C = list(sorted(zip(sorted(C), list(sort_i)),key=lambda x: x[1]))
# print(C[sort_i])
ans = 0
visited_e = []
# start = max_di + 1
visited = [False for i in range(N)]
p = 0
ans = [-1 for i in range(N)]
M = 0

rec(sort_i[0], p)

for e in edges:
    M += min(ans[e[0]-1], ans[e[1]-1])
    # print(ans)
print(M)
print(' '.join(list(map(lambda x: str(x), ans))))


Fixed submission:
import numpy as np
from collections import defaultdict
import sys
sys.setrecursionlimit(10**9)
def rec(start, p):
    if ans[start] != -1:
        return p
    ans[start] = C[p]
    p += 1
    for node in tree[start+1]:
        p = rec(node-1, p)
    return p

N = int(input())
tree = defaultdict(list)
degree = [0 for i in range(N)]
edges = [0 for i in range(N-1)]
for i in range(N-1):
    a, b = map(int, input().split())
    edges[i] = (a, b)
    tree[a].append(b)
    tree[b].append(a)
for k, v in tree.items():
    degree[k-1] = len(v)
# print(degree)
sort_i = np.argsort(degree)[::-1]
# max_di = sort_i[-1]
# print(sort_i)
C = list(map(int, input().split()))
C = sorted(C, reverse=True)
# C = list(sorted(zip(sorted(C), list(sort_i)),key=lambda x: x[1]))
# print(C[sort_i])
ans = 0
visited_e = []
# start = max_di + 1
visited = [False for i in range(N)]
p = 0
ans = [-1 for i in range(N)]
M = 0

rec(sort_i[0], p)

for e in edges:
    M += min(ans[e[0]-1], ans[e[1]-1])
    # print(ans)
print(M)
print(' '.join(list(map(lambda x: str(x), ans))))
Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np
N, M = map(int, input().split())
count_list = np.array([0 for i in range(N+1)])
for i in range(M):
    L, R = map(int, input().split())
    count_list[L:R+1] += 1

print(np.sum(count_list==M))


Fixed submission:
N, M = map(int, input().split())
max_L = -1
min_R = 10**6
for i in range(M):
    L, R = map(int, input().split())
    max_L = max(L, max_L)
    min_R = min(R, min_R)

print(max(min_R - max_L + 1, 0))
Buggy python submission (verdict: Time Limit Exceeded):
N, M = map(int, input().split())
A = list(map(int, input().split()))
min_a = min(A)
for i in range(M):
    B, C = map(int, input().split())
    if min_a < C:
        C = [C for i in range(B)]
        A.extend(C)
A = sorted(A, reverse=True)
print(sum(A[:N]))


Fixed submission:
from collections import Counter
N, M = map(int, input().split())
A = list(map(int, input().split()))
count_a = Counter(A)
A = [(v, k) for k, v in count_a.items()]
for i in range(M):
    B, C = map(int, input().split())
    A.append((B, C))
A = sorted(A, reverse=True, key=lambda x: x[1])
ans = 0
for k, v in A:
    N = N - k
    if N <= 0:
        ans += k*v+N*v
        break
    ans += k*v
print(ans)
Buggy python submission (verdict: Runtime Error):
from collections import defaultdict
def dfs(node_i, oe):
    if ans[node_i] != -1:
        return
    next_nodes = graph[node_i]
    ans[node_i] = oe
    for next_i, cost in next_nodes:
        dfs(next_i, (oe+cost)%2)
        

N = int(input())
ans = [-1 for i in range(N+1)]
graph = defaultdict(list)
for i in range(N-1):
    u, v, w = map(int, input().split())
    graph[u] += [(v, w)]
    graph[v] += [(u, w)]

dfs(1, 0)
for i in range(1, N+1):
    print(ans[i])

Fixed submission:
import sys
sys.setrecursionlimit(10**7)
from collections import defaultdict
def dfs(node_i, oe):
    if ans[node_i] != -1:
        return
    next_nodes = graph[node_i]
    ans[node_i] = oe
    for next_i, cost in next_nodes:
        dfs(next_i, (oe+cost)%2)
        

N = int(input())
ans = [-1 for i in range(N+1)]
graph = defaultdict(list)
for i in range(N-1):
    u, v, w = map(int, input().split())
    graph[u] += [(v, w)]
    graph[v] += [(u, w)]

dfs(1, 0)
for i in range(1, N+1):
    print(ans[i])
Buggy python submission (verdict: Time Limit Exceeded):
R, G, B, N = map(int, input().split())
count = 0
rgb = sorted([R, G, B], reverse=True)
for i in range(N+1):
    for j in range(N+1):
        tmp = N - (rgb[0] * i + rgb[1] * j)
        if 0 > tmp:
            break
        if tmp % rgb[2] == 0:
            count += 1

print(count)


Fixed submission:
R, G, B, N = map(int, input().split())
count = 0
rgb = sorted([R, G, B], reverse=True)
if False:
    count = 0
else:
    for i in range(N+1):
        for j in range(N+1):
            tmp = N - (rgb[0] * i + rgb[1] * j)
            if 0 > tmp:
                break
            if tmp % rgb[2] == 0:
                count += 1
print(count)
Buggy python submission (verdict: Time Limit Exceeded):
import math
import fractions
from functools import reduce
N = int(input())
A = list(map(int, input().split()))
# ans = 1
ans = reduce(fractions.gcd, A[1:])
for i in range(1, N-1):
    left_gcd = reduce(fractions.gcd, A[:i])
    right_gcd = reduce(fractions.gcd, A[i+1:])
    ans = max(ans, fractions.gcd(left_gcd, right_gcd))
left_gcd = reduce(fractions.gcd, A[:-1])
ans = max(ans, left_gcd)
print(ans)


Fixed submission:
import math
import fractions
from functools import reduce
N = int(input())
A = list(map(int, input().split()))
from_left = [0 for i in range(N)]
from_right = [0 for i in range(N)]
from_left[0] = A[0]
from_right[-1] = A[-1]
for i in range(1, N):
    from_left[i] = fractions.gcd(A[i], from_left[i-1])
for i in range(N-2, -1, -1):
    from_right[i] = fractions.gcd(A[i], from_right[i+1])
# print(from_left)
# print(from_right)
ans = max(from_left[-2], from_right[1])
for i in range(1, N-1):
    ans = max(ans, fractions.gcd(from_left[i-1], from_right[i+1]))
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
# import math
import fractions
from functools import reduce

N = int(input())
A = list(map(int, input().split()))
ans = 1
for i in range(N):
    ans = max(ans, reduce(fractions.gcd, [A[j] for j in range(N) if i!=j]))
print(ans)


Fixed submission:
import math
import fractions
from functools import reduce
N = int(input())
A = list(map(int, input().split()))
from_left = [0 for i in range(N)]
from_right = [0 for i in range(N)]
from_left[0] = A[0]
from_right[-1] = A[-1]
for i in range(1, N):
    from_left[i] = fractions.gcd(A[i], from_left[i-1])
for i in range(N-2, -1, -1):
    from_right[i] = fractions.gcd(A[i], from_right[i+1])
# print(from_left)
# print(from_right)
ans = max(from_left[-2], from_right[1])
for i in range(1, N-1):
    ans = max(ans, fractions.gcd(from_left[i-1], from_right[i+1]))
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = list(map(int, input().split()))
for i in range(N-1):
    for j in range(i, N-1):
        if A[j] < 0:
            A[j], A[j+1] = A[j]*-1, A[j+1]*-1
print(sum(A))


Fixed submission:
N = int(input())
A = list(map(int, input().split()))
mn = len(list(filter(lambda x: x < 0, A)))
ans = [-A[i] if A[i] < 0 else A[i] for i in range(N)]
if mn % 2 == 0:
    print(sum(ans))
else:
    print(sum(ans)-min(ans)*2)
Buggy python submission (verdict: Time Limit Exceeded):
N, Q = map(int, input().split())
S = input()
AC = [S[i:i+2] == 'AC'for i in range(len(S)-1)]
AC = [sum(AC[:i+1]) for i in range(len(AC))]
AC.insert(0, 0)
for i in range(Q):
    l, r = map(int, input().split())
    # print(AC[r-1], AC[l-1])
    print(AC[r-1]-AC[l-1])


Fixed submission:
N, Q = map(int, input().split())
S = input()
AC = [int(S[i:i+2] == 'AC') for i in range(len(S)-1)]
for i in range(1, len(AC)):
    AC[i] = AC[i] + AC[i-1]
AC.insert(0, 0)
for i in range(Q):
    l, r = map(int, input().split())
    # print(AC[r-1], AC[l-1])
    print(AC[r-1]-AC[l-1])

Buggy python submission (verdict: Time Limit Exceeded):
N, Q = map(int, input().split())
S = input()
AC = [S[i:i+2] == 'AC'for i in range(len(S)-1)]
for i in range(Q):
    l, r = map(int, input().split())
    print(sum(AC[l-1:r-1]))


Fixed submission:
N, Q = map(int, input().split())
S = input()
AC = [int(S[i:i+2] == 'AC') for i in range(len(S)-1)]
for i in range(1, len(AC)):
    AC[i] = AC[i] + AC[i-1]
AC.insert(0, 0)
for i in range(Q):
    l, r = map(int, input().split())
    # print(AC[r-1], AC[l-1])
    print(AC[r-1]-AC[l-1])
Buggy python submission (verdict: Runtime Error):
N = int(input())
C = [int(input()) for i in range(N)]
dp = [0] * (N+1)
dp_c = [0] * (N+1)
pred_ci = 0
dp[0] = 1
for i, ci in enumerate(C, 1):
    if pred_ci == ci:
        dp[i] += dp[i-1]
        continue
    dp[i] += dp[i-1] + dp_c[ci]
    dp_c[ci] = dp[i]
    pred_ci = ci

print(dp[N])

Fixed submission:
MOD = 10**9 + 7
N = int(input())
C = [int(input()) for i in range(N)]
dp = [0] * (N+1)
dp_c = [0] * (2*10**5+1)
pred_ci = 0
dp[0] = 1
for i, ci in enumerate(C, 1):
    if pred_ci == ci:
        dp[i] += dp[i-1]
        continue
    dp[i] = (dp[i-1] + dp_c[ci]) % MOD
    dp_c[ci] = dp[i]
    pred_ci = ci

print(dp[N])
Buggy python submission (verdict: Runtime Error):
import functools
# import math
import fraction
N = int(input())
A = list(map(int, input().split()))
# ans = functools.reduce(math.gcd, A)
ans = functools.reduce(fraction.gcd, A)
print(ans)


Fixed submission:
import functools
# import math
import fractions
N = int(input())
A = list(map(int, input().split()))
# ans = functools.reduce(math.gcd, A)
ans = functools.reduce(fractions.gcd, A)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**6)
def rec(i):
    if i == 0:
        C[i] = 0
        return C[i]
    elif i == 1:
        C[i] = rec(i-1)+abs(H[i]-H[i-1])
        return C[i]
    # print(i, rec(i-1), rec(i-2))
    C[i] = min(rec(i-1)+abs(H[i]-H[i-1]), rec(i-2)+abs(H[i]-H[i-2]))
    return C[i]
INFTY = 10**13
N = int(input())
H = list(map(int, input().split()))
C = [INFTY for i in range(N)]
# C[0] = 0
# for i in range(N):
#     if i+1 < N:
#         C[i+1] = min(C[i] + abs(H[i+1]-H[i]), C[i+1])
#     if i+2 < N:
#         C[i+2] = min(C[i] + abs(H[i+2]-H[i]), C[i+2])
# print(C[-1])
print(rec(N-1))


Fixed submission:
N = int(input())
H = list(map(int, input().split()))
C = [10**13 for i in range(N)]
C[0] = 0
for i in range(N):
    if i+1 < N:
        C[i+1] = min(C[i] + abs(H[i+1]-H[i]), C[i+1])
    if i+2 < N:
        C[i+2] = min(C[i] + abs(H[i+2]-H[i]), C[i+2])
print(C[-1])

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**6)
def rec(i):
    if i == 0:
        C[i] = 0
        return C[i]
    elif i == 1:
        C[i] = rec(i-1)+abs(H[i]-H[i-1])
        return C[i]
    # print(i, rec(i-1), rec(i-2))
    C[i] = min(rec(i-1)+abs(H[i]-H[i-1]), rec(i-2)+abs(H[i]-H[i-2]))
    return C[i]
INFTY = 10**13
N = int(input())
H = list(map(int, input().split()))
C = [INFTY for i in range(N)]
# C[0] = 0
# for i in range(N):
#     if i+1 < N:
#         C[i+1] = min(C[i] + abs(H[i+1]-H[i]), C[i+1])
#     if i+2 < N:
#         C[i+2] = min(C[i] + abs(H[i+2]-H[i]), C[i+2])
# print(C[-1])
print(rec(N-1))


Fixed submission:
N = int(input())
H = list(map(int, input().split()))
C = [10**13 for i in range(N)]
C[0] = 0
for i in range(N):
    if i+1 < N:
        C[i+1] = min(C[i] + abs(H[i+1]-H[i]), C[i+1])
    if i+2 < N:
        C[i+2] = min(C[i] + abs(H[i+2]-H[i]), C[i+2])
print(C[-1])

Buggy python submission (verdict: Runtime Error):
def rec(i):
    if i == 0:
        C[i] = 0
        return C[i]
    elif i == 1:
        C[i] = rec(i-1)+abs(H[i]-H[i-1])
        return C[i]
    # print(i, rec(i-1), rec(i-2))
    C[i] = min(rec(i-1)+abs(H[i]-H[i-1]), rec(i-2)+abs(H[i]-H[i-2]))
    return C[i]
INFTY = 10**13
N = int(input())
H = list(map(int, input().split()))
C = [INFTY for i in range(N)]
# C[0] = 0
# for i in range(N):
#     if i+1 < N:
#         C[i+1] = min(C[i] + abs(H[i+1]-H[i]), C[i+1])
#     if i+2 < N:
#         C[i+2] = min(C[i] + abs(H[i+2]-H[i]), C[i+2])
# print(C[-1])
print(rec(N-1))


Fixed submission:
N = int(input())
H = list(map(int, input().split()))
C = [10**13 for i in range(N)]
C[0] = 0
for i in range(N):
    if i+1 < N:
        C[i+1] = min(C[i] + abs(H[i+1]-H[i]), C[i+1])
    if i+2 < N:
        C[i+2] = min(C[i] + abs(H[i+2]-H[i]), C[i+2])
print(C[-1])
Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**6)
def rec(i):
    if C[i] != INFTY:
        return C[i]
    if i == 0:
        C[i] = 0
        return C[i]
    elif i == 1:
        C[i] = rec(i-1)+abs(H[i]-H[i-1])
        return C[i]
    C[i] = min([rec(i-k)+abs(H[i]-H[i-k]) for k in range(1, min(i+1, K+1))])
    return C[i]

INFTY = 10**13
N, K = map(int, input().split())
H = list(map(int, input().split()))
C = [INFTY for i in range(N)]
print(rec(N-1))

Fixed submission:
N, K = map(int, input().split())
H = list(map(int, input().split()))
C = [10**13 for i in range(N)]
C[0] = 0
for i in range(N):
    for j in range(1, K+1):
        if i+j < N:
            C[i+j] = min(C[i] + abs(H[i+j]-H[i]), C[i+j])
print(C[-1])

Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int, input().split())
H = list(map(int, input().split()))
C = [10**13 for i in range(N)]
C[0] = 0
for i in range(N):
    for j in range(1, K+1):
        if i+j < N:
            C[i+j] = min(C[i] + abs(H[i+j]-H[i]), C[i+j])
print(C[-1])


Fixed submission:
N, K = map(int, input().split())
H = list(map(int, input().split()))
C = [10**13 for i in range(N)]
C[0] = 0
for i in range(N):
    for j in range(1, K+1):
        if i+j < N:
            C[i+j] = min(C[i] + abs(H[i+j]-H[i]), C[i+j])
print(C[-1])
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
P = list(map(float, input().split()))
memo = [[0 for j in range(N+1)] for i in range(N)]

memo[0][0] = 1 - P[0]
memo[0][1] = P[0]

for i in range(1, N):
    memo[i][0] = memo[i-1][0] * (1 - P[i])
    for j in range(1, i+2):
        memo[i][j] = memo[i-1][j-1] * P[i]
        memo[i][j] += memo[i-1][j] * (1 - P[i])
            
print(sum(memo[-1][N//2+1:]))


Fixed submission:
N = int(input())
P = list(map(float, input().split()))
memo = [[0 for j in range(N+1)] for i in range(N)]

memo[0][0] = 1 - P[0]
memo[0][1] = P[0]

for i in range(1, N):
    memo[i][0] = memo[i-1][0] * (1 - P[i])
    for j in range(1, i+2):
        memo[i][j] = memo[i-1][j-1] * P[i]
        memo[i][j] += memo[i-1][j] * (1 - P[i])
            
print(sum(memo[-1][N//2+1:]))

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
P = list(map(float, input().split()))
memo = [[0 for j in range(N+1)] for i in range(N)]

for i in range(N):
    if i == 0:
        memo[i][0] = 1 - P[i]
    else:
        memo[i][0] = memo[i-1][0] * (1 - P[i])
    for j in range(1, i+2):
        if i == 0:
            memo[i][j] = P[i]
        else:
            memo[i][j] = memo[i-1][j-1] * P[i]
            memo[i][j] += memo[i-1][j] * (1 - P[i])
            
print(sum(memo[-1][N//2+1:]))


Fixed submission:
N = int(input())
P = list(map(float, input().split()))
memo = [[0 for j in range(N+1)] for i in range(N)]

memo[0][0] = 1 - P[0]
memo[0][1] = P[0]

for i in range(1, N):
    memo[i][0] = memo[i-1][0] * (1 - P[i])
    for j in range(1, i+2):
        memo[i][j] = memo[i-1][j-1] * P[i]
        memo[i][j] += memo[i-1][j] * (1 - P[i])
            
print(sum(memo[-1][N//2+1:]))
Buggy python submission (verdict: Time Limit Exceeded):
S = list(input())
ans = 0
for i in range(len(S)-1):
    reversed_flag = False
    for j in range(len(S)-1):
        if reversed_flag:
            reversed_flag = False
            continue
        elif S[j] == 'B' and S[j+1] == 'W':
            S[j] = 'W'
            S[j+1] = 'B'
            ans += 1
            reversed_flag = True

print(ans)


Fixed submission:
S = list(input())
ans = 0
B_count = 0
for i in range(len(S)-1):
    if S[i] == 'B' and S[i+1] == 'W':
        B_count += 1
        S[i+1] = 'B'
        ans += B_count
        B_count -= 1
    elif S[i] == 'B':
        B_count += 1

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N, M = map(int, input().split())
p_dict = {}
p = [0 for i in range(M)]
y = [0 for i in range(M)]
for i in range(M):
    p[i], y[i] = map(int, input().split())
    if p[i] not in p_dict:
        p_dict[p[i]] = [y[i]]
        continue
    p_dict[p[i]].append(y[i])

for key in p_dict.keys():
    p_dict[key].sort()

for i in range(M):
    print('{:06d}{:06d}'.format(p[i], p_dict[p[i]].index(y[i])+1))


Fixed submission:
import numpy as np
N, M = map(int, input().split())
p_dict = {}
p = [0 for i in range(M)]
y = [0 for i in range(M)]
i_in_p = [0 for i in range(M)]

for i in range(M):
    p[i], y[i] = map(int, input().split())
    if p[i] not in p_dict:
        i_in_p[i] = 0
        p_dict[p[i]] = [y[i]]
        continue
    i_in_p[i] = len(p_dict[p[i]])
    p_dict[p[i]].append(y[i])
for key in p_dict.keys():
    p_dict[key] = np.array(p_dict[key]).argsort().argsort() + 1
for i in range(M):
    print('{:06d}{:06d}'.format(p[i], p_dict[p[i]][i_in_p[i]]))
Buggy python submission (verdict: Runtime Error):
N = int(input())
A = [int(input()) for i in range(N)]
A.sort()
leftA = A[:N//2+N%2]
rightA = A[N//2+N%2:]
rightA.sort(reverse=True)
tmp = leftA[0]
leftA[0] = leftA[1]
leftA[1] = tmp
ans = 0
if len(leftA) == len(rightA):
    for i in range(N//2):
        if i == 0:
            ans += abs(leftA[i] - rightA[i])
            lastA = rightA[i]
            continue
        ans += abs(lastA - leftA[i])
        if i == N//2-1:
            ans += max(abs(leftA[i] - rightA[i]), abs(leftA[0] - rightA[i]))
            continue
        ans += abs(leftA[i] - rightA[i])
        lastA = rightA[i]
else:
    for i in range(N//2+1):
        if i == 0:
            ans += abs(leftA[i] - rightA[i])
            lastA = rightA[i]
            continue
        ans += abs(lastA - leftA[i])
        if i == N//2:
            continue
        ans += abs(leftA[i] - rightA[i])
        lastA = rightA[i]
    ans2 = 0
    tmp = leftA.pop(-1)
    rightA.insert(0, tmp)
    for i in range(N//2):
        if i == 0:
            ans2 += abs(leftA[i] - rightA[i])
            lastA = rightA[i]
            continue
        ans2 += abs(lastA - leftA[i])
        lastA = rightA[i]
    ans2 += abs(rightA[-2] - rightA[-1])
    ans = max(ans, ans2)

print(ans)


Fixed submission:
N = int(input())
A = [int(input()) for i in range(N)]
A = sorted(A)
h = N // 2
if N % 2 == 0:
    ans = sum(A[h:])*2 - sum(A[:h])*2 - A[h] + A[h-1]
else:
    ans1 = sum(A[h-1:])*2 - sum(A[:h-1])*2 - (A[h-1] + A[h]) * 3
    ans2 = sum(A[h:])*2 - sum(A[:h])*2 - (A[h] + A[h+1])
    ans = max(ans1, ans2)
print(ans)
Buggy python submission (verdict: Runtime Error):
import math
N = int(input())
ai = list(map(int, input().split()))
m = 1
ans = 0
for a in ai:
    m = (m * a) // math.gcd(m, a)
m -= 1
for a in ai:
    ans += m % a
    
print(ans)


Fixed submission:
import fractions
N = int(input())
ai = list(map(int, input().split()))
m = 1
ans = 0
for a in ai:
    m = (m * a) // fractions.gcd(m, a)
m -= 1
for a in ai:
    ans += m % a

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import heapq
from collections import defaultdict
WHITE = 0
GRAY = 1
BLACK = 2
INFTY = 10**16
def dijkstra(s, VC):
    color = [WHITE for i in range(N)]
    d = [INFTY for i in range(N)]
    d[s] = 0
    pq = []
    heapq.heappush(pq, (0, s))

    while len(pq) != 0:
        u = heapq.heappop(pq)[1]
        color[u] = BLACK

        for v, c in VC[u]:
            if color[v] != BLACK:
                if d[u] + c < d[v]:
                    d[v] = d[u] + c
                    color[v] = GRAY
                    heapq.heappush(pq, (d[v], v))

    return d

N, M, S, T = map(int, input().split())
# VA = [[] for i in range(N)]
# VB = [[] for i in range(N)]
VA = defaultdict(list)
VB = defaultdict(list)
for i in range(M):
    u, v, a, b = list(map(int, input().split()))
    VA[u-1].append([v-1, a,])
    VA[v-1].append([u-1, a])
    VB[u-1].append([v-1, b])
    VB[v-1].append([u-1, b])

da = dijkstra(S-1, VA)
db = dijkstra(T-1, VB)
tmp = 10**16
base = 10 ** 15
ans = [0 for i in range(N)]
for i in range(N-1, -1, -1):
    tmp = min(da[i] + db[i], tmp)
    ans[i] = tmp

for i in range(N):
    print(base - ans[i])


Fixed submission:
import heapq
WHITE = 0
GRAY = 1
BLACK = 2
INFTY = 10**16
def dijkstra(s, VC):
    color = [WHITE for i in range(N)]
    d = [INFTY for i in range(N)]
    d[s] = 0
    pq = []
    heapq.heappush(pq, (0, s))

    while len(pq) != 0:
        u = heapq.heappop(pq)[1]
        color[u] = BLACK

        for v, c in VC[u]:
            if color[v] != BLACK:
                if d[u] + c < d[v]:
                    d[v] = d[u] + c
                    color[v] = GRAY
                    heapq.heappush(pq, (d[v], v))

    return d

N, M, S, T = map(int, input().split())
VA = [[] for i in range(N)]
VB = [[] for i in range(N)]
for i in range(M):
    u, v, a, b = list(map(int, input().split()))
    VA[u-1].append([v-1, a,])
    VA[v-1].append([u-1, a])
    VB[u-1].append([v-1, b])
    VB[v-1].append([u-1, b])

da = dijkstra(S-1, VA)
db = dijkstra(T-1, VB)
tmp = 10**16
base = 10 ** 15
ans = [0 for i in range(N)]
for i in range(N-1, -1, -1):
    tmp = min(da[i] + db[i], tmp)
    ans[i] = tmp

for i in range(N):
    print(base - ans[i])
Buggy python submission (verdict: Time Limit Exceeded):
from collections import Counter
n = int(input())
a = list(map(int, input().split()))
ans = -1
for i in range(n):
    a[i] = a[i] - i - 1
count = Counter(a)
for b in count.keys():
    tmp = 0
    for i in range(n):
        tmp += abs(a[i] - b)
    if ans == -1 or tmp < ans:
        ans = tmp
print(ans)


Fixed submission:
n = int(input())
a = list(map(int, input().split()))
ans = 0
for i in range(n):
    a[i] = a[i] - i - 1
a.sort()
b = a[n // 2]
for i in range(n):
    ans += abs(a[i] - b)
print(ans)
Buggy python submission (verdict: Runtime Error):
N = int(input())
A = list(map(int, input().split()))
A2 = []
Z = []
ans = 0
zerocnt = 0
for ai in A:
    if ai == 0:
        zerocnt += 1
    elif zerocnt >= 1:
        A2 += [0]
        Z += [zerocnt]
        ans += (zerocnt * (zerocnt+1)) // 2
        zerocnt = 0
    if ai != 0:
        A2 += [ai]
        Z += [1]
        ans += 1

if zerocnt >= 1:
    A2 += [0]
    Z += [zerocnt]
    ans += (zerocnt * (zerocnt+1)) // 2
    zerocnt = 0

for i, ai in enumerate(A2):
    aixor = ai
    sumA = ai
    for j in range(i+1, min(i+41, len(A2))):
        aj = A2[j]
        aixor = aixor ^ aj
        sumA += aj
        if aixor != sumA:
            break
        else:
            ans += (Z[i] * Z[j])
        
print(ans)

Fixed submission:
a, b = map(int, input().split())
ans = max(a+b, a-b)
ans = max(ans, a*b)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
s = input()
s = list(map(lambda x: 0 if x == 'W' else 1, s))
ans = 300000
for i in range(n):
    left = s[:i]
    right = s[i+1:]
    ans = min(ans, len(left)-sum(left)+sum(right))

print(ans)


Fixed submission:
n = int(input())
s = input()
s = list(map(lambda x: 0 if x == 'W' else 1, s))
ans = 300000
beright = [0 for i in range(n)]
beleft = [0 for i in range(n)]
for i in range(1, n):
    beright[i] = beright[i-1] + abs(s[i-1] - 1)
    beleft[-i-1] = beleft[-i] + s[-i]

for br, bl in zip(beright, beleft):
    ans = min(ans, br + bl)

print(ans)