Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
(N,M) = map(int,input().split())
A = [0]*M
B = [0]*M
for i in range(M):
    (A[i], B[i]) = map(int,input().split())
    A[i] -= 1
    B[i] -= 1

parent = [-1]*N
depth = [0] * N

def boss(n):
    d = 0
    while parent[n] >= 0:
        n = parent[n]
        d += 1
    return n,d

P = [1]*N
S = (N*(N-1))//2

ans = [0] * M
ans[M-1] = S

#print(A)
#print(B)

for i in range(M-1):
#    print(parent)
    j = M-1-i
    bA, dA = boss(A[j])
    bB, dB = boss(B[j])
#    print(A[j],B[j],bA,bB)
    if bA != bB:
        if depth[bA] < depth[bB]:
            (bA, bB) = (bB, bA)
        parent[bB] = bA
        S -= P[bA]*P[bB]
        P[bA] = P[bA] + P[bB]
        P[bB] = 0
    ans[j-1] = S

for i in range(M):
    print(ans[i])

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

parent = [-1]*N
depth = [0] * N

def boss(n):
    d = 0
    while parent[n] >= 0:
        n = parent[n]
        d += 1
    return n,d

P = [1]*N
S = (N*(N-1))//2

ans = [0] * M
ans[M-1] = S

#print(A)
#print(B)

for i in range(M-1):
#    print(parent)
    j = M-1-i
    bA, dA = boss(A[j])
    bB, dB = boss(B[j])
#    print(A[j],B[j],bA,bB)
    if bA != bB:
        if depth[bA] < depth[bB]:
            (bA, bB) = (bB, bA)
        parent[bB] = bA
        S -= P[bA]*P[bB]
        P[bA] = P[bA] + P[bB]
        P[bB] = 0
        depth[bA] = max(depth[bA],depth[bB]+1)
    ans[j-1] = S

for i in range(M):
    print(ans[i])

Buggy python submission (verdict: Time Limit Exceeded):
(N,M) = map(int,input().split())
A = [0]*M
B = [0]*M
for i in range(M):
    (A[i], B[i]) = map(int,input().split())
    A[i] -= 1
    B[i] -= 1

parent = [-1]*N

def boss(n):
    while parent[n] >= 0:
        n = parent[n]
    return n

P = [1]*N
S = (N*(N-1))//2

ans = [0] * M
ans[M-1] = S

for i in range(M-1):
    j = M-1-i
    bA = boss(A[j])
    bB = boss(B[j])
    if bA != bB:
        parent[bB] = bA
        S -= P[bA]*P[bB]
        P[bA] = P[bA] + P[bB]
        P[bB] = 0
    ans[j-1] = S

for i in range(M):
    print(ans[i])

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

parent = [-1]*N
depth = [0] * N

def boss(n):
    d = 0
    while parent[n] >= 0:
        n = parent[n]
        d += 1
    return n,d

P = [1]*N
S = (N*(N-1))//2

ans = [0] * M
ans[M-1] = S

#print(A)
#print(B)

for i in range(M-1):
#    print(parent)
    j = M-1-i
    bA, dA = boss(A[j])
    bB, dB = boss(B[j])
#    print(A[j],B[j],bA,bB)
    if bA != bB:
        if depth[bA] < depth[bB]:
            (bA, bB) = (bB, bA)
        parent[bB] = bA
        S -= P[bA]*P[bB]
        P[bA] = P[bA] + P[bB]
        P[bB] = 0
        depth[bA] = max(depth[bA],depth[bB]+1)
    ans[j-1] = S

for i in range(M):
    print(ans[i])
Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np
import bisect

(A,B,Q) = map(int,input().split())
inf = 10**12
s = np.empty(A+2,dtype=np.int64)
t = np.empty(B+2,dtype=np.int64)
s[0] = -inf
t[0] = -inf
s[A+1] = inf
t[B+1] = inf

for i in range(A):
    s[i+1] = np.int64(input())
for i in range(B):
    t[i+1] = np.int64(input())

