Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
A, B, K = map(int,input().split())
if K >=A+B:
    print("0 0")
elif A+B>K>=A:
    p = A+B-K
    print(f"0 {p}")
else:
    q = A-K
    print(f"{q} {B}")

Fixed submission:
A, B, K = map(int,input().split())
if A+B<K:
    print(*[0,0])
elif A<K<=A+B:
    print(*[0,A+B-K])
else:
    print(*[A-K,B])
Buggy python submission (verdict: Runtime Error):
A,B = map(int,input().split())
GCD(p,q):
    if p<q:
        p,q = q,p
    p = q
    q = p%q
    if q!=0:
        GCD(p,q)
    else:
        return p
gcd = GCD(A,B)
ans = (A*B)//gcd
print(ans)

Fixed submission:
A,B = map(int,input().split())
def GCD(p,q):
    if p<q:
        p,q = q,p
    r = p
    p = q
    q = r%q
    if q!=0:
        return GCD(p,q)
    else:
        return p
gcd = GCD(A,B)
ans = (A*B)//gcd
print(ans)
Buggy python submission (verdict: Runtime Error):
S = list(input())
A = reversed(S)
LEN=len(S)
ans=0
if LEN%2==0:
    for i in range(LEN//2):
        if S[i]!=A[i]:
            ans+=1
else:
    for i in range((LEN-1)//2):
        if S[i]!=A[i]:
            ans+=1
print(ans)

Fixed submission:
S = list(input())
A = list(reversed(S))
LEN=len(S)
ans=0
if LEN%2==0:
    for i in range(LEN//2):
        if S[i]!=A[i]:
            ans+=1
else:
    for i in range((LEN-1)//2):
        if S[i]!=A[i]:
            ans+=1
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
S = input()
a = [str(i)+str(j)+str(k) for i in range(10) for j in range(10) for k in range(10)]
cnt = 0
tmp_i = -1
tmp_j = -1
for num in a:
    for i in range(N):
        if S[i]==num[0]:
            tmp_i = i
            break
    if tmp_i == -1:
        continue
    for j in range(N-1,-1,-1):
        if S[j]==num[2]:
            tmp_j = j
            break
    if tmp_j == -1:
        tmp_i = -1
        continue
    if tmp_i+1<tmp_j:
        if num[1] in S[tmp_i+1:tmp_j]:
            cnt+=1
    tmp_i = -1
    tmp_j = -1
print(cnt)

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

s = set()
L = [[set() for i in range(2)] for j in range(N+1)]

ans = set()

for i in range(N):
    L[i+1][0].add(S[i])
    for k in L[i][0]:
        L[i+1][0].add(k)
        L[i+1][1].add(k + S[i])
    for k in L[i][1]:
        L[i+1][1].add(k)
        ans.add(k + S[i])

print(len(ans))

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
S = input()
cnt = 0
all_set = set()
for i in range(1,N-1):
    before_set = set(S[:i])
    after_set = set(S[i+1:])
    for j in before_set:
        for k in after_set:
            all_set.add(j+S[i]+k)
print(len(all_set))

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

s = set()
L = [[set() for i in range(2)] for j in range(N+1)]

ans = set()

for i in range(N):
    L[i+1][0].add(S[i])
    for k in L[i][0]:
        L[i+1][0].add(k)
        L[i+1][1].add(k + S[i])
    for k in L[i][1]:
        L[i+1][1].add(k)
        ans.add(k + S[i])

print(len(ans))

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
S = input()
lst = []
for i in range(N-2):
    for j in range(i+1,N-1):
        for k in range(j+1,N):
            if not S[i]+S[j]+S[k] in lst:
                lst.append(S[i]+S[j]+S[k])
print(len(lst))

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

s = set()
L = [[set() for i in range(2)] for j in range(N+1)]

ans = set()

for i in range(N):
    L[i+1][0].add(S[i])
    for k in L[i][0]:
        L[i+1][0].add(k)
        L[i+1][1].add(k + S[i])
    for k in L[i][1]:
        L[i+1][1].add(k)
        ans.add(k + S[i])

print(len(ans))
Buggy python submission (verdict: Runtime Error):
mod = 10 ** 9 + 7
cnt = [0] * 3
N = int(input())
A = list(map(int,input().split()))

ans = 1
for i in range(N):
    ans *= cnt.count(A[i])
    ans %= mod
    cnt[cnt.index(A[i])] += 1

print(ans)

Fixed submission:
mod = 10 ** 9 + 7
cnt = [0] * 3
N = int(input())
A = list(map(int,input().split()))

ans = 1
for i in range(N):
    ans *= cnt.count(A[i])
    ans %= mod
    if ans == 0:
        break
    cnt[cnt.index(A[i])] += 1

print(ans)
Buggy python submission (verdict: Runtime Error):
INF = 10 ** 10

N = int(input())

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

L.sort(key=lambda x:(-x[0], x[1]))

MAX_L = 0
MIN_R = INF
MAX = 0
a = 0
b = 0

for i in range(N):
    if MAX_L < L[i][0]:
        MAX_L = L[i][0]
        a = i
    if MIN_R > L[i][1]:
        MIN_R = L[i][1]
        b = i
    MAX = max(MAX, L[i][1] - L[i][0] + 1)

ans = MAX + max(0, MIN_R - MAX_L + 1)

p = 0

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


    print(ans)INF = 10 ** 10

N = int(input())

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

L.sort(key=lambda x:(-x[0], x[1]))

MAX_L = 0
MIN_R = INF
MAX = 0
a = 0
b = 0

for i in range(N):
    if MAX_L < L[i][0]:
        MAX_L = L[i][0]
        a = i
    if MIN_R > L[i][1]:
        MIN_R = L[i][1]
        b = i
    MAX = max(MAX, L[i][1] - L[i][0] + 1)

ans = MAX + max(0, MIN_R - MAX_L + 1)

p = 0

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


    print(ans)

Fixed submission:
INF = 10 ** 10

N = int(input())
 
L = [tuple(map(int,input().split())) for _ in range(N)]
 
L.sort(key=lambda x:(-x[0], x[1]))
 
MAX_L = 0
MIN_R = INF
MAX = 0
a = 0
b = 0
 
for i in range(N):
    if MAX_L < L[i][0]:
        MAX_L = L[i][0]
        a = i
    if MIN_R > L[i][1]:
        MIN_R = L[i][1]
        b = i
    MAX = max(MAX, L[i][1] - L[i][0] + 1)
 
ans = MAX + max(0, MIN_R - MAX_L + 1)
 
p = INF
 
for i in range(N-1):
    p = min(p, L[i][1])
    ans = max(ans, max(0, p - L[a][0] + 1) + max(0, L[b][1] - L[i+1][0] + 1))
 
print(ans)
Buggy python submission (verdict: Runtime Error):
import math

a, b, x = map(int,input().split())
if (a**2)*b<2*x:
    print(90-math.degrees(math.atan((a**3)/(2*((a**2)*b-x)))))
else:
    print(90-math.degrees(math.atan((2*x)/(a*(b**2)))))

Fixed submission:
import math

a, b, x = map(int,input().split())
if (a**2)*b == x:
    print(0)
elif (a**2)*b<2*x:
    print(90-math.degrees(math.atan((a**3)/(2*((a**2)*b-x)))))
else:
    print(90-math.degrees(math.atan((2*x)/(a*(b**2)))))
Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int,input().split())
A = list(map(int,input().split()))
F = list(map(int,input().split()))

A.sort()
F.sort(reverse = True)

def solve(n):
    cnt = 0
    for i in range(N):
        cnt += max(0, A[i] - n // F[i])
    return cnt <= K

left = -1
right = 10 ** 12 + 1

while left + 1 < right:
    mid = (left + right) // 2
    if solve(mid):
        right = mid
    else:
        left = mid

print(right)

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

A.sort()
F.sort(reverse = True)

def solve(n):
    cnt = 0
    for i in range(N):
        cnt += max(0, A[i] - n // F[i])
    return cnt <= K

left = -1
right = 10 ** 12 + 1

while left + 1 < right:
    mid = (left + right) // 2
    if solve(mid):
        right = mid
    else:
        left = mid

print(right)

Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int,input().split())
A = list(map(int,input().split()))
F = list(map(int,input().split()))
all_0 = [0 for i in range(N)]
A.sort()
F.sort()
F.reverse()
MUL = [A[i]*F[i] for i in range(N)]

def max_MUL():
    max_MUL = -1
    index = -1
    for i in range(N):
        if max_MUL<MUL[i]:
            max_MUL = MUL[i]
            index = i
        elif max_MUL==MUL[i]:
            if F[index]<F[i]:
                index = i
    return index
def Gluttony(K):
    if A == all_0:
        return 0
    while K>0:
        index = max_MUL()
        A[index]-=1
        MUL[index]=A[index]*F[index]
        K-=1
        if A == all_0:
            return 0
    return MUL[max_MUL()]

print(Gluttony(K))

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

A.sort()
F.sort(reverse = True)

def solve(n):
    cnt = 0
    for i in range(N):
        cnt += max(0, A[i] - n // F[i])
    return cnt <= K

left = -1
right = 10 ** 12 + 1

while left + 1 < right:
    mid = (left + right) // 2
    if solve(mid):
        right = mid
    else:
        left = mid

print(right)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
L = list(map(int,input().split()))
ans = 0
L.sort()
lst = [0 for i in range(10**3+1)]
for i in range(N):
    lst[L[i]]+=1
for i in range(N-1):
    for j in range(i+1,N):
        p = L[i]+L[j]
        ans += sum(lst[:p])-(j+1)
print(ans)

Fixed submission:
N = int(input())
L = list(map(int,input().split()))
ans = 0
L.sort()
lst = [0 for i in range(10**3+1)]
for i in range(N):
    lst[L[i]]+=1
for i in range(10**3+1):
    if i != 0:
        lst[i]=lst[i-1]+lst[i]
for i in range(N-1):
    for j in range(i+1,N):
        p = L[i]+L[j]
        if p-1>=10**3+1:
            ans += lst[10**3]-(j+1)
        else:
            ans += lst[p-1]-(j+1)
print(ans)
Buggy python submission (verdict: Runtime Error):
import fraction

A, B = map(int,input().split())
GCD = fraction.gcd(A, B)

def prime_factorize(n):
    a = [1]
    flag = 1
    while n % 2 == 0:
        if flag:
            a.append(2)
            flag = 0
        n //= 2
    f = 3
    flag = 1
    while f * f <= n:
        if n % f == 0:
            if flag:
                a.append(f)
                flag = 0
            n //= f
        else:
            f += 2
            flag = 1
    if n != 1 and n != a[-1]:
        a.append(n)
    return a

a = prime_factorize(GCD)

print(len(a))

Fixed submission:
import fractions

A, B = map(int,input().split())
GCD = fractions.gcd(A, B)

def prime_factorize(n):
    a = [1]
    flag = 1
    while n % 2 == 0:
        if flag:
            a.append(2)
            flag = 0
        n //= 2
    f = 3
    flag = 1
    while f * f <= n:
        if n % f == 0:
            if flag:
                a.append(f)
                flag = 0
            n //= f
        else:
            f += 2
            flag = 1
    if n != 1 and n != a[-1]:
        a.append(n)
    return a

a = prime_factorize(GCD)

print(len(a))
Buggy python submission (verdict: Runtime Error):
Weather = [Sunny, Cloudy, Rainy, Sunny]
S = input()
print(Weather[Weather.index(S)+1])

Fixed submission:
Weather = ["Sunny", "Cloudy", "Rainy", "Sunny"]
S = input()
print(Weather[Weather.index(S)+1])
Buggy python submission (verdict: Runtime Error):
import heapq

N, M = map(int,input().split())
A = list(map(lambda x: int(x) * (-1),input().split()))
heapq.heapify(A)
for i in range(M):
    tmp = heapq.heappop(A)
    tmp *= -1
    tmp //= 2
    tmp *= -1
    print(A)
print(sum(A) * -1)

Fixed submission:
import heapq

N, M = map(int,input().split())
A = list(map(lambda x: int(x) * (-1),input().split()))
heapq.heapify(A)
for i in range(M):
    tmp = heapq.heappop(A)
    tmp *= -1
    tmp //= 2
    tmp *= -1
    heapq.heappush(A,tmp)
print(sum(A) * -1)
Buggy python submission (verdict: Time Limit Exceeded):
def z_algo(S):
    N = len(S)
    A = [0]*N
    i = 1; j = 0
    A[0] = l = len(S)
    while i < l:
        while i+j < l and S[j] == S[i+j]:
            j += 1
        if not j:
            i += 1
            continue
        A[i] = j
        k = 1
        while l-i > k < j - A[k]:
            A[i+k] = A[k]
            k += 1
        i += k; j -= k
    return A

N = int(input())
S = input()
MAX = 0

for i in range(N-1):
    A = z_algo(S[i:])
    for j in range(len(A)):
        if MAX < A[j] and A[j] <= j:
            MAX = A[j]

print(MAX)

Fixed submission:
def z_algo(S):
    N = len(S)
    A = [0]*N
    i = 1; j = 0
    A[0] = l = len(S)
    while i < l:
        while i+j < l and S[j] == S[i+j]:
            j += 1
        if not j:
            i += 1
            continue
        A[i] = j
        k = 1
        while l-i > k < j - A[k]:
            A[i+k] = A[k]
            k += 1
        i += k; j -= k
    return A

N = int(input())
S = input()
MAX = 0

for i in range(N-1):
    A = z_algo(S[i:])
    for j in range(len(A)):
        if MAX < A[j] and A[j] <= j:
            MAX = A[j]

print(MAX)
Buggy python submission (verdict: Runtime Error):
import heapq
N, M = map(int,input().split())
L = [[] for _ in range(M)]
for _ in range(N):
    A, B = map(int,input().split())
    L[A-1].append(-B)
Q = []
ans = 0
for i in range(M):
    for j in L[i]:
        heapq.heappush(Q, j)
    try:
        ans -= heapq.heappop(Q)
    except:
        pass
print(ans)

Fixed submission:
import heapq
N, M = map(int,input().split())
L = [[] for _ in range(M)]
for _ in range(N):
    A, B = map(int,input().split())
    try:
        L[A-1].append(-B)
    except:
        pass
Q = []
ans = 0
for i in range(M):
    for j in L[i]:
        heapq.heappush(Q, j)
    try:
        ans -= heapq.heappop(Q)
    except:
        pass
print(ans)

Buggy python submission (verdict: Runtime Error):
import heapq
N, M = map(int,input().split())
L = [[] for _ in range(M)]
for _ in range(N):
    A, B = map(int,input().split())
    L[A-1].append(-B)
Q = []
ans = 0
for i in range(M):
    for j in L[i]:
        heapq.heappush(Q, j)
    ans -= heapq.heappop(Q)
    
print(ans)

Fixed submission:
import heapq
N, M = map(int,input().split())
L = [[] for _ in range(M)]
for _ in range(N):
    A, B = map(int,input().split())
    try:
        L[A-1].append(-B)
    except:
        pass
Q = []
ans = 0
for i in range(M):
    for j in L[i]:
        heapq.heappush(Q, j)
    try:
        ans -= heapq.heappop(Q)
    except:
        pass
print(ans)

Buggy python submission (verdict: Runtime Error):
import heapq
N, M = map(int,input().split())
L = [[] for _ in range(M)]
for _ in range(N):
    A, B = map(int,input().split())
    L[A-1].append(B)
Q = []
ans = 0
for i in range(M):
    Q += L[i]
    try:
        ans += heapq.heappop(Q)
    except:
        pass
print(ans)

Fixed submission:
import heapq
N, M = map(int,input().split())
L = [[] for _ in range(M)]
for _ in range(N):
    A, B = map(int,input().split())
    try:
        L[A-1].append(-B)
    except:
        pass
Q = []
ans = 0
for i in range(M):
    for j in L[i]:
        heapq.heappush(Q, j)
    try:
        ans -= heapq.heappop(Q)
    except:
        pass
print(ans)

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

N, M = map(int,input().split())
jobs = [[] for i in range(10 ** 5 + 1)]
lst = []

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

ans = 0

for i in range(1,M+1):
    lst += jobs[i]
    if lst:
        heapq.heapify(lst)
        k = heapq.heappop(lst)
        ans += (-1) * k

print(ans)

Fixed submission:
import heapq
N, M = map(int,input().split())
L = [[] for _ in range(M)]
for _ in range(N):
    A, B = map(int,input().split())
    try:
        L[A-1].append(-B)
    except:
        pass
Q = []
ans = 0
for i in range(M):
    for j in L[i]:
        heapq.heappush(Q, j)
    try:
        ans -= heapq.heappop(Q)
    except:
        pass
print(ans)
Buggy python submission (verdict: Runtime Error):
N = int(input())
P = list(map(int(),input().split()))
cnt = 0
for i in range(N):
    if P[i]!=i+1:
        cnt+=1
if cnt<=2:
    print("YES")
else:
    print("NO")

Fixed submission:
N = int(input())
P = list(map(int,input().split()))
cnt = 0
for i in range(N):
    if P[i]!=i+1:
        cnt+=1
if cnt<=2:
    print("YES")
else:
    print("NO")
Buggy python submission (verdict: Time Limit Exceeded):
S = list(input())

MOD = 10 ** 9 + 7

dp = [[0 for i in range(13)] for i in range(10**5+1)]
dp[0][0] = 1

for i in range(len(S)):
    if S[i] != "?":
        for j in range(13):
            dp[i+1][(j * 10 + int(S[i])) % 13] += dp[i][j]
    else:
        for j in range(13):
            for k in range(10):
                dp[i+1][(j * 10 + k) % 13] += dp[i][j]
    for j in range(13):
        dp[i+1][j] %= MOD

print(dp[len(S)][5])

Fixed submission:
S = list(input())

MOD = 10 ** 9 + 7

dp = [[0 for i in range(13)] for i in range(10**5+1)]
dp[0][0] = 1

for i in range(len(S)):
    if S[i] != "?":
        for j in range(13):
            dp[i+1][(j * 10 + int(S[i])) % 13] += dp[i][j]
    else:
        for j in range(13):
            for k in range(10):
                dp[i+1][(j * 10 + k) % 13] += dp[i][j]
    for j in range(13):
        dp[i+1][j] %= MOD

print(dp[len(S)][5])
Buggy python submission (verdict: Time Limit Exceeded):
L, R = map(int,input().split())
lst = [i%2019 for i in range(L,R+1)]
lst = set(lst)
lst = list(lst)
N = len(lst)
ans = 10**8
for i in range(N-1):
    for j in range(i+1,N):
        if ans>(lst[i]*lst[j])%2019:
            ans = (lst[i]*lst[j])%2019
print(ans)

Fixed submission:
L, R = map(int,input().split())
if R-L>=2018:
    print(0)
else:
    lst = [i%2019 for i in range(L,R+1)]
    lst = set(lst)
    lst = list(lst)
    N = len(lst)
    ans = 10**8
    for i in range(N-1):
        for j in range(i+1,N):
            if ans>(lst[i]*lst[j])%2019:
                ans = (lst[i]*lst[j])%2019
    print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = list(map(int,input().split()))
ans = [0 for i in range(N)]
SUM = []
for i in range(N):
    tmp = 0
    for j in range(i+1,i+N-1,2):
        tmp+=2*A[j%N]
    SUM.append(tmp)
for i in range(N):
    ans[i] = sum(A)-SUM[i]
print(*ans)

Fixed submission:
N = int(input())
A = list(map(int,input().split()))
B = [0 for i in range(N)]

for i in range(N):
    if i%2 == 0:
        B[0] += A[i]
    else:
        B[0] -= A[i]

for i in range(N-1):
    B[i+1] = 2 * A[i] - B[i]

print(*B)
Buggy python submission (verdict: Runtime Error):
mod = 10 ** 9 + 7

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

ans = K

def factorial(n, k, mod):
    fact = 1
    for integer in range(n, n-k, -1):
        fact *= integer
        fact %= mod
    return fact

def dfs(parent, current):
    ret = 1
    for child in graph[current]:
        if child != parent:
            ret *= dfs(current, child)
    L = len(graph[current])
    R = K - 1
    if parent != -1:
        L -= 1
        R -= 1
    ret *= factorial(R, L, mod)
    return ret % mod

ans *= dfs(-1, 0)
ans %= mod

print(ans)

Fixed submission:
import sys
sys.setrecursionlimit(4100000)

mod = 10 ** 9 + 7

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

ans = K

def factorial(n, k, mod):
    fact = 1
    for integer in range(n, n-k, -1):
        fact *= integer
        fact %= mod
    return fact

def dfs(parent, current):
    ret = 1
    for child in graph[current]:
        if child != parent:
            ret *= dfs(current, child)
    L = len(graph[current])
    R = K - 1
    if parent != -1:
        L -= 1
        R -= 1
    ret *= factorial(R, L, mod)
    return ret % mod

ans *= dfs(-1, 0)
ans %= mod

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
from queue import Queue
import sys
N, M = map(int,input().split())
edges = [[] for _ in range(3 * N)]
flag = [0] * (3 * N)
for _ in range(M):
    u, v = map(int,input().split())
    u -= 1
    v -= 1
    edges[u % (3 * N)].append((v + N) % (3 * N))
    edges[(u + N) % (3 * N)].append((v + 2 * N) % (3 * N))
    edges[(u + 2 * N) % (3 * N)].append(v % (3 * N))

S, T = map(int,input().split())
q = Queue()
q.put([0,S-1])
while not q.empty():
    p = q.get()
    if p[1] == T-1:
        print(p[0] // 3)
        sys.exit()
    for i in edges[p[1]]:
        if flag[i] == 0:
            flag[i] = 1
            q.put([p[0]+1,i])
print(-1)

Fixed submission:
from queue import Queue
import sys
N, M = map(int,input().split())
edges = [[] for _ in range(3 * N)]
flag = [0] * (3 * N)
for _ in range(M):
    u, v = map(int,input().split())
    u -= 1
    v -= 1
    edges[u % (3 * N)].append((v + N) % (3 * N))
    edges[(u + N) % (3 * N)].append((v + 2 * N) % (3 * N))
    edges[(u + 2 * N) % (3 * N)].append(v % (3 * N))

S, T = map(int,input().split())
q = Queue()
q.put([0,S-1])
while not q.empty():
    p = q.get()
    if p[1] == T-1:
        print(p[0] // 3)
        sys.exit()
    for i in edges[p[1]]:
        if flag[i] == 0:
            flag[i] = 1
            q.put([p[0]+1,i])
print(-1)
Buggy python submission (verdict: Runtime Error):
import math

A,B,C,D = map(int,input().split())
LCM = (C*D)//math.gcd(C,D)
ans = B-A-(B//C-(A-1)//C)-(B//D-(A-1)//D)+(B//LCM-(A-1)//LCM)+1
print(ans)

Fixed submission:
import fractions

A,B,C,D = map(int,input().split())
LCM = (C*D)//fractions.gcd(C,D)
ans = B-A-(B//C-(A-1)//C)-(B//D-(A-1)//D)+(B//LCM-(A-1)//LCM)+1
print(ans)
Buggy python submission (verdict: Runtime Error):
N, M = map(int,input().split())
L = []
R = []
for i in range(M):
    tmp_L, tmp_R = input().split()
    L.append(tmp_L)
    R.append(tmp_R)

left = max(L)
right = min(R)

if right - left < 0:
    print(0)
else:
    print(right - left + 1)

Fixed submission:
N, M = map(int,input().split())
L = []
R = []
for i in range(M):
    tmp_L, tmp_R = map(int,input().split())
    L.append(tmp_L)
    R.append(tmp_R)

left = max(L)
right = min(R)

if right - left < 0:
    print(0)
else:
    print(right - left + 1)
Buggy python submission (verdict: Time Limit Exceeded):
import heapq

N, M = map(int,input().split())
A = list(map(int,input().split()))
heapq.heapify(A)


def change(A, B, C):
    for i in range(B):
        tmp = heapq.heappop(A)
        if tmp < C:
            heapq.heappush(A, C)
        else:
            heapq.heappush(A, tmp)
            break


for i in range(M):
    B, C = map(int,input().split())
    change(A, B, C)

print(sum(A))

Fixed submission:
import heapq

N, M = map(int,input().split())
A = list(map(int,input().split()))
heapq.heapify(A)
B = []
C = []
for i in range(M):
    tmp_B, tmp_C = map(int,input().split())
    B.append(tmp_B)
    C.append(tmp_C)

def change(A, B, C):
    for i in range(B):
        tmp = heapq.heappop(A)
        if tmp < C:
            heapq.heappush(A, C)
        else:
            heapq.heappush(A, tmp)
            break

ZIP = zip(C, B)

ZIP = reversed(sorted(ZIP))

C, B = zip(*ZIP)

for i in range(M):
    change(A, B[i], C[i])

print(sum(A))

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

N, M = map(int,input().split())
A = list(map(int,input().split()))
heapq.heapify(A)


def change(A, B, C):
    for i in range(B):
        tmp = heapq.heappop(A)
        if tmp < C:
            heapq.heappush(A, C)
        else:
            heapq.heappush(A, tmp)
            break


for i in range(M):
    B, C = map(int,input().split())
    change(A, B, C)

print(sum(A))

Fixed submission:
import heapq

N, M = map(int,input().split())
A = list(map(int,input().split()))
heapq.heapify(A)
B = []
C = []
for i in range(M):
    tmp_B, tmp_C = map(int,input().split())
    B.append(tmp_B)
    C.append(tmp_C)

def change(A, B, C):
    for i in range(B):
        tmp = heapq.heappop(A)
        if tmp < C:
            heapq.heappush(A, C)
        else:
            heapq.heappush(A, tmp)
            break

ZIP = zip(C, B)

ZIP = reversed(sorted(ZIP))

C, B = zip(*ZIP)

for i in range(M):
    change(A, B[i], C[i])

print(sum(A))