Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
n,m = map(int,input().split())
a = [int(input()) for _ in range(m)]
mod = 10**9+7
memo = [-1]*(n+1)
def rec(x):
    if memo[x] != -1: pass
    elif x == 0: memo[x] = 1
    elif a and x == a[-1]:
        memo[x] = 0
        a.pop()
    elif x == 1: memo[x] = 1
    else: memo[x] = rec(x-1)+rec(x-2)
    return memo[x]%mod
print(rec(n))

Fixed submission:
n,m = map(int,input().split())
aa = [int(input()) for i in range(m)]

cnt2 = 0
cnt1 = 1
aa.append(-1)
a = aa.pop(0)


for i in range(1,n):
    if i == a:
        cnt2, cnt1 = cnt1, 0
        a = aa.pop(0)
    else:
        cnt2, cnt1 = cnt1, cnt2+cnt1
else:
    ans = (cnt2+cnt1)%1000000007

print(ans)

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

cnt2 = 0
cnt1 = 1

for i in range(1,n):
    if i in a:
        cnt2, cnt1 = cnt1, 0
    else:
        cnt2, cnt1 = cnt1, cnt2+cnt1
else:
    ans = (cnt2+cnt1)%1000000007

print(ans)


Fixed submission:
n,m = map(int,input().split())
aa = [int(input()) for i in range(m)]

cnt2 = 0
cnt1 = 1
aa.append(-1)
a = aa.pop(0)


for i in range(1,n):
    if i == a:
        cnt2, cnt1 = cnt1, 0
        a = aa.pop(0)
    else:
        cnt2, cnt1 = cnt1, cnt2+cnt1
else:
    ans = (cnt2+cnt1)%1000000007

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n,m = map(int,input().split())
lr = [list(map(int,input().split())) for i in range(m)]

wildcard = set(range(lr[0][0],lr[0][1]+1))
for i in range(1,len(lr)):
    wildcard &= set(range(lr[i][0],lr[i][1]+1))

ans = len(wildcard)
print(ans)


Fixed submission:
n,m = map(int,input().split())
lr = [list(map(int,input().split())) for i in range(m)]

lp = 1
rp = n

for i in range(m):
    if lp < lr[i][0]:
        lp = lr[i][0]
    if rp > lr[i][1]:
        rp = lr[i][1]
else:
    if rp - lp < 0:
        ans = 0
    else:
        ans = rp-lp+1

print(ans)
Buggy python submission (verdict: Runtime Error):
n,m = map(int,input().split())
a = [int(i) for i in input().split()]
bc = [[int(i) for i in input().split()] for i in range(m)]
a.sort()
bc.sort(key=lambda x:x[1],reverse=True)
d = []
cnt1 = 0
cnt2 = 0
x = 0

for lst in bc:
    cnt2 = 0
    while cnt1 < n and cnt2 < lst[0]:
        d.append(lst[1])
        cnt1 += 1
        cnt2 += 1

for i in range(n):
    if d[i] - a[i] < 0:
        x = i
        break

print(sum(d[:x]+a[x:]))

Fixed submission:
n,m = map(int,input().split())
a = [int(i) for i in input().split()]
bc = [[int(i) for i in input().split()] for i in range(m)]
ans = 0
cnt = 0
d = {}

for i in range(n): 
    d[a[i]] = d.get(a[i],0)+1
for k in d: 
    bc.append([d[k],k])
bc.sort(key= lambda x:x[1],reverse=True)

for i in range(len(bc)):
    if cnt < n:
        ans += bc[i][1]*bc[i][0]
        cnt += bc[i][0]
    else:
        ans -= (cnt-n)*bc[i-1][1]
        break
else:
    ans -= (cnt-n)*bc[i][1]

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
n,m = map(int,input().split())
a = [int(i) for i in input().split()]

for i in range(m):
    b,c = map(int,input().split())
    for j in range(b):
        a.append(c)

a.sort(reverse=True)
print(sum(a[:n]))


Fixed submission:
n,m = map(int,input().split())
a = [int(i) for i in input().split()]
bc = [[int(i) for i in input().split()] for i in range(m)]
ans = 0
cnt = 0
d = {}

for i in range(n): 
    d[a[i]] = d.get(a[i],0)+1
for k in d: 
    bc.append([d[k],k])
