Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(20000)

N, Q = map(int, input().split())
T = [[] for _ in range(N)]
ans = [0] * N

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

#再帰は危険かも？
def dfs(s):
  ans[s-1] += x
  for i in T[s-1]:
    dfs(i)

for _ in range(Q):
  p, x = map(int, input().split())
  dfs(p)

print(*ans)

Fixed submission:
import sys

input = sys.stdin.readline
sys.setrecursionlimit(10**6)

N, Q = map(int, input().split())
T = [[] for _ in range(N)]
ans = [0] * N

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

cnt = [0] * N
for _ in range(Q):
  p, x = map(int, input().split())
  p -= 1
  cnt[p] += x

def dfs(x, d, s): # x:計算する頂点（上側）, d:計算済み(0)か否か(1), s:頂点xの値
  for y in T[x]: # 頂点xとつながる各頂点yの計算を行う
    if d[y] == 1: # 頂点yが計算未了の場合
      s += cnt[y] # 頂点xの値sに頂点yの値を足す
      ans[y] = s # 頂点yの値はsに確定
      d[y] = 0 # 頂点yの計算は終わったのでd[y]=0とする
      dfs(y, d, s) # 頂点yの下層についても再帰的に計算
      s -= cnt[y] # 頂点yの下層の計算が終わったので、sを頂点xの値に戻す

d = [1] * N
d[0] = 0

ans[0] = cnt[0]
s = cnt[0]

dfs(0, d, s)

print(*ans)
Buggy python submission (verdict: Runtime Error):
import collections
from sympy import prime

N = int(input())
count = 1
lis = [0]*N

for i in range(N):
  s = input()
  for j in range(10):
    count *= prime(ord(s[j])-ord("a")+1)
  lis[i] += count
  count = 0