for i in range(Q):
    x = np.int64(input())
    p = bisect.bisect_left(s,x)
    q = bisect.bisect_left(t,x)
    ans = min(max(s[p]-x,t[q]-x),
              max(x-s[p-1],x-t[q-1]),
                  (s[p]-x)*2 + (x-t[q-1]),
                  (s[p]-x) + (x-t[q-1])*2,
                  (t[q]-x)*2 + (x-s[p-1]),
                  (t[q]-x) + (x-s[p-1])*2)
    print(ans)

Fixed submission:
import numpy as np
import bisect
 
(A,B,Q) = map(int,input().split())
inf = 10**12
s = np.empty(A+2,dtype=np.object)
t = np.empty(B+2,dtype=np.object)
s[0] = -inf
t[0] = -inf
s[A+1] = inf
t[B+1] = inf
 
for i in range(A):
    s[i+1] = int(input())
for i in range(B):
    t[i+1] = int(input())
 
for i in range(Q):
    x = int(input())
    p = bisect.bisect_left(s,x)
    q = bisect.bisect_left(t,x)
    ans = min(max(s[p]-x,t[q]-x),
              max(x-s[p-1],x-t[q-1]),
                  (s[p]-x)*2 + (x-t[q-1]),
                  (s[p]-x) + (x-t[q-1])*2,
                  (t[q]-x)*2 + (x-s[p-1]),
                  (t[q]-x) + (x-s[p-1])*2)
    print(ans)
Buggy python submission (verdict: Runtime Error):
(N,M) = map(int,input().split())
r = int32(-1)
for i in range(M):
  A = list(map(int,input().split()))
  A.pop(0)
  c = 0
  for a in A:
    c |= (1 << (a-1))
  d &= c

ans = sum([(d>>n)&1 for n in range(n)])
print(ans)

Fixed submission:
import numpy as np

(N,M) = map(int,input().split())
B = np.ones(M,dtype=np.int)

for _ in range(N):
    A = np.array(list(map(int,input().split())))[1:]
    for i in range(M):
        if not i+1 in A:
            B[i] = 0
print(B.sum())
Buggy python submission (verdict: Runtime Error):
import math
from functools import reduce

def gcd_list(numbers):
    return reduce(math.gcd, numbers)

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

print(gcd_list(A))

Fixed submission:
from functools import reduce

def gcd(a,b):
    if a < b:
        (a,b) = (b,a)
    while 1:
        (a, b) = (b, a % b)
        if b == 0:
            return a

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

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

print(gcd_list(A))
Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
import sys
sys.setrecursionlimit(10**9)
input = lambda: sys.stdin.readline().rstrip()
inpl = lambda: list(map(int,input().split()))
N, M = inpl()
AB = []
children = [set() for _ in range(N)]
for _ in range(N+M-1):
    A, B = inpl()
    A -= 1
    B -= 1
    children[A].add(B)
    AB.append((A,B))
roots = [True]*N
for A, B in AB:
    roots[B] = False
for i in range(N):
    if roots[i]:
        root = i
        break

distance = [0]*N
parent = [-1]*N
pool = deque([(root,0)])
while pool:
    i, d = pool.popleft()
    for c in children[i]:
        if d+1 > distance[c]:
            distance[c] = d+1
            parent[c] = i
            pool.append((c,d+1))
for i in range(N):
    if parent[i] < 0:
        print(0)
    else:
        print(parent[i]+1)

Fixed submission:
import sys
input = lambda: sys.stdin.readline().rstrip()
inpl = lambda: list(map(int,input().split()))
N, M = inpl()
AB = []
children = [set() for _ in range(N)]
parents = [set() for _ in range(N)]
for _ in range(N+M-1):
    A, B = inpl()
    A -= 1
    B -= 1
    children[A].add(B)
    parents[B].add(A)

parent = [-1]*N
pool = list(range(N))
L = []
visited = [False]*N
while pool:
    i = pool.pop()
    if i >= N:
        L.append(i-N)
    elif visited[i]:
        continue
    else:
        visited[i] = True
        pool.append(i+N)
        for c in children[i]:
            pool.append(c)