bc.sort(key= lambda x:x[1],reverse=True)

for i in range(len(bc)):
    if cnt < n:
        ans += bc[i][1]*bc[i][0]
        cnt += bc[i][0]
    else:
        ans -= (cnt-n)*bc[i-1][1]
        break
else:
    ans -= (cnt-n)*bc[i][1]

print(ans)
Buggy python submission (verdict: Runtime Error):
n = int(input())
T = [[] for _ in range(n)]
for _ in range(n-1):
    u,v,w = map(int,input().split())
    u -= 1
    v -= 1
    w %= 2
    T[u].append((v,w))
    T[v].append((u,w))

ans = [0]*n
def dfs(u,p=-1,c=0):
    for v,w in T[u]:
        if v == p: continue
        if w: c = (c+1)%2
        ans[v] = c
        dfs(v,u,c)
dfs(0)

print("\n".join(map(str,ans)))

Fixed submission:
import sys
sys.setrecursionlimit(10**9)
n = int(input())
T = [[] for _ in range(n)]
for _ in range(n-1):
    u,v,w = map(int,input().split())
    u -= 1
    v -= 1
    w %= 2
    T[u].append((v,w))
    T[v].append((u,w))

ans = [0]*n
def dfs(u,p=-1,c=0):
    for v,w in T[u]:
        if v == p: continue
        nc = (c+1)%2 if w else c 
        ans[v] = nc
        dfs(v,u,nc)
dfs(0)

print("\n".join(map(str,ans)))
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
mv = [int(input()) for i in range(5)]
st = [n,0,0,0,0,0]
time = 0

while st[5] != n:
    stcpy = st[:]
    for i in range(5):
        if stcpy[i]-mv[i] >= 0:
            st[i] -= mv[i]
            st[i+1] += mv[i]
        else:
            st[i] -= stcpy[i]
            st[i+1] += stcpy[i]
    time += 1
else:
    ans = time

print(ans)