dic = collections.Counter(lis)
newlis = list(dic.values())
ans = sum([(i*(i-1))//2 for i in newlis]) 

print(ans)

Fixed submission:
from collections import defaultdict

N = int(input())
S = defaultdict(int)

for i in range(N):
  s = sorted(input())
  w = "".join(s)
  S[w] += 1

ans = sum([(i*(i-1))//2 for i in list(S.values())])

print(ans)

Buggy python submission (verdict: Runtime Error):
N = int(input())
count = 0
ans = 0
lis = [0]*N

for i in range(N):
  s = input()
  for j in range(10):
    count += ord(s[j])
  lis[i] += count
  count = 0

dic = collections.Counter(lis)
newlis = list(dic.values())

for i in newlis:
  ans += i*(i-1)/2

print(int(ans))

Fixed submission:
from collections import defaultdict

N = int(input())
S = defaultdict(int)

for i in range(N):
  s = sorted(input())
  w = "".join(s)
  S[w] += 1

ans = sum([(i*(i-1))//2 for i in list(S.values())])

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N, M = map(int, input().split())
AB = []

for _ in range(N):
  A, B = map(int, input().split())
  AB.append((A, B))

AB.sort()
AB.sort(key = lambda x:x[1], reverse = True)

ans = [0]*(M+1)

for a, b in AB:
  while a <= M:
    if ans[a] < b:
      ans[a] = b
      break
    a += 1

print(sum(ans))

Fixed submission:
from heapq import heappop,heappush
from collections import defaultdict

N, M = map(int, input().split())
D = defaultdict(list)

for _ in range(N):
  A, B = map(int, input().split())
  D[A].append(B)

H = []
ans = [0]*(M+1)

for i in range(1, M+1):
  for j in D[i]:
    heappush(H, -j)
  if H:
    a = heappop(H)
    ans[i] = -a

print(sum(ans))
Buggy python submission (verdict: Runtime Error):

N, D = map(int, input().split())
Ps = []
count = 0

for i in range(N):
  P = list(map(int, input().split()))
  Ps.append(P)

def dis2(A, B):
  dis = 0
  for i in range(D):
    dis += (A[i] - B[i])**2
  return dis

for i in range(N-1):
  for j in range(i+1, N):
    if math.sqrt(dis2(Ps[i], Ps[j])).is_integer():
      count += 1

print(count)

Fixed submission:
import math

N, D = map(int, input().split())
Ps = []
count = 0

for i in range(N):
  P = list(map(int, input().split()))
  Ps.append(P)

def dis2(A, B):
  dis = 0
  for i in range(D):
    dis += (A[i] - B[i])**2
  return dis

for i in range(N-1):
  for j in range(i+1, N):
    if math.sqrt(dis2(Ps[i], Ps[j])).is_integer():
      count += 1

print(count)
Buggy python submission (verdict: Time Limit Exceeded):
L, R = map(int, input().split())
ans = 2019

for i in range(L, R):
    for j in range(i+1, R+1):
        a = i % 2019
        b = j % 2019
        x = (a * b) % 2019
        ans = min(ans, x)

print(ans)

Fixed submission:
L, R = map(int, input().split())
R = min(L+2019, R)
ans = 2019
Flag = False

for i in range(L, R):
    for j in range(i+1, R+1):
        x = (i * j) % 2019
        ans = min(ans, x)
        if ans == 0:
            Flag = True
            break
    if Flag:
        break

print(ans)
Buggy python submission (verdict: Runtime Error):
import scipy.linalg as linalg

N = int(input())
b = np.array(list(map(int, input().split())))

A = np.zeros(N**2).reshape(N, N)
for i in range(N):
    for j in range(N):
        if i == j or i+1 == j:
            A[i, j] = 1
        else:
            continue
A[N-1, 0] = 1
A = A / 2
A_inv = linalg.inv(A)

x = np.dot(A_inv, b)
print(*x)

Fixed submission:
N = int(input())
A = list(map(int, input().split()))
ans = []

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

ans.append(x1)

for i in range(N-1):
  ans.append(2*A[i] - ans[i])

print(*ans)
Buggy python submission (verdict: Runtime Error):
import math

A, B, C, D = map(int, input().split())
lcm = (C * D) // math.gcd(C, D)

def f(x):
  return B//x - (A-1)//x

print( (B - A + 1) - (f(C) + f(D) - f(lcm)) )

Fixed submission:
import fractions

A, B, C, D = map(int, input().split())
lcm = (C * D) // fractions.gcd(C, D)

def f(x):
  return B//x - (A-1)//x

print( (B - A + 1) - (f(C) + f(D) - f(lcm)) )
Buggy python submission (verdict: Runtime Error):
N, K = map(int, input().split())
ans = 0

for i in range(1, N+1):
  if i < K:
    cnt = math.ceil(math.log2(K / i))
    ans += (1 / N) * (1 / 2)**cnt
  else:
    ans += 1 / N

print(ans)

Fixed submission:
import math

N, K = map(int, input().split())
ans = 0

for i in range(1, N+1):
  if i < K:
    cnt = math.ceil(math.log2(K / i))
    ans += (1 / N) * (1 / 2)**cnt
  else:
    ans += 1 / N

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
X, Y, Z, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = sorted(map(int, input().split()), reverse=True)

AB = [0]*(X*Y)
i = 0
for a in A:
  for b in B:
    AB[i] = a+b
    i += 1
AB.sort(reverse = True)

ans = [0]*(K*Z)
j = 0
for ab in AB[:K]:
  for c in C:
    ans[j] = ab+c
    j += 1

ans.sort(reverse=True)
print(*ans[:K], sep="\n")

Fixed submission:
X, Y, Z, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = sorted(map(int, input().split()), reverse=True)

AB = []
for a in A:
  for b in B:
    AB.append(a+b)
AB.sort(reverse = True)

ans = []
for ab in AB[:K]:
  for c in C:
    ans.append(ab+c)

ans.sort(reverse=True)
print(*ans[:K], sep="\n")

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

X, Y, Z, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = sorted(map(int, input().split()), reverse=True)

AB = []
for a in A:
  for b in B:
    AB.append(a+b)
AB.sort(reverse = True)

ans = []
for ab in AB[:K]:
  for c in C:
    ans.append(ab+c)

ans.sort(reverse=True)
print(*ans[:K], sep="\n")

Fixed submission:
X, Y, Z, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = sorted(map(int, input().split()), reverse=True)

AB = []
for a in A:
  for b in B:
    AB.append(a+b)
AB.sort(reverse = True)

ans = []
for ab in AB[:K]:
  for c in C:
    ans.append(ab+c)

ans.sort(reverse=True)
print(*ans[:K], sep="\n")

Buggy python submission (verdict: Time Limit Exceeded):
X, Y, Z, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = sorted(map(int, input().split()), reverse=True)

AB = []
for a in A:
  for b in B:
    AB.append(a+b)
AB.sort(reverse = True)

ans = []
for ab in AB[:K]:
  for c in C:
    ans.append(ab+c)

ans.sort(reverse=True)
print(*ans[:K], sep="\n")

Fixed submission:
X, Y, Z, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = sorted(map(int, input().split()), reverse=True)

AB = []
for a in A:
  for b in B:
    AB.append(a+b)
AB.sort(reverse = True)

ans = []
for ab in AB[:K]:
  for c in C:
    ans.append(ab+c)

ans.sort(reverse=True)
print(*ans[:K], sep="\n")
Buggy python submission (verdict: Runtime Error):
A, B, K = map(int, input().split())
cnt = 0

for i in range(100, 0, -1):
  if A%i == 0 and B%i == 0:
    cnt += 1
    if cnt = K:
      print(i)
      exit()

Fixed submission:
A, B, K = map(int, input().split())

def make_div(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i:
        divisors.append(n//i)
  return divisors

print(sorted(set(make_div(A))&set(make_div(B)), reverse=True)[K-1])
Buggy python submission (verdict: Time Limit Exceeded):
class UnionFind():
  def __init__(self, n):
    self.n = n
    self.parents = [-1] * n

  def find(self, x):
    if self.parents[x] < 0:
      return x
    else:
      self.parents[x] = self.find(self.parents[x])
      return self.parents[x]

  def union(self, x, y):
    x = self.find(x)
    y = self.find(y)
    if x == y:
      return
    if self.parents[x] > self.parents[y]:
      x, y = y, x
    self.parents[x] += self.parents[y]
    self.parents[y] = x

  def size(self, x):
    return -self.parents[self.find(x)]

  def same(self, x, y):
    return self.find(x) == self.find(y)

  def members(self, x):
    root = self.find(x)
    return [i for i in range(self.n) if self.find(i) == root]

  def roots(self):
    return [i for i, x in enumerate(self.parents) if x < 0]

  def group_count(self):
    return len(self.roots())

  def all_group_members(self):
    return {r: self.members(r) for r in self.roots()}

  def __str__(self):
    return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

N, M = map(int, input().split())
AB = []
for _ in range(M):
  A, B = map(int, input().split())
  AB.append((A-1, B-1))

uf = UnionFind(N)
unhappy = [N*(N-1)//2]

for A, B in reversed(AB):
  uf.union(A, B)
  happy = 0
  for i in uf.roots():
    temp = uf.size(i)
    happy += temp*(temp-1)//2
  unhappy.append(N*(N-1)//2 - happy)

print(*reversed(unhappy[:-1]), sep="\n")

Fixed submission:
class UnionFind():
  def __init__(self, n):
    self.n = n
    self.parents = [-1] * n

  def find(self, x):
    if self.parents[x] < 0:
      return x
    else:
      self.parents[x] = self.find(self.parents[x])
      return self.parents[x]

  def union(self, x, y):
    x = self.find(x)
    y = self.find(y)
    if x == y:
      return
    if self.parents[x] > self.parents[y]:
      x, y = y, x
    self.parents[x] += self.parents[y]
    self.parents[y] = x

  def size(self, x):
    return -self.parents[self.find(x)]

  def same(self, x, y):
    return self.find(x) == self.find(y)

  def members(self, x):
    root = self.find(x)
    return [i for i in range(self.n) if self.find(i) == root]

  def roots(self):
    return [i for i, x in enumerate(self.parents) if x < 0]

  def group_count(self):
    return len(self.roots())

  def all_group_members(self):
    return {r: self.members(r) for r in self.roots()}

  def __str__(self):
    return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

N, M = map(int, input().split())
AB = []
for _ in range(M):
  A, B = map(int, input().split())
  AB.append((A-1, B-1))

uf = UnionFind(N)
unhappy = [N*(N-1)//2]

def conb(x):
  return x*(x-1)//2

for A, B in reversed(AB):
  old_ap, old_bp = uf.find(A), uf.find(B)
  if old_ap == old_bp:
    uf.union(A, B)
    unhappy.append(unhappy[-1])
  else:
    old_happy = conb(uf.size(old_ap)) + conb(uf.size(old_bp))
    uf.union(A, B)
    new_happy = conb(uf.size(A))
    happy = new_happy - old_happy
    unhappy.append(unhappy[-1] - happy)

print(*reversed(unhappy[:-1]), sep="\n")
Buggy python submission (verdict: Runtime Error):
N, K = map(int, input().split())
TD = []

for _ in range(N):
  TD.append(tuple(map(int, input().split())))

TD.sort(key = lambda x:x[1], reverse=True)
TD += [(TD[-1][-1], 0)]

ans1 = 0
T1 = [0]*N
L = []
cnt1 = 0
temp = TD[0][1]

ans2 = 0
T2 = [0]*N
D2 = []
cnt2 = 0

for t, d in TD:
  if cnt1 < K:
    if temp == d and T1[t-1] == 1:
      L.append((t, d))
    elif temp == d and T1[t-1] == 0:
      T1[t-1] = 1
      ans1 += d
      cnt1 += 1
    else:
      while L:
        if cnt1 == K:
          break
        a, b = L.pop()
        ans1 += b
        cnt1 += 1
      if cnt1 < K:
        T1[t-1] = 1
        ans1 += d
        cnt1 += 1
        temp = d
  if cnt2 < K:
    if T2[t-1]:
      D2.append(d)
    else:
      T2[t-1] = 1
      ans2 += d
      cnt2 += 1

ans1 += sum(T1)**2
ans2 += sum(D2[:K-cnt2]) + sum(T2)**2

print(max(ans1, ans2))

Fixed submission:
from collections import defaultdict
from heapq import heappop, heappush

N, K = map(int, input().split())
TD = []

for _ in range(N):
  TD.append(tuple(map(int, input().split())))

TD.sort(key = lambda x:x[1], reverse=True)
TD += [(TD[-1][0], 0)]

D = defaultdict(list)
T = [0]*N
H = []
ans = 0

for i in range(K):
  t, d = TD[i]
  T[t-1] += 1
  D[t].append(d)
  ans += d

cnt = sum(1 for c in T if c >= 1)
ans += cnt**2

for t in range(1, N+1):
  if T[t-1] >= 2:
    heappush(H, (D[t].pop(), t))
    T[t-1] -= 1

#print(ans, H, T, cnt)
for i in range(K, N):
  if H:
    t1, d1 = TD[i]
    d2, t2 = heappop(H)
    #print(t1, d1, t2, d2)
    if T[t1-1] == 0 and d1 - d2 + 2*cnt + 1 >= 0:
      ans += d1 - d2 + 2*cnt + 1
      cnt += 1
      T[t1-1] += 1
      if T[t2-1] >= 2:
        T[t2-1] -= 1
      if T[t2-1] >= 2:
        heappush(H, (D[t2].pop(), t2))
    else:
      heappush(H, (d2, t2))
    #print(ans, H, T, cnt)

#元のやつとの組み合わせ...？
ans2 = 0
T2 = [0]*N
D2 = []
cnt2 = 0
 
for t, d in TD:
  if cnt2 < K:
    if T2[t-1]:
      D2.append(d)
    else:
      T2[t-1] = 1
      ans2 += d
      cnt2 += 1

ans2 += sum(D2[:K-cnt2]) + sum(T2)**2

print(max(ans, ans2))
Buggy python submission (verdict: Time Limit Exceeded):
from functools import lru_cache

N, W = map(int, input().split())
WV = []

for i in range(N):
  w, v = map(int, input().split())
  WV.append((w, v))

@lru_cache(None)
def Knap(i, j):
  ret = 0
  if i == N:
    ret = 0
  elif j < WV[i][0]:
    ret = Knap(i+1, j)
  else:
    ret = max(Knap(i+1, j), Knap(i+1, j-WV[i][0])+WV[i][1] )
  return ret

print(Knap(0, W))

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

dp = [[0]*(W+1) for _ in range(N+1)]

for i in range(N):
  w, v = map(int, input().split())
  for j in range(W+1):
    if j - w < 0:
      dp[i+1][j] = dp[i][j]
    else:
      dp[i+1][j] = max(dp[i][j], dp[i][j-w] + v)

print(dp[-1][-1])

Buggy python submission (verdict: Time Limit Exceeded):
from functools import lru_cache

N, W = map(int, input().split())
WV = []

for i in range(N):
  w, v = map(int, input().split())
  WV.append((w, v))

@lru_cache(None)
def Knap(i, j):
  ret = 0
  if i == N:
    ret = 0
  elif j < WV[i][0]:
    ret = Knap(i+1, j)
  else:
    ret = max(Knap(i+1, j), Knap(i+1, j-WV[i][0])+WV[i][1] )
  return ret

print(Knap(0, W))

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

dp = [[0]*(W+1) for _ in range(N+1)]

for i in range(N):
  w, v = map(int, input().split())
  for j in range(W+1):
    if j - w < 0:
      dp[i+1][j] = dp[i][j]
    else:
      dp[i+1][j] = max(dp[i][j], dp[i][j-w] + v)

print(dp[-1][-1])

Buggy python submission (verdict: Time Limit Exceeded):
N, W = map(int, input().split())

dp = [[0]*(W+1) for _ in range(N+1)]

for i in range(N):
  w, v = map(int, input().split())
  for j in range(W+1):
    if j - w < 0:
      dp[i+1][j] = dp[i][j]
    else:
      dp[i+1][j] = max(dp[i][j], dp[i][j-w] + v)

print(dp[-1][-1])

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

dp = [[0]*(W+1) for _ in range(N+1)]

for i in range(N):
  w, v = map(int, input().split())
  for j in range(W+1):
    if j - w < 0:
      dp[i+1][j] = dp[i][j]
    else:
      dp[i+1][j] = max(dp[i][j], dp[i][j-w] + v)

print(dp[-1][-1])
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

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

INF = float("inf")
dp = [0] + [INF] * 10**5

for _ in range(N):
  w, v = map(int, input().split())
  for j in range(10**5, v-1, -1):
    dp[j] = min(dp[j], dp[j-v] + w)

for i, x in enumerate(dp):
  if x <= W:
    ans = i

print(ans)

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

INF = 10**11 + 1
dp = [[INF]*(10**5 + 1) for _ in range(N+1)]
dp[0][0] = 0

for i in range(N):
  w, v = map(int, input().split())
  for j in range(10**5 + 1):
    dp[i+1][j] = min(dp[i][j], dp[i][max(0, j-v)] + w)

ans = 0
    
for i, x in enumerate(dp[-1]):
  if x <= W:
    ans = i

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N, W = map(int, input().split())

INF = float("inf")
dp = [0] + [INF] * 10**5

for _ in range(N):
  w, v = map(int, input().split())
  for j in range(10**5, v-1, -1):
    dp[j] = min(dp[j], dp[j-v] + w)

for i, x in enumerate(dp):
  if x <= W:
    ans = i

print(ans)

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

INF = 10**11 + 1
dp = [[INF]*(10**5 + 1) for _ in range(N+1)]
dp[0][0] = 0

for i in range(N):
  w, v = map(int, input().split())
  for j in range(10**5 + 1):
    dp[i+1][j] = min(dp[i][j], dp[i][max(0, j-v)] + w)

ans = 0
    
for i, x in enumerate(dp[-1]):
  if x <= W:
    ans = i

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N, W = map(int, input().split())

INF = 10**11 + 1
dp = [[INF]*(10**5 + 1) for _ in range(N+1)]
dp[0][0] = 0

for i in range(N):
  w, v = map(int, input().split())
  for j in range(10**5 + 1):
    dp[i+1][j] = min(dp[i][j], dp[i][max(0, j-v)] + w)

ans = 0
    
for i, x in enumerate(dp[-1]):
  if x <= W:
    ans = i

print(ans)

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

INF = 10**11 + 1
dp = [[INF]*(10**5 + 1) for _ in range(N+1)]
dp[0][0] = 0

for i in range(N):
  w, v = map(int, input().split())
  for j in range(10**5 + 1):
    dp[i+1][j] = min(dp[i][j], dp[i][max(0, j-v)] + w)

ans = 0
    
for i, x in enumerate(dp[-1]):
  if x <= W:
    ans = i

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

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

G = [[] for _ in range(N+1)]

for _ in range(M):
  L, R = map(int, input().split())
  G[L].append(R)

for i in range(N+1):
  G[i].sort()

for _ in range(Q):
  p, q = map(int, input().split())
  ans = 0
  for i in range(p, q+1):
    ans += bisect(G[i], q)
  print(ans)

Fixed submission:
N, M, Q = map(int, input().split())

G = [[0]*(N+1) for _ in range(N+1)]

for _ in range(M):
  L, R = map(int, input().split())
  G[L][R] += 1

for i in range(N+1):
  for j in range(1, N+1):
    G[i][j] += G[i][j-1]

for _ in range(Q):
  p, q = map(int, input().split())
  ans = 0
  for i in range(p, q+1):
    ans += G[i][q]
  print(ans)

Buggy python submission (verdict: Runtime Error):
N, M, Q = map(int, input().split())
tL = []
tR = []
for i in range(M):
    a, b = map(int, input().split())
    tL.append(a)
    tR.append(b)
ql = []
qr = []
for j in range(Q):
    c, d = map(int, input().split())
    ql.append(c)
    qr.append(d)

for j in range(Q):
    count = 0
    for i in range(M):
        if ql[j] => tL[i] or tR[i] => qr[j]:
            continue
        else:
            count += 1
    print(count)

Fixed submission:
N, M, Q = map(int, input().split())

G = [[0]*(N+1) for _ in range(N+1)]

for _ in range(M):
  L, R = map(int, input().split())
  G[L][R] += 1

for i in range(N+1):
  for j in range(1, N+1):
    G[i][j] += G[i][j-1]

for _ in range(Q):
  p, q = map(int, input().split())
  ans = 0
  for i in range(p, q+1):
    ans += G[i][q]
  print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N, M, Q = map(int, input().split())
tL = []
tR = []
for i in range(M):
    a, b = map(int, input().split())
    tL.append(a)
    tR.append(b)
ql = []
qr = []
for j in range(Q):
    c, d = map(int, input().split())
    ql.append(c)
    qr.append(d)

for j in range(Q):
    count = 0
    for i in range(M):
        if ql[j] <= tL[i] and tR[i] <= qr[j]:
            count += 1
    print(count)

Fixed submission:
N, M, Q = map(int, input().split())

G = [[0]*(N+1) for _ in range(N+1)]

for _ in range(M):
  L, R = map(int, input().split())
  G[L][R] += 1

for i in range(N+1):
  for j in range(1, N+1):
    G[i][j] += G[i][j-1]

for _ in range(Q):
  p, q = map(int, input().split())
  ans = 0
  for i in range(p, q+1):
    ans += G[i][q]
  print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np
import itertools

N, M = map(int, input().split())
lists = []
for i in range(N):
    li =list(map(int, input().split()))
    lists.extend(li)
    li.clear()
    
Mat = np.reshape(lists, (N, 3))

X = 0
Y = 0
Z = 0
V = -np.inf

L = range(1, N+1)
for C in itertools.combinations(L, M):
    for j in C:
        X += Mat[j-1, 0]
    for j in C:
        Y += Mat[j-1, 1]
    for j in C:
        Z += Mat[j-1, 2]
    if abs(X) + abs(Y) + abs(Z) > V:
        V = abs(X) + abs(Y) + abs(Z)
    X = 0
    Y = 0
    Z = 0

print(V)

Fixed submission:
from itertools import product

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

for i in range(N):
  x, y, z = map(int, input().split())
  L[i] += [x, y, z]

ans = 0

for pm in product([-1, 1], repeat=3):
  temp = []
  for l in L:
    temp.append(pm[0]*l[0] + pm[1]*l[1] + pm[2]*l[2])
  temp.sort(reverse = True)
  ans = max(ans, sum(temp[:M]))

print(ans)
Buggy python submission (verdict: Runtime Error):
X = int(input())

if X == 1:
  print(1)
  exit()

ans = 0

for b in range(2, int(x**0.5)+2):
  temp = b
  while temp <= X:
    ans = max(ans, temp)
    temp *= b

print(ans)

Fixed submission:
X = int(input())

if X == 1:
  print(1)
  exit()

ans = 0

for b in range(2, int(X**0.5)+2):
  temp = b
  while temp <= X:
    ans = max(ans, temp)
    temp *= b

print(ans)
Buggy python submission (verdict: Runtime Error):
A, B, C, D = map(int, input().split())

print(min(A, B) + min(C, D))

Fixed submission:
ans = []

for _ in range(4):
  ans.append(int(input()))

print(min(ans[:2]) + min(ans[2:]))
Buggy python submission (verdict: Time Limit Exceeded):
from itertools import permutations

N, M, R = map(int, input().split())
r = list(map(lambda x: int(x)-1, input().split()))

INF = 10**9
cost = [[INF]*N for _ in range(N)]
for _ in range(M):
  A, B, C = map(int, input().split())
  A -= 1
  B -= 1
  cost[A][B] = C
  cost[B][A] = C

for k in range(N):
  for i in range(N):
    for j in range(N):
      cost[i][j] = min(cost[i][j], cost[i][k]+cost[k][j])

ans = INF

for route in permutations(r):
  temp = 0
  for i in range(R-1):
    temp += cost[route[i]][route[i+1]]
  ans = min(ans, temp)

print(ans)

Fixed submission:
from itertools import permutations

N, M, R = map(int, input().split())
r = list(map(lambda x: int(x)-1, input().split()))

INF = 10**9
cost = [[INF]*N for _ in range(N)]
for _ in range(M):
  A, B, C = map(int, input().split())
  A -= 1
  B -= 1
  cost[A][B] = C
  cost[B][A] = C

for k in range(N):
  for i in range(N):
    for j in range(N):
      cost[i][j] = min(cost[i][j], cost[i][k]+cost[k][j])

ans = INF

for route in permutations(r):
  temp = 0
  for i in range(R-1):
    temp += cost[route[i]][route[i+1]]
  ans = min(ans, temp)

print(ans)
Buggy python submission (verdict: Runtime Error):
X, A, B = map(int, input().split())

print(min(abs(X-A), abs(B-X))

Fixed submission:
X, A, B = map(int, input().split())
D = {abs(X-A):"A", abs(X-B):"B"}

print(D[min(abs(X-A), abs(B-X))])
Buggy python submission (verdict: Runtime Error):
print(~input())

Fixed submission:
a = int(input())
print("1" if(a == 0) else "0")
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a  = [int(i) for i in input().split()]
mod = 10 ** 9 + 7
ans = 0
for i in range(n):
    for j in range(i+1, n):
        ans += (a[i] * a[j]) % mod
        ans %= mod

print(ans)

Fixed submission:
from itertools import accumulate
n = int(input())
a = [int(i) for i in input().split()]
mod = 10 ** 9 + 7
a_acc = list(accumulate(a))
ans = 0
for i in range(n):
    ans += (a[i] * (a_acc[-1] - a_acc[i])) % mod
    ans %= mod
print(ans)