L = L[::-1]
position = [None]*N
for i in range(N):
    position[L[i]] = i
for i in range(N):
    if not parents[i]:
        print(0)
    else:
        print(L[max(position[c] for c in parents[i])]+1)
Buggy python submission (verdict: Runtime Error):
def inpl(): return list(map(int,input().split()))
 
N, W = inpl()
dp = [[0]*W for _ in range(N+1)]
for n in range(1,N+1):
  w, v = inpl()
  for x in range(W+1):
    if x < w:
      dp[n][x] = dp[n-1][x]
    else:
      dp[n][x] = max(dp[n-1][x], dp[n-1][x-w] + v)
print(dp[-1][-1])


Fixed submission:
def inpl(): return list(map(int,input().split()))
 
N, W = inpl()
dp = [[0]*(W+1) for _ in range(N+1)]
for n in range(1,N+1):
  w, v = inpl()
  for x in range(W+1):
    if x < w:
      dp[n][x] = dp[n-1][x]
    else:
      dp[n][x] = max(dp[n-1][x], dp[n-1][x-w] + v)
print(dp[-1][-1])

Buggy python submission (verdict: Runtime Error):
def inpl(): return list(map(int,input().split()))
 
N, W = inpl()
dp = [[0]*W for _ in range(N)]
for n in range(1,N+1):
  w, v = inpl()
  for x in range(W):
    if x < w:
      dp[n][x] = dp[n-1][x]
    else:
      dp[n][x] = max(dp[n-1][x], dp[n-1][x-w] + v)
print(dp[-1][-1])

Fixed submission:
def inpl(): return list(map(int,input().split()))
 
N, W = inpl()
dp = [[0]*(W+1) for _ in range(N+1)]
for n in range(1,N+1):
  w, v = inpl()
  for x in range(W+1):
    if x < w:
      dp[n][x] = dp[n-1][x]
    else:
      dp[n][x] = max(dp[n-1][x], dp[n-1][x-w] + v)
print(dp[-1][-1])

Buggy python submission (verdict: Runtime Error):
def inpl(): return map(int,input().split())

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


Fixed submission:
def inpl(): return list(map(int,input().split()))
 
N, W = inpl()
dp = [[0]*(W+1) for _ in range(N+1)]
for n in range(1,N+1):
  w, v = inpl()
  for x in range(W+1):
    if x < w:
      dp[n][x] = dp[n-1][x]
    else:
      dp[n][x] = max(dp[n-1][x], dp[n-1][x-w] + v)
print(dp[-1][-1])
Buggy python submission (verdict: Runtime Error):
import numpy as np

def list753(n):
    if n == 1:
        return np.array([3,5,7],dtype=np.int)
    else:
        prev = list753(n-1)
        return np.concatenate((10*prev+3,10*prev+5,10*prev+7))

def all_list753(n):
    return np.concatenate(tuple([list753(i) for i in range(3,n+1)]))

Nstr = input()
N = int(Nstr)
Nlen = len(Nstr)

candidates = all_list753(Nlen)
ans = 0

for c in candidates:
    if c > N:
        continue
    cstr = str(c)
    if '3' in cstr and '5' in cstr and '7' in cstr:
        ans += 1

print(ans)

Fixed submission:
import numpy as np

def count(n,s):
    if s == 0:
        return 3**n - 3*(2**n) + 3
    elif s == 1:
        return 3**n - 2**(n+1) + 1
    elif s == 2:
        return 3**n - 2**n
    else:
        return 3**n

def num753(Nlist, appeared):
    n = len(Nlist)
    if n == 0:
        if appeared == 7:
            return 1
        else:
            return 0
    
    top = Nlist[-1]
    
    ap3 = appeared|1
    s3 = ap3 % 2 + (ap3 % 4)//2 + ap3 // 4
    ap5 = appeared|2
    s5 = ap5 % 2 + (ap5 % 4)//2 + ap5 // 4
    ap7 = appeared|4
    s7 = ap7 % 2 + (ap7 % 4)//2 + ap7 // 4

    if appeared == 0:
        ans = sum([count(i,0) for i in range(3,n)])
    else:
        ans = 0

    if top < 3:
        pass
    elif top == 3:
        ans = ans + num753(Nlist[:-1],ap3)
    elif top == 4:
        ans = ans + count(n-1,s3)
    elif top == 5:
        ans = ans + count(n-1,s3) + num753(Nlist[:-1],ap5)
    elif top == 6:
        ans = ans + count(n-1,s3) + count(n-1,s5)
    elif top == 7:
        ans = ans + count(n-1,s3) + count(n-1,s5) + num753(Nlist[:-1],ap7)
    else: # top == 8,9
        ans = ans + count(n-1,s3) + count(n-1,s5) + count(n-1,s7)
    
    return ans

N = int(input())
Nlist=[]
while N > 0:
    Nlist.append(N % 10)
    N = N // 10
Nlist = np.array(Nlist,dtype=np.int)

print(num753(Nlist,0))
Buggy python submission (verdict: Runtime Error):
N = int(input())
if N==1:
	print('Hello World')
else:
	A = int(input())
	B = int(input())
    print(A+B)

Fixed submission:
N = int(input())
if N == 1:
  print('Hello World')
else:
  A = int(input())
  B = int(input())
  print(A+B)

Buggy python submission (verdict: Runtime Error):
inpl = lambda: map(int,input().split())
N = int(input())
if N == 1:
  print('Hello World')
else:
  A, B = inpl()
  print(A+B)

Fixed submission:
N = int(input())
if N == 1:
  print('Hello World')
else:
  A = int(input())
  B = int(input())
  print(A+B)
Buggy python submission (verdict: Runtime Error):
import numpy as np
N = int(input())
x = np.empty(N,dtype=np.int)
y = np.empty(N,dtype=np.int)
h = np.empty(N,dtype=np.int)
for n in range(N):
    (x[n],y[n],h[n]) = map(int,input().split())

M = 100

grads = np.array([[1,1],[-1,1],[-1,-1],[1,-1]],dtype=np.int)
def height(x,y,h,i,j,d):
    # d=0-3
    return (h + grads[d,0]*(i-x) + grads[d,1]*(j-y))

def quadrant(x,y):
    if x > 0 and y >= 0:
        return 0
    elif y > 0:
        return 1
    elif x < 0:
        return 2
    else:
        return 3

Clist = [(Cx,Cy) for Cy in range(M+1) for Cx in range(M+1)]
k = h.argmax()
for (Cx,Cy) in Clist:
    H = height(x[k],y[k],h[k],Cx,Cy,quadrant(Cx-x[k],Cy-y[k]))
    for n in range(N):
        Hn = height(x[n],y[n],h[n],Cx,Cy,quadrant(Cx-x[n],Cy-y[n]))
        if h[n] == 0:
            if Hn < H:
                break
        else:
            if Hn != H:
                break
    else:
        break

print(i,j,H)

Fixed submission:
import numpy as np
N = int(input())
x = np.empty(N,dtype=np.int)
y = np.empty(N,dtype=np.int)
h = np.empty(N,dtype=np.int)
for n in range(N):
    (x[n],y[n],h[n]) = map(int,input().split())

M = 100

grads = np.array([[1,1],[-1,1],[-1,-1],[1,-1]],dtype=np.int)
def height(x,y,h,i,j,d):
    # d=0-3
    return (h + grads[d,0]*(i-x) + grads[d,1]*(j-y))

def quadrant(x,y):
    if x > 0 and y >= 0:
        return 0
    elif y > 0:
        return 1
    elif x < 0:
        return 2
    else:
        return 3

Clist = [(Cx,Cy) for Cy in range(M+1) for Cx in range(M+1)]
k = h.argmax()
for (Cx,Cy) in Clist:
    H = height(x[k],y[k],h[k],Cx,Cy,quadrant(Cx-x[k],Cy-y[k]))
    for n in range(N):
        Hn = height(x[n],y[n],h[n],Cx,Cy,quadrant(Cx-x[n],Cy-y[n]))
        if h[n] == 0:
            if Hn < H:
                break
        else:
            if Hn != H:
                break
    else:
        break