Fixed submission:
n = int(input())
t = [int(input()) for _ in range(5)]
m = min(t)
print((n+m-1)//m+4)
Buggy python submission (verdict: Time Limit Exceeded):
x,y,z,k = map(int,input().split())
A = [int(i) for i in input().split()]
B = [int(i) for i in input().split()]
C = [int(i) for i in input().split()]
lst = [a+b for a in A for b in B]
lst.sort(reverse=True)
lst = [e+c for e in lst[:k] for c in C]
lst.sort(reverse=True)
for i in range(k): print(lst[i])

Fixed submission:
x,y,z,k = map(int,input().split())
A = [int(i) for i in input().split()]
B = [int(i) for i in input().split()]
C = [int(i) for i in input().split()]
lst = [a+b for a in A for b in B]
lst.sort(reverse=True)
lst = [e+c for e in lst[:k] for c in C]
lst.sort(reverse=True)
for i in range(k): print(lst[i])
Buggy python submission (verdict: Runtime Error):
n,q = map(int,input().split())
s = input()
lr = [list(map(int,input().split())) for i in range(q)]

aclist = [0]
acsum = 0

for i in range(1,n):
    if s[i-1] == "A" and s[i] == "C":
        acsum += 1
    aclist.append(acsum)

for i in range(q):
    ans = aclist [lr[i][1]-1] - aclist [lr[i][0]-2]
    if aclist [lr[i][0]-1] - aclist [lr[i][0]-2] != 0:
        ans -= 1
    print(ans)

Fixed submission:
b = input()

if b == "A":
    ans = "T"
elif b == "T":
    ans = "A"
elif b == "C":
    ans = "G"
else:
    ans = "C"

print(ans)

Buggy python submission (verdict: Runtime Error):
n,q = map(int,input().split())
s = input()
lr = [list(map(int,input().split())) for i in range(q)]

aclist = [0]
acsum = 0

for i in range(1,n):
    if s[i-1] == "A" and s[i] == "C":
        acsum += 1
    aclist.append(acsum)

for i in range(q):
    ans = aclist [lr[i][0]-1] - aclist [lr[i][0]-2]
    if aclist [lr[i][0]-1] - aclist [lr[i][0]-2] != 0:
        ans -= 1
    print(ans)


Fixed submission:
b = input()

if b == "A":
    ans = "T"
elif b == "T":
    ans = "A"
elif b == "C":
    ans = "G"
else:
    ans = "C"

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n,q = map(int,input().split())
s = input()
lr = [list(map(int,input().split())) for i in range(q)]
accnt = 0

for i in range(q):
    for j in range(lr[i][0],lr[i][1]):
        if s[j-1] == "A" and s[j] == "C":
            accnt += 1
    else:
        print(accnt)
        accnt = 0

Fixed submission:
n,q = map(int,input().split())
s = input()
lr = [list(map(int,input().split())) for i in range(q)]

aclist = [0,0]
acsum = 0

for i in range(1,n):
    if s[i-1] == "A" and s[i] == "C":
        acsum += 1
    aclist.append(acsum)

for i in range(q):
    if aclist [lr[i][0]] - aclist [lr[i][0]-1] != 0:
        ans = aclist[lr[i][1]] - aclist[lr[i][0]-1] - 1 
    else:
        ans = aclist[lr[i][1]] - aclist[lr[i][0]-1]
    print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
a,b = map(int,input().split())
xor = 0

for i in range(a,b+1):
    xor ^= i
else:
    ans = xor
    print(ans)

Fixed submission:
a,b = map(int,input().split())

if a%2 == 0 and b%2 == 0:
    ans = b^((b-a)//2)%2
elif a%2 == 0 and b%2 != 0:
    ans = ((b-a+1)//2)%2
elif a%2 != 0 and b%2 == 0:
    ans = a^b^((b-1-a)//2)%2
else:
    ans = a^((b-a)//2)%2

print(ans)
Buggy python submission (verdict: Runtime Error):
s = input()
zero = 0
one = 0

for i in len(s):
    if s[i]=="0":
        zero += 1
    else:
        one += 1
else:
    ans = min(zero,one)*2

print(ans)

Fixed submission:
s = input()
zero = 0
one = 0

for i in range(len(s)):
    if s[i]=="0":
        zero += 1
    else:
        one += 1
else:
    ans = min(zero,one)*2

print(ans)
Buggy python submission (verdict: Runtime Error):
from itertools import product 
n,a,b,c = map(int,input().split())
l = [int(input()) for _ in range(n)]
tar = [a,b,c]
ans = float("inf")
for p in product(range(4),repeat=8):
    mp = 0
    length = [0]*3
    for i,j in enumerate(p):
        if j == 3: continue
        if length[j] > 0: mp += 10
        length[j] += l[i]
    for i in range(3):
        if length[i] == 0: break
        mp += abs(length[i]-tar[i])
    else:
        ans = min(ans, mp)
print(ans)

Fixed submission:
from itertools import product 
n,a,b,c = map(int,input().split())
l = [int(input()) for _ in range(n)]
tar = [a,b,c]
ans = float("inf")
for p in product(range(4),repeat=n):
    mp = 0
    length = [0]*3
    for i,j in enumerate(p):
        if j == 3: continue
        if length[j] > 0: mp += 10
        length[j] += l[i]
    for j in range(3):
        if length[j] == 0: break
        mp += abs(length[j]-tar[j])
    else:
        ans = min(ans, mp)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n,k = map(int,input().split())
h = [int(i) for i in input().split()]
def cost(i,j): return abs(h[i]-h[j])
INF = float("INF")
dp = [INF]*n
dp[0] = 0
for i in range(n):
    for j in range(i+1,min(i+k+1,n)):
        dp[j] = min(dp[j],dp[i]+cost(i,j))
print(dp[n-1])

Fixed submission:
n,K = map(int,input().split())
h = [0]
for i in input().split(): h.append(int(i))
def cost(i,j): return abs(h[i]-h[j])

dp = [float("inf") for _ in range(n+1)]
dp[0] = dp[1] = 0
for i in range(2,n+1):
    for k in range(1,K+1):
        if i-k > 0:
            dp[i] = min(dp[i-k]+cost(i,i-k),dp[i])

print(dp[n])

Buggy python submission (verdict: Time Limit Exceeded):
n,K = map(int,input().split())
h = [0]
for i in input().split(): h.append(int(i))
def cost(i,j): return abs(h[i]-h[j])

dp = [float("inf") for _ in range(n+1)]
dp[0] = dp[1] = 0
for i in range(2,n+1):
    for k in range(1,K+1):
        if i-k > 0:
            dp[i] = min(dp[i-k]+cost(i,i-k),dp[i])

print(dp[n])


Fixed submission:
n,K = map(int,input().split())
h = [0]
for i in input().split(): h.append(int(i))
def cost(i,j): return abs(h[i]-h[j])

dp = [float("inf") for _ in range(n+1)]
dp[0] = dp[1] = 0
for i in range(2,n+1):
    for k in range(1,K+1):
        if i-k > 0:
            dp[i] = min(dp[i-k]+cost(i,i-k),dp[i])

print(dp[n])
Buggy python submission (verdict: Runtime Error):
N,W = map(int,input().split())
w = [0]*(N+1)
v = [0]*(N+1)
for i in range(1,N+1): w[i],v[i] = map(int,input().split())

dp = [[0]*(W+1) for _ in range(N+1)]
for i in range(1,N+1):
    for j in range(1,W+1):
        if j < w[j]: dp[i][j] = dp[i-1][j]
        else: dp[i][j] = max(dp[i-1][j],dp[i-1][j-w[j]]+v[j])
print(dp[N][W])

Fixed submission:
n,W = map(int,input().split())
w = [0]*n
v = [0]*n
for i in range(n):
    w[i],v[i] = map(int,input().split())

dp = [[0 for _ in range(n+1)] for _ in range(W+1)]
for i in range(1,W+1):
    for j in range(1,n+1):
        if i-w[j-1] >= 0:
            dp[i][j] = max(dp[i-w[j-1]][j-1]+v[j-1],dp[i][j-1])
        else:
            dp[i][j] = dp[i][j-1]

print(dp[W][n])

Buggy python submission (verdict: Time Limit Exceeded):
n,W = map(int,input().split())
w = [0]*n
v = [0]*n
for i in range(n):
    w[i],v[i] = map(int,input().split())

dp = [[0 for _ in range(n+1)] for _ in range(W+1)]
for i in range(1,W+1):
    for j in range(1,n+1):
        if i-w[j-1] >= 0:
            dp[i][j] = max(dp[i-w[j-1]][j-1]+v[j-1],dp[i][j-1])
        else:
            dp[i][j] = dp[i][j-1]

print(dp[W][n])

Fixed submission:
n,W = map(int,input().split())
w = [0]*n
v = [0]*n
for i in range(n):
    w[i],v[i] = map(int,input().split())

dp = [[0 for _ in range(n+1)] for _ in range(W+1)]
for i in range(1,W+1):
    for j in range(1,n+1):
        if i-w[j-1] >= 0:
            dp[i][j] = max(dp[i-w[j-1]][j-1]+v[j-1],dp[i][j-1])
        else:
            dp[i][j] = dp[i][j-1]

print(dp[W][n])
Buggy python submission (verdict: Time Limit Exceeded):
s = input()
t = input()
x = len(s)
y = len(t)
dp = [[""]*(y+1) for _ in range(x+1)]
for i in range(x):
    for j in range(y):
        if s[i] == t[j]:
            lcs = dp[i][j] + s[i]
        elif len(dp[i+1][j]) >= len(dp[i][j+1]):
            lcs = dp[i+1][j]
        else:
            lcs = dp[i][j+1]
        dp[i+1][j+1] = lcs
# for i in range(x+1): print(dp[i])
print(dp[x][y])

Fixed submission:
s = input()
t = input()
x = len(s)
y = len(t)
dp = [[0]*(y+1) for _ in range(x+1)]
for i in range(x):
    for j in range(y):
        if s[i] == t[j]: dp[i+1][j+1] = dp[i][j] + 1
        else: dp[i+1][j+1] = max(dp[i+1][j],dp[i][j+1])
        
# for i in range(x+1): print(dp[i])
ans = ""
i = x
j = y
while i > 0 and j > 0:
    if dp[i][j] == dp[i-1][j]: i -= 1
    elif dp[i][j] == dp[i][j-1]: j -= 1
    else:
        ans = s[i-1]+ans
        i -= 1
        j -= 1
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
s = input()
t = input()
x = len(s)
y = len(t)
dp = [[""]*(y+1) for _ in range(x+1)]
for i in range(x):
    for j in range(y):
        if s[i] == t[j]:
            lcs = dp[i][j] + s[i]
        elif len(dp[i+1][j]) >= len(dp[i][j+1]):
            lcs = dp[i+1][j]
        else:
            lcs = dp[i][j+1]
        dp[i+1][j+1] = lcs
# for i in range(x+1): print(dp[i])
print(dp[x][y])

Fixed submission:
s = input()
t = input()
x = len(s)
y = len(t)
dp = [[0]*(y+1) for _ in range(x+1)]
for i in range(x):
    for j in range(y):
        if s[i] == t[j]: dp[i+1][j+1] = dp[i][j] + 1
        else: dp[i+1][j+1] = max(dp[i+1][j],dp[i][j+1])
        
# for i in range(x+1): print(dp[i])
ans = ""
i = x
j = y
while i > 0 and j > 0:
    if dp[i][j] == dp[i-1][j]: i -= 1
    elif dp[i][j] == dp[i][j-1]: j -= 1
    else:
        ans = s[i-1]+ans
        i -= 1
        j -= 1
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n,x = map(int,input().split())
b = "P"
for _ in range(n):
    b = "B"+b+"P"+b+"B"

print(b[:x].count("P"))

Fixed submission:
n,x = map(int,input().split())
burger = [1]
patty = [1]

for i in range(n):
    burger.append(burger[i]*2+3)
    patty.append(patty[i]*2+1)

def f(n,x):
    if n == 0:
        return 1
    elif x == 1:
        return 0
    elif x <= 1+burger[n-1]:
        return f(n-1,x-1)
    elif x == 2+burger[n-1]:
        return 1+patty[n-1]
    elif x <= 2+2*burger[n-1]:
        return 1+patty[n-1]+f(n-1,x-2-burger[n-1])
    else:
        return patty[n]

print(f(n,x))

Buggy python submission (verdict: Time Limit Exceeded):
def burger(n):
    if n == 0:
        return "P"
    else:
        return "B"+burger(n-1)+"P"+burger(n-1)+"B"

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

ans = 0
nburger = list(burger(N))
for i in range(X):
    if nburger[i] == "P":
        ans += 1

print(ans)

Fixed submission:
n,x = map(int,input().split())
burger = [1]
patty = [1]

for i in range(n):
    burger.append(burger[i]*2+3)
    patty.append(patty[i]*2+1)

def f(n,x):
    if n == 0:
        return 1
    elif x == 1:
        return 0
    elif x <= 1+burger[n-1]:
        return f(n-1,x-1)
    elif x == 2+burger[n-1]:
        return 1+patty[n-1]
    elif x <= 2+2*burger[n-1]:
        return 1+patty[n-1]+f(n-1,x-2-burger[n-1])
    else:
        return patty[n]

print(f(n,x))
Buggy python submission (verdict: Runtime Error):
def gcd(a,b):
    if b == 0:
        return a
    else:
        return gcd(b,a%b)

n,x = map(int,input().split())
lstx = [int(i) for i in input().split()]

g = abs(lstx[0]-x)
for i in range(1,n): g = gcd(g,abs(lstx[i]-x))

print(g)

Fixed submission:
a,b = map(int,input().split())
if a%2 == 0 or b%2 == 0:
    ans = "No"
else:
    ans = "Yes"

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n,C = map(int,input().split())
d = [[int(i) for i in input().split()] for _ in range(C)]
c = [[int(i)-1 for i in input().split()] for _ in range(n)]

cnt0 = [0]*C
cnt1 = [0]*C
cnt2 = [0]*C
for i in range(n):
    for j in range(n):
        for k in range(C):
            if (i+j)%3 == 0: cnt0[k] += d[c[i][j]][k]
            elif (i+j)%3 == 1: cnt1[k] += d[c[i][j]][k]
            else: cnt2[k] += d[c[i][j]][k]

ans = float("inf")
for i in range(C):
    for j in range(C):
        if i == j: continue
        for k in range(C):
            if i == k or j == k: continue
            ans = min(ans, cnt0[i] + cnt1[j] + cnt2[k])
print(ans)

Fixed submission:
n,C = map(int,input().split())
d = [[int(i) for i in input().split()] for _ in range(C)]
c = [[int(i)-1 for i in input().split()] for _ in range(n)]

cnt0 = [0]*C
cnt1 = [0]*C
cnt2 = [0]*C
for i in range(n):
    for j in range(n):
        for k in range(C):
            if (i+j)%3 == 0: cnt0[k] += d[c[i][j]][k]
            elif (i+j)%3 == 1: cnt1[k] += d[c[i][j]][k]
            else: cnt2[k] += d[c[i][j]][k]

ans = float("inf")
for i in range(C):
    for j in range(C):
        if i == j: continue
        for k in range(C):
            if i == k or j == k: continue
            ans = min(ans, cnt0[i] + cnt1[j] + cnt2[k])
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
s = input()
k = int(input())
l = len(s)
substr = set()

for i in range(0,l):
    for j in range(i+1,l+1):
        substr.add(s[i:j])

substr = sorted(list(substr))
print(substr[k-1])

Fixed submission:
s = input()
K = int(input())
idx = [[] for _ in range(26)]

for i in range(len(s)):
    idx[ord(s[i])-ord("a")].append(i)

substr = set()
for i in range(26):
    for j in idx[i]:
        for k in range(j+1,j+6):
            substr.add(s[j:k])
    if len(substr) >= K:
        substr = sorted(list(substr))
        break

print(substr[K-1])

Buggy python submission (verdict: Time Limit Exceeded):
s = input()
k = int(input())
l = len(s)
substr = set()

for i in range(0,l):
    for j in range(i+1,l+1):
        substr.add(s[i:j])

substr = sorted(list(substr))
print(substr[k-1])


Fixed submission:
s = input()
K = int(input())
idx = [[] for _ in range(26)]

for i in range(len(s)):
    idx[ord(s[i])-ord("a")].append(i)

substr = set()
for i in range(26):
    for j in idx[i]:
        for k in range(j+1,j+6):
            substr.add(s[j:k])
    if len(substr) >= K:
        substr = sorted(list(substr))
        break

print(substr[K-1])
Buggy python submission (verdict: Time Limit Exceeded):
a,b,k = map(int,input().split())

for i in range(a,b+1):
    if i <= a+k-1 or i >= b-k+1: print(i) 

Fixed submission:
a,b,k = map(int,input().split())

for i in range(a,min(a+k,b+1)):
    print(i)

for i in range(max(a+k,b+1-k),b+1):
    print(i)
Buggy python submission (verdict: Time Limit Exceeded):
h,w,d = map(int,input().split())
a = [[int(i) for i in input().split()] for _ in range(h)]
q = int(input())
l = [0]*q ;r = [0]*q
for i in range(q): l[i],r[i] = map(int,input().split())
dct = {}

for i in range(h):
    for j in range(w):
        dct[a[i][j]] = (i,j)
    
for i in range(q):
    ans = 0
    n = l[i]
    cx,cy = dct[n]
    while dct[n] != dct[r[i]]:
        n += d
        nx,ny = dct[n]
        ans += abs(nx-cx)+abs(ny-cy)
        cx,cy = nx,ny
    print(ans)

Fixed submission:
h,w,D = map(int,input().split())
a = [[int(i) for i in input().split()] for _ in range(h)]
px = [0]*(h*w+1)
py = [0]*(h*w+1)
d = [0]*(h*w+1)

for i in range(h):
    for j in range(w):
        px[a[i][j]] = i
        py[a[i][j]] = j

for i in range(D+1,h*w+1):
    d[i] = d[i-D] + abs(px[i]-px[i-D]) + abs(py[i]-py[i-D])

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

Buggy python submission (verdict: Time Limit Exceeded):
h,w,d = map(int,input().split())
a = [[int(i) for i in input().split()] for _ in range(h)]
q = int(input())
l = [0]*q ;r = [0]*q
for i in range(q): l[i],r[i] = map(int,input().split())
dct = {}

for i in range(h):
    for j in range(w):
        dct[a[i][j]] = (i,j)
    
for i in range(q):
    ans = 0
    n = l[i]
    cx,cy = dct[n]
    while dct[n] != dct[r[i]]:
        n += d
        nx,ny = dct[n]
        ans += abs(nx-cx)+abs(ny-cy)
        cx,cy = nx,ny
    print(ans)

Fixed submission:
h,w,D = map(int,input().split())
a = [[int(i) for i in input().split()] for _ in range(h)]
px = [0]*(h*w+1)
py = [0]*(h*w+1)
d = [0]*(h*w+1)

for i in range(h):
    for j in range(w):
        px[a[i][j]] = i
        py[a[i][j]] = j

for i in range(D+1,h*w+1):
    d[i] = d[i-D] + abs(px[i]-px[i-D]) + abs(py[i]-py[i-D])

q = int(input())
for _ in range(q):
    l,r = map(int,input().split())
    print(d[r]-d[l])
Buggy python submission (verdict: Runtime Error):
n,m = map(int,input().split())
G = [[] for _ in range(n)]
INF = float("INF")
pos = [INF]*n
for _ in range(m):
    l,r,d = map(int,input().split())
    l -= 1
    r -= 1
    G[l].append((r,d))
    G[r].append((l,-d))

def dfs(now):
    for nxt,d in G[now]:
        if pos[nxt] == INF:
            pos[nxt] = pos[now]+d
            dfs(nxt)
        elif pos[nxt] != pos[now]+d:
            print("No")
            exit()

for i in range(n):
    if pos[i] == INF:
        pos[i] = 0
        dfs(i)
print("Yes")

Fixed submission:
import sys
sys.setrecursionlimit(1000000000)

n,m = map(int,input().split())
G = [[] for _ in range(n)]
INF = float("INF")
pos = [INF]*n
for _ in range(m):
    l,r,d = map(int,input().split())
    l -= 1
    r -= 1
    G[l].append((r,d))
    G[r].append((l,-d))

def dfs(now):
    for nxt,d in G[now]:
        if pos[nxt] == INF:
            pos[nxt] = pos[now]+d
            dfs(nxt)
        elif pos[nxt] != pos[now]+d:
            print("No")
            exit()

for i in range(n):
    if pos[i] == INF:
        pos[i] = 0
        dfs(i)
print("Yes")
Buggy python submission (verdict: Time Limit Exceeded):
n,y = map(int,input().split())

sen = y//1000
for gosen in range(sen//5+1):
    for man in range((sen-gosen*5)//10+1):
        if y == man*10000+gosen*5000+(sen-gosen*5-man*10)*1000 and n == man+gosen+sen-gosen*5-man*10:
            print(man,gosen,sen-gosen*5-man*10)
            exit()

print(-1,-1,-1)

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

for sen in range(n+1):
    for gosen in range(n+1-sen):
        man = n-sen-gosen
        if 1000*sen + 5000*gosen + 10000*man == y:
            print(man,gosen,sen)
            exit()

print(-1,-1,-1)
Buggy python submission (verdict: Runtime Error):
n = int(input())

ans = "Yes" if x%sum(map(int,list(str(n)))) == 0 else "No"
print(ans)

Fixed submission:
n = int(input())

ans = "Yes" if n%sum(map(int,list(str(n)))) == 0 else "No"
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n,C = map(int,input().split())
INF = float("INF")
ch = [[0]*(200001) for _ in range(C)]
m = 0
for _ in range(n):
    s,t,c = map(int,input().split())
    s = s*2-1
    t *= 2
    c -= 1
    ch[c][s] += 1
    ch[c][t] -= 1
    m = max(m,t)

cnt = [0]*(m+1)
for c in range(C):
    for i in range(1,m+1):
        ch[c][i] += ch[c][i-1]
        if ch[c][i-1] == 0 and ch[c][i] > 0: cnt[i] += 1
        if ch[c][i-1] > 0 and ch[c][i] == 0: cnt[i] -= 1

for i in range(1,m+1): cnt[i] += cnt[i-1]
print(max(cnt))

Fixed submission:
n,C = map(int,input().split())
INF = float("INF")
ch = [[0]*(200001) for _ in range(C)]
m = 0
for _ in range(n):
    s,t,c = map(int,input().split())
    s = s*2-1
    t *= 2
    c -= 1
    ch[c][s] += 1
    ch[c][t] -= 1
    m = max(m,t)

cnt = [0]*(m+1)
for c in range(C):
    for i in range(1,m+1):
        ch[c][i] += ch[c][i-1]
        if ch[c][i-1] == 0 and ch[c][i] > 0: cnt[i] += 1
        if ch[c][i-1] > 0 and ch[c][i] == 0: cnt[i] -= 1

for i in range(1,m+1): cnt[i] += cnt[i-1]
print(max(cnt))