print(Cx,Cy,H)
Buggy python submission (verdict: Time Limit Exceeded):
(N,M)=map(int,input().split())
s = M//N;
while M%s:
    s = s-1
print(s)

Fixed submission:
import math
N, M = map(int, input().split())
sqrtM = round(math.sqrt(M))+1

if N < sqrtM:
  for i in range(N,sqrtM+1):
    if M % i == 0:
      print(M//i)
      exit()
  for i in range(N-1,0,-1):
    if M % i == 0:
      print(i)
      exit()
else:
  for i in range(M//N,0,-1):
    if M % i == 0:
      print(i)
      exit()
Buggy python submission (verdict: Runtime Error):
inpl = lambda: list(map(int,input().split()))
N, M, X, Y = inpl()
x = inpl()
y = inpl()

x.append(X)
y.append(Y)
xmax = max(X)
ymin = min(Y)
if xmax < ymin:
  print('No War')
else:
  print('War')

Fixed submission:
inpl = lambda: list(map(int,input().split()))
N, M, X, Y = inpl()
x = inpl()
y = inpl()
 
x.append(X)
y.append(Y)
xmax = max(x)
ymin = min(y)
if xmax < ymin:
  print('No War')
else:
  print('War')
Buggy python submission (verdict: Time Limit Exceeded):
inpl = lambda: list(map(int,input().split()))
MOD = 10**9 + 7
N, M = inpl()
 
def factorize(n):
  prime_list = []
  factorize_list = []
  i = 2
  while i <= n:
    for p in prime_list:
      if i % p == 0:
        break
    else:
      prime_list.append(i)
      k = 0
      while n % i == 0:
        n //= i
        k += 1
      factorize_list.append(k)
    i += 1
  return(factorize_list)

def H(n,k):
  h = 1
  L = n + k - 1
  k = min(n-1,k)
  for j in range(k):
    h *= L-j
  for j in range(k):
    h //= j+1
  return h

ans = 1
for k in factorize(M):
  ans *= H(N,k) % MOD
  ans %= MOD

print(ans)

Fixed submission:
import math

R = 10**9 + 7

def combination(n,k):
    if 2*k > n:
        k = n - k

    r = 1
    for i in range(n-k+1,n+1):
        r = (r*i)

    r = (r//math.factorial(k))

    return r

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

decomposition = []
i = 2
while i * i <= M:
    if M % i == 0:
        decomposition.append(0)
        while M % i ==0:
            decomposition[-1] = decomposition[-1] + 1
            M = M//i
    i = i + 1
if M > 1:
    decomposition.append(1)

H = [ combination(N+k-1,k) % R for k in decomposition]
r = 1
for h in H:
    r = (r*h) % R

print(r)

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

def combination(n,k):
    return (math.factorial(n)//math.factorial(k))//math.factorial(n-k)

R = 10**9 + 7

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

decomposition = []
i = 2
while i * i <= M:
    if M % i == 0:
        decomposition.append(0)
        while M % i ==0:
            decomposition[-1] = decomposition[-1] + 1
            M = M//i
    i = i + 1
if M > 1:
    decomposition.append(1)

H = [ combination(N+k-1,k) % R for k in decomposition]
r = 1
for h in H:
    r = (r*h) % R

print(r)

Fixed submission:
import math

R = 10**9 + 7

def combination(n,k):
    if 2*k > n:
        k = n - k

    r = 1
    for i in range(n-k+1,n+1):
        r = (r*i)

    r = (r//math.factorial(k))

    return r

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

decomposition = []
i = 2
while i * i <= M:
    if M % i == 0:
        decomposition.append(0)
        while M % i ==0:
            decomposition[-1] = decomposition[-1] + 1
            M = M//i
    i = i + 1
if M > 1:
    decomposition.append(1)

H = [ combination(N+k-1,k) % R for k in decomposition]
r = 1
for h in H:
    r = (r*h) % R

print(r)
Buggy python submission (verdict: Runtime Error):
inpl = lambda: list(map(int, input().split()))
H, W = inpl()
def next_sq(sq):
  h, w = sq
  if h % 2 == 0:
    if w == h-1:
      return h+1, w
    else:
      return h, w+1
  else:
    if w == 0:
      return h+1, w
    else:
      return h, w-1
a = [inpl() for _ in range(H)]
n = sum(sum(a[h][w] % 2 for w in range(W)) for h in range(H))
if n < 2:
  print(0)
  exit()
sq = (0, 0)
prev = None
for _ in range(H*W):
  h, w = sq
  if prev is not None:
    print(prev[0], prev[1], h, w)
    if a[h][w] % 2:
      n -= 1
      if n < 2:
        break
      prev = None
    else:
      prev = sq
  elif a[h][w] % 2:
	n -= 1
    prev = sq
  sq = next_sq(sq)

Fixed submission:
inpl = lambda: list(map(int,input().split()))

H, W = inpl()
A = []
for _ in range(H):
    A.append(inpl())

def pos(n):
    q, m = divmod(n, W)
    if q % 2:
        m = (W-1) - m
    return q, m

ans = []
f = 0
hn, wn = 0, 0
for n in range(H*W-1):
    h, w = hn, wn
    hn, wn = pos(n+1)
    if (f+A[h][w]) % 2:
        ans.append([h+1,w+1,hn+1,wn+1])
        f = 1
    else:
        f = 0

print(len(ans))
for rec in ans:
    print(rec[0],rec[1],rec[2],rec[3])
Buggy python submission (verdict: Runtime Error):
import bisect
inpl = lambda: list(map(int,input().split()))
N, K = inpl()
x = inpl()

infty = 10**9
c = bisect.bisect_left(x,0)
if x[c] > 0:
    K += 1
    N += 1
    x.insert(c,0)

if c >= K-1:
    turn = c-(K-1)
    ans = -x[turn]
    turn += 1
else:
    turn = 0
    ans = infty

while turn <= c and turn + K <= N:
    L = -x[turn]
    R = x[turn + K - 1]
    cur = L + R + min(L,R)
    if cur < ans:
        ans = cur
    turn += 1

print(ans)

Fixed submission:
import bisect
inpl = lambda: list(map(int,input().split()))
N, K = inpl()
x = inpl()

infty = 10**9
c = bisect.bisect_left(x,0)
if c == N:
    print(-x[-K])
    exit()
elif x[c] > 0:
    K += 1
    N += 1
    x.insert(c,0)

if c >= K-1:
    turn = c-(K-1)
else:
    turn = 0

ans = infty
while turn <= c and turn + K <= N:
    L = -x[turn]
    R = x[turn + K - 1]
    cur = L + R + min(L,R)
    if cur < ans:
        ans = cur
    turn += 1

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np
def inpl(): return list(map(int,input().split()))

N, M , Q = inpl()
#trains = np.zeros((N+1,N+1),dtype=np.int)
cumsum = np.zeros((N+1,N+1),dtype=np.int)
ans = np.zeros((N+1,N+1),dtype=np.int)

for i in range(M):
    L, R = inpl()
    cumsum[L,R] += 1

for l in range(1,N+1):
    for r in range(1,N+1):
        cumsum[l,r] += cumsum[l-1,r] + cumsum[l,r-1] - cumsum[l-1,r-1]

for l in range(1,N+1):
    for r in range(l,N+1):
        ans[l,r] = cumsum[r,r] - cumsum[l-1,r] - cumsum[r,l-1] + cumsum[l-1,l-1]

for i in range(Q):
    p, q = inpl()
    print(ans[p,q])

Fixed submission:
def inpl(): return list(map(int,input().split()))

N, M, Q = inpl()
cumsum = [0]*((N+1)**2)
ans = [0]*((N+1)**2)

for i in range(M):
    L, R = inpl()
    cumsum[L*(N+1)+R] += 1

for l in range(1,N+1):
    for r in range(1,N+1):
        cumsum[l*(N+1)+r] += cumsum[(l-1)*(N+1)+r] + cumsum[l*(N+1)+r-1] - cumsum[(l-1)*(N+1)+r-1]

for l in range(1,N+1):
    for r in range(l,N+1):
        ans[l*(N+1)+r] = cumsum[r*(N+1)+r] - cumsum[(l-1)*(N+1)+r] - cumsum[r*(N+1)+l-1] + cumsum[(l-1)*(N+1)+l-1]

for i in range(Q):
    p, q = inpl()
    print(ans[p*(N+1)+q])

Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np
def inpl(): return list(map(int,input().split()))

N, M , Q = inpl()
trains = np.zeros((N,N),dtype=np.int)
ans = np.zeros((N,N),dtype=np.int)

for i in range(M):
    L, R = inpl()
    trains[L-1,R-1] += 1

for l in range(N):
    for r in range(l,N):
        ans[l,r] = trains[l:r+1,l:r+1].sum()

for i in range(Q):
    p, q = inpl()
    print(ans[p-1,q-1])

Fixed submission:
def inpl(): return list(map(int,input().split()))

N, M, Q = inpl()
cumsum = [0]*((N+1)**2)
ans = [0]*((N+1)**2)

for i in range(M):
    L, R = inpl()
    cumsum[L*(N+1)+R] += 1

for l in range(1,N+1):
    for r in range(1,N+1):
        cumsum[l*(N+1)+r] += cumsum[(l-1)*(N+1)+r] + cumsum[l*(N+1)+r-1] - cumsum[(l-1)*(N+1)+r-1]

for l in range(1,N+1):
    for r in range(l,N+1):
        ans[l*(N+1)+r] = cumsum[r*(N+1)+r] - cumsum[(l-1)*(N+1)+r] - cumsum[r*(N+1)+l-1] + cumsum[(l-1)*(N+1)+l-1]

for i in range(Q):
    p, q = inpl()
    print(ans[p*(N+1)+q])
Buggy python submission (verdict: Time Limit Exceeded):
import math
N = int(input())
A = list(map(int, input().split()))

sum = 0
for i in range(N-1):
    for j in range(i+1, N):
        sum += A[i] * A[j]

const = 10 ** 9 + 7
print(sum % const)

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

res = []
res.append(A[0])
for i in range(len(A)-1):
    res.append(res[i] + A[i+1])

sum = 0
for i in range(N-1):
    sum += A[i] * (res[N - 1] - res[i])

print(sum % (10**9+7))
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
AB = list(map(int, input().split()))

limit = 10 ** 18

sum = 1
for i in range(N):
    sum *= AB[i]

if (limit < sum):
    print(-1)
else:
    print(sum)



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

limit = 1000000000000000000

sum = 1
for i in range(N):
    if (limit < sum or sum == -1):
        sum = -1
    else:
        sum *= AB[i]
    if (AB[i] == 0):
        print(0)
        exit()

if (limit < sum):
    sum = -1

print(sum)
Buggy python submission (verdict: Time Limit Exceeded):
T = input()

replace = ""
target = []
for i in range(len(T)):
    if (T[i] == "?"):
        replace += "D"
    else:
        replace += T[i]

print(replace)

Fixed submission:
T = input()

print(T.replace("?", "D"))
Buggy python submission (verdict: Time Limit Exceeded):
import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

def gcd_list(numbers):
    return reduce(math.gcd, numbers)

K = int(input()) + 1

sum = 0
for i in range(1, K):
    for j in range(1, K):
        for k in range(1, K):
            sum += gcd(i, j, k)

print(sum)

Fixed submission:
import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

K = int(input()) + 1
cache = []

for i in range(1, K):
    for j in range(i, K):
        if (i == j):
            continue
        else:
            cache.append(gcd(i, j))


sum = 0
for j in range(1, K):
    for i in range(len(cache)):
        if (cache[i] == 1 or j == 1):
            sum += 1 * 2
        else:
            sum += gcd(cache[i], j) * 2
    for k in range(1, K):
        sum += gcd(j, k)

print(sum)