Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
def lcs(X, Y):
    m = len(X)
    n = len(Y)
    c = [[0 for i in range(n+1)] for i in range(m+1)]
    for i in range(1,m+1):
        for j in range(1,n+1):
            if X[i -1] == Y[j - 1]:
                c[i][j] = c[i-1][j-1] + 1
            elif c[i -1][j] >= c[i][j - 1]:
                c[i][j] = c[i-1][j]
            else:
                c[i][j] = c[i][j-1]
    return str(c[m][n])

q = int(input())
for i in range(q):
    X = input()
    Y = input()
    print(lcs(X, Y))

Fixed submission:
import sys
def lcs(X, Y):
    indices = [0]
    for c in Y:
        for i in range(len(indices) - 1, -1, -1):
            tmp = X.find(c, indices[i])
            if tmp + 1:
                if i + 1 < len(indices):
                    indices[i + 1] = min(indices[i + 1], tmp + 1)
                else:
                    indices.append(tmp + 1)
    return len(indices) - 1

q = int(input())
for i in range(q):
    X = sys.stdin.readline().rstrip('\r\n')
    Y = sys.stdin.readline().rstrip('\r\n')
    print(lcs(X, Y))

Buggy python submission (verdict: Time Limit Exceeded):
import sys
def lcs(X, Y):
    m = len(X)
    n = len(Y)
    c = [[0 for i in range(n+1)] for i in range(m+1)]
    for i in range(1,m+1):
        for j in range(1,n+1):
            if X[i -1] == Y[j - 1]:
                c[i][j] = c[i-1][j-1] + 1
            elif c[i -1][j] >= c[i][j - 1]:
                c[i][j] = c[i-1][j]
            else:
                c[i][j] = c[i][j-1]
    return str(c[m][n])

q = int(input())
for i in range(q):
    X = sys.stdin.readline().rstrip('\r\n')
    Y = sys.stdin.readline().rstrip('\r\n')
    print(lcs(X, Y))
                

Fixed submission:
import sys
def lcs(X, Y):
    indices = [0]
    for c in Y:
        for i in range(len(indices) - 1, -1, -1):
            tmp = X.find(c, indices[i])
            if tmp + 1:
                if i + 1 < len(indices):
                    indices[i + 1] = min(indices[i + 1], tmp + 1)
                else:
                    indices.append(tmp + 1)
    return len(indices) - 1

q = int(input())
for i in range(q):
    X = sys.stdin.readline().rstrip('\r\n')
    Y = sys.stdin.readline().rstrip('\r\n')
    print(lcs(X, Y))
Buggy python submission (verdict: Runtime Error):
t=input()
p=input()
lt=len(t)
lp=len(p)
for i in range(lt-lp+1):
    if t[i:i+l_p]==p:print(i)

Fixed submission:
t=input()
p=input()
lt=len(t)
lp=len(p)
for i in range(lt-lp+1):
    if t[i:i+lp]==p:print(i)
Buggy python submission (verdict: Time Limit Exceeded):
x,y=map(int, input().split())

def answer(x,y):
 for i in range(y, 0, -1):
  if x % i == 0 and y % i == 0:
   return i
 
if x == y:
 print(x)
elif x >= y:
 print(str(answer(x, x%y)))
else:
 print(str(answer(y, y%x)))

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

def gcd(x,y):
 if x < y:
  x,y = y,x
 while y > 0:
  r = x % y
  x = y
  y = r
 return x

print(str(gcd(x,y)))
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
A = [int(input()) for i in range(n)]

def insertionSort(A, n, g):
 global cnt
 for i in range(g, n):
  v = A[i]
  j = i - g
  while j >= 0 and A[j] > v:
   A[j + g] = A[j]
   j -= g
   cnt +=1
  A[j + g] = v

def shellSort(A, n, m, G):
 A1 = A[:]
 global cnt
 cnt = 0
 for i in range(m):
  insertionSort(A1, n, G[i])
 return A1

def Gmake(m):
 G=[]
 for i in range(m):
  G.append(3*i + 1)
 G.reverse()
 return G

for m in range(1, 100):
 G = Gmake(m)
 A2 = shellSort(A, n, m, G)
 if cnt < n ** 1.5:
  print(str(m))
  print(" ".join(map(str, G)))
  print(str(cnt))
  for i in A2:
   print(str(i))
  break

Fixed submission:
n = int(input())
A = [int(input()) for i in range(n)]

def insertionSort(A, n, g):
 global cnt
 for i in range(g, n):
  v = A[i]
  j = i - g
  while j >= 0 and A[j] > v:
   A[j + g] = A[j]
   j -= g
   cnt +=1
  A[j + g] = v

def shellSort(A, n, m, G):
 A1 = A[:]
 global cnt
 cnt = 0
 for i in range(m):
  insertionSort(A1, n, G[i])
 return A1

def Gmake(n):
 G=[]
 k = 1
 while k <= n and len(G) < 100:
  G.append(k)
  k = 3 * k + 1
 G.reverse()
 return G

G = Gmake(n)
A2 = shellSort(A, n, len(G), G)
print(str(len(G)))
print(" ".join(map(str, G)))
print(str(cnt))
for i in A2:
 print(str(i))

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
A = [int(input()) for i in range(n)]

def insertionSort(A, n, g):
 global cnt
 for i in range(g, n):
  v = A[i]
  j = i - g
  while j >= 0 and A[j] > v:
   A[j + g] = A[j]
   j -= g
   cnt +=1
  A[j + g] = v

def shellSort(A, n, m, G):
 A1 = A[:]
 global cnt
 cnt = 0
 for i in range(m):
  insertionSort(A1, n, G[i])
 return A1

def Gmake(n):
 G=[]
 k = 1
 while k <= n and len(G) < 100:
  G.append(k)
  k += 3
 G.reverse()
 return G

G = Gmake(n)
A2 = shellSort(A, n, len(G), G)
print(str(len(G)))
print(" ".join(map(str, G)))
print(str(cnt))
for i in A2:
 print(str(i))

Fixed submission:
n = int(input())
A = [int(input()) for i in range(n)]

def insertionSort(A, n, g):
 global cnt
 for i in range(g, n):
  v = A[i]
  j = i - g
  while j >= 0 and A[j] > v:
   A[j + g] = A[j]
   j -= g
   cnt +=1
  A[j + g] = v

def shellSort(A, n, m, G):
 A1 = A[:]
 global cnt
 cnt = 0
 for i in range(m):
  insertionSort(A1, n, G[i])
 return A1

def Gmake(n):
 G=[]
 k = 1
 while k <= n and len(G) < 100:
  G.append(k)
  k = 3 * k + 1
 G.reverse()
 return G

G = Gmake(n)
A2 = shellSort(A, n, len(G), G)
print(str(len(G)))
print(" ".join(map(str, G)))
print(str(cnt))
for i in A2:
 print(str(i))
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
S = list(map(int, input().split()))
q = int(input())
T = list(map(int, input().split()))
cnt = 0
for i in T:
 a = 0
 b = n-1
 while b >= a:
  mid = (a + b) // 2
  if S[mid] == i:
   cnt += 1
   break
  elif S[mid] > i:
   b = mid
   continue
  else:
   a = mid + 1
   continue
print(str(cnt))

Fixed submission:
n = int(input())
S = list(map(int, input().split()))
q = int(input())
T = list(map(int, input().split()))
cnt = 0
for i in T:
 a = 0
 b = n-1
 while b >= a:
  mid = (a + b) // 2
  if S[mid] == i:
   cnt += 1
   break
  elif S[mid] > i:
   b = mid - 1
   continue
  else:
   a = mid + 1
   continue
print(str(cnt))
Buggy python submission (verdict: Time Limit Exceeded):
n= int(input())
A = list(map(int, input().split()))
q = int(input())
Mi = list(map(int, input().split()))

def solve(i,m):
 if m == 0:
  return True
 if i >= n:
  return False
 res = solve(i+1, m) or solve(i + 1, m - A[i])
 return res

for m in Mi:
 for i in range(n):
  if solve(i, m):
   print("yes")
   break
  if i == n-1 and not(solve(i,m)):
   print("no")

Fixed submission:
n= int(input())
A = list(map(int, input().split()))
q = int(input())
Mi = map(int, input().split())
PS={}
def solve(i,m):
 if m == 0:
  return True
 if (i,m) in PS:
  return PS[(i,m)]
 if i >= n:
  return False
 res = solve(i+1, m) or solve(i + 1, m - A[i])
 PS[(i,m)] = res
 return res

for m in Mi:
 if solve(0, m):
  print("yes")
 else:
  print("no")

Buggy python submission (verdict: Time Limit Exceeded):
n= int(input())
A = list(map(int, input().split()))
q = int(input())
Mi = list(map(int, input().split()))

def solve(i,m):
 if m == 0:
  return True
 if i >= n:
  return False
 res = solve(i+1, m) or solve(i + 1, m - A[i])
 return res

for m in Mi:
 if solve(0, m):
  print("yes")
 else:
  print("no")

Fixed submission:
n= int(input())
A = list(map(int, input().split()))
q = int(input())
Mi = map(int, input().split())
PS={}
def solve(i,m):
 if m == 0:
  return True
 if (i,m) in PS:
  return PS[(i,m)]
 if i >= n:
  return False
 res = solve(i+1, m) or solve(i + 1, m - A[i])
 PS[(i,m)] = res
 return res

for m in Mi:
 if solve(0, m):
  print("yes")
 else:
  print("no")
Buggy python submission (verdict: Time Limit Exceeded):
def merge(A, left, mid, right):
 global x
 n1 = mid - left
 n2 = right - mid
 L = [0] * (n1+1)
 R = [0] * (n2+1)
 for i in range(n1):
  L[i] = A[left + i]
 for i in range(n2):
  R[i] = A[mid + i]
 L[n1] =  float("inf")
 R[n2] =  float("inf")
 i = 0
 j = 0
 for k in range(left,right):
  if L[i] <= R[j]:
   A[k] = L[i]
   x += 1
   i += 1
  else:
   A[k] = R[j]
   x += 1
   j += 1

def mergeSort(A, left, right):
 global x
 if left+1 < right:
  mid = (left + right)//2
  mergeSort(A,left,mid)
  mergeSort(A,mid,right)
  merge(A,left,mid,right)
 return x

n = int(input())
A = list(map(int, input().split()))
x = 0
x = mergeSort(A, 0, n)
print(" ".join(map(str, A)))
print(str(x))

Fixed submission:
def merge(A, left, mid, right):
	global cnt

	L = A[left:mid] + [1000000001]
	R = A[mid:right] + [1000000001]

	i = j = 0
	for k in range(left, right):
		if L[i] <= R[j]:
			A[k] = L[i]
			i += 1
		else:
			A[k] = R[j]
			j += 1
	cnt += right - left

def mergeSort(A, left, right):
	if left + 1 < right:
		mid = (left + right) // 2
		mergeSort(A, left, mid)
		mergeSort(A, mid, right)
		merge(A, left, mid, right)

if __name__ == '__main__':
	n = int(input())
	A = list(map(int, input().split()))
	cnt = 0
	mergeSort(A, 0, n)
	print(*A)
	print(cnt)
Buggy python submission (verdict: Runtime Error):
class Node:
    def __init__(self, num, parent, children):
        self.id = num
        self.parent = -1
        self.depth = 0
        self.type = None
        self.children = children
         
    def show(self):
        print('node {0}: parent = {1}, depth = {2}, {3}, {4}'.format(self.id,self.parent,self.depth,self.type,self.children))
 
 
def set_node(node_data):
    L = list(map(int, node_data.split()))
    num = i_l[0]
    children = i_l[2:]
    node = Node(num, -1, children)
    T[num] = node
    for n in children:
        T[-1] -= n
 
def set_pdt(n_i, parent, depth):
    node = T[n_i]
    node.parent = parent
    node.depth = depth
    if node.children:
        node.type = 'internal node'
        for n in node.children:
            set_pdt(n, n_i, depth + 1)
    else:
        node.type = 'leaf'
 
n = int(input())
 
T = [None] * n
 
T.append(int(n * (n - 1) / 2))
 
for i in range(n):
    x = input()
    set_node(x)
 
set_pdt(T[-1], -1, 0)
 
T[T[-1]].type ='root'
 
for n in T[:-1]:
    n.show()

Fixed submission:
class Node:
    def __init__(self, num, parent, children):
        self.id = num
        self.parent = -1
        self.depth = 0
        self.type = None
        self.children = children
          
    def show(self):
        print('node {0}: parent = {1}, depth = {2}, {3}, {4}'.format(self.id,self.parent,self.depth,self.type,self.children))
  
  
def set_node(node_data):
    L = list(map(int, node_data.split()))
    num = L[0]
    children = L[2:]
    node = Node(num, -1, children)
    T[num] = node
    for n in children:
        T[-1] -= n
  
def set_pdt(n_i, parent, depth):
    node = T[n_i]
    node.parent = parent
    node.depth = depth
    if node.children:
        node.type = 'internal node'
        for n in node.children:
            set_pdt(n, n_i, depth + 1)
    else:
        node.type = 'leaf'
  
n = int(input())
  
T = [None] * n
  
T.append(int(n * (n - 1) / 2))
  
for i in range(n):
    x = input()
    set_node(x)
  
set_pdt(T[-1], -1, 0)
  
T[T[-1]].type ='root'
  
for n in T[:-1]:
    n.show()
Buggy python submission (verdict: Runtime Error):
#Reconstruction of the Tree
n = int(input())
pre = list(map(int,input().split()))
ino = list(map(int,input().split()))

post=[]
i = -1
def recaonstruction(l, r):
    global i
    if l >= r:
        return
    i += 1
    c = pre[i]
    m = ino.index(c)
    reconstruction(l, m)
    reconstruction(m+1, r)
    post.append(c)
reconstruction(0, n)
print(" ".join(map(str,post)))

Fixed submission:
n = int(input())
pre = list(map(int,input().split()))
ino = list(map(int,input().split()))

post=[]
i = -1
def reconstruction(l, r):
    global i
    if l >= r:
        return
    i += 1
    c = pre[i]
    m = ino.index(c)
    reconstruction(l, m)
    reconstruction(m+1, r)
    post.append(c)
reconstruction(0, n)
print(" ".join(map(str,post)))
Buggy python submission (verdict: Time Limit Exceeded):
def maxHeapify(H, A, i):
    left = 2*i
    right = left + 1
 
    if left <= H and A[left] > A[i]:
        largest = left
    else: largest = i
    if right <= H and A[right] > A[largest]:
        largest = right
    if largest != i:
        A[i], A[largest] = A[largest],A[i]
        maxHeapify(H,A,largest)
 
def buildmaxHeap(H,A):
    for i in range(H//2,0,-1):
        maxHeapify(H,A,i)

A = [None]
L = input()
while L !="end":
    L = L.split()
    if L[0] == "insert":
        A.append(int(L[1]))
    else:
        buildmaxHeap(len(A) - 1, A)
        print(str(A[1]))
        A = [None] + A[2:]
    L = input()

Fixed submission:
import heapq
pq = []

def insert(S,k):
    heapq.heappush(pq, - k)

def extractMax(S):
    a = - heapq.heappop(S)
    print(str(a))

L = input()
while L != "end":
    if L =="extract":
        extractMax(pq)
    else:
        L = L.split()
        insert(pq, int(L[1]))
    L = input()

Buggy python submission (verdict: Time Limit Exceeded):
def maxHeapify(H, A, i):
    left = 2*i
    right = left + 1
 
    if left <= H and A[left] > A[i]:
        largest = left
    else: largest = i
    if right <= H and A[right] > A[largest]:
        largest = right
    if largest != i:
        A[i], A[largest] = A[largest],A[i]
        maxHeapify(H,A,largest)
 
def buildmaxHeap(H,A):
    for i in range(H//2,0,-1):
        maxHeapify(H,A,i)

A = [None]
L = input()
while L !="end":
    L = L.split()
    if L[0] == "insert":
        A.append(int(L[1]))
        buildmaxHeap(len(A) - 1, A)
    else:
        print(str(A[1]))
        A = [None] + A[2:]
        buildmaxHeap(len(A) - 1, A)
    L = input()

Fixed submission:
import heapq
pq = []

def insert(S,k):
    heapq.heappush(pq, - k)

def extractMax(S):
    a = - heapq.heappop(S)
    print(str(a))

L = input()
while L != "end":
    if L =="extract":
        extractMax(pq)
    else:
        L = L.split()
        insert(pq, int(L[1]))
    L = input()

Buggy python submission (verdict: Time Limit Exceeded):
def maxHeapify(H, A, i):
    left = 2*i
    right = left + 1
  
    if left <= H and A[left] > A[i]:
        largest = left
    else: largest = i
    if right <= H and A[right] > A[largest]:
        largest = right
    if largest != i:
        A[i], A[largest] = A[largest],A[i]
        maxHeapify(H,A,largest)
  
def buildmaxHeap(H,A):
    for i in range(H//2,0,-1):
        maxHeapify(H,A,i)
 
A = [None]
import sys
for x in sys.stdin.readlines():
    if x[0] == 'i':
        A.append(int(x[7:]))
    elif x[1] == 'x':
        buildmaxHeap(len(A) - 1, A)
        print(str(A[1]))
        A = [None] + A[2:]
    else:
        pass

Fixed submission:
import heapq
pq = []

def insert(S,k):
    heapq.heappush(pq, - k)

def extractMax(S):
    a = - heapq.heappop(S)
    print(str(a))

L = input()
while L != "end":
    if L =="extract":
        extractMax(pq)
    else:
        L = L.split()
        insert(pq, int(L[1]))
    L = input()
Buggy python submission (verdict: Time Limit Exceeded):
from bisect import bisect
n = int(input())
A = []
for i in range(n):
 A.append(int(input()))
 
 L = [None for i in range(n)]
def LIS():
    L[0] = A[0]
    length = 0
    for i in range(n):
        if L[length] < A[i]:
            length += 1
            L[length] = A[i]
        else:
            if A[i] in L: continue
            j = bisect(L, A[i], 0, length)
            L[j] = A[i]
    return length + 1

print(LIS())

Fixed submission:
from bisect import bisect_left
import sys

n = int(input())
A = [int(i.rstrip("\n")) for i in sys.stdin.readlines()]

def LIS():
    L = A[:1]
    for i in A[1:]:
        if L[-1] < i:
            L.append(i)
        else:
            j = bisect_left(L, i)
            L[j] = i
    return len(L)

print(LIS())

Buggy python submission (verdict: Runtime Error):
from bisect import bisect_left
import sys
n = int(input())
A = [int(i.rstrip("\n")) for i in sys.stdin.readlines()]

def LIS():
    L = A[:1]
    for i in A[1:]:
        if L[-1] < i:
            L.append(i)
        else:
            L[j] = i
    return len(L)

print(LIS())

Fixed submission:
from bisect import bisect_left
import sys

n = int(input())
A = [int(i.rstrip("\n")) for i in sys.stdin.readlines()]

def LIS():
    L = A[:1]
    for i in A[1:]:
        if L[-1] < i:
            L.append(i)
        else:
            j = bisect_left(L, i)
            L[j] = i
    return len(L)

print(LIS())
Buggy python submission (verdict: Runtime Error):
import sys
H,W = map(int, input().split())
C = [list(map(int,i.split())) for i in sys.stdin.readlines()]
G =[[None for i in range(W)] for j in range(H)]

for i in range(W):
  if C[0][i] == 0:
      G[0][i] = 1
  else: G[0][i] = 0
for i in range(H):
  if C[i][0] == 0:
      G[i][0] = 1
  else: G[i][0] = 0

ans = []
for i in range(1,H):
    for j in range(1,W):
        if C[i][j] == 0:
            G[i][j] = min(G[i-1][j], G[i][j-1],G[i-1][j-1]) + 1
            ans.append(G[i][j])
        else:G[i][j] = 0

ans = max(ans) ** 2
print(str(ans))

Fixed submission:
import sys
H,W = map(int, input().split())
C = [list(map(int,i.split())) for i in sys.stdin.readlines()]
G =[[None for i in range(W)] for j in range(H)]

for i in range(W):
  if C[0][i] == 0:
      G[0][i] = 1
  else: G[0][i] = 0
for i in range(H):
  if C[i][0] == 0:
      G[i][0] = 1
  else: G[i][0] = 0


for i in range(1,H):
    for j in range(1,W):
        if C[i][j] == 0:
            G[i][j] = min(G[i-1][j], G[i][j-1],G[i-1][j-1]) + 1
        else:G[i][j] = 0

ans = max(max(i) for i in G) ** 2
print(str(ans))

Buggy python submission (verdict: Runtime Error):
import sys
H,W = map(int, input().split())
C = [list(map(int,i.split())) for i in sys.stdin.readlines()]
G =[[None for i in range(W)] for j in range(H)]

ans = []
for i in range(W):
  if C[0][i] == 0:
      G[0][i] = 1
      ans.append(1)
  else: G[0][i] = 0
for i in range(H):
  if C[i][0] == 0:
      G[i][0] = 1
      ans.append(1)
  else: G[i][0] = 0


for i in range(1,H):
    for j in range(1,W):
        if C[i][j] == 0:
            G[i][j] = min(G[i-1][j], G[i][j-1],G[i-1][j-1]) + 1
            ans.append(G[i][j])
        else:G[i][j] = 0

ans = max(ans) ** 2
print(str(ans))

Fixed submission:
import sys
H,W = map(int, input().split())
C = [list(map(int,i.split())) for i in sys.stdin.readlines()]
G =[[None for i in range(W)] for j in range(H)]

for i in range(W):
  if C[0][i] == 0:
      G[0][i] = 1
  else: G[0][i] = 0
for i in range(H):
  if C[i][0] == 0:
      G[i][0] = 1
  else: G[i][0] = 0


for i in range(1,H):
    for j in range(1,W):
        if C[i][j] == 0:
            G[i][j] = min(G[i-1][j], G[i][j-1],G[i-1][j-1]) + 1
        else:G[i][j] = 0

ans = max(max(i) for i in G) ** 2
print(str(ans))
Buggy python submission (verdict: Runtime Error):
import math, sys

#??°????????????????????§????¨????????????¨???????????°??????????????????????§????
class SegmentTree():
    def __init__(self, n):
        self.TreeRange = pow(2, math.ceil(math.log2(n)))
        self.List = [0] * (2 * self.TreeRange - 1)

    def add(self, i, x):
        i += self.TreeRange - 1
        self.List[i] += x
        while i > 0:
            i = (i - 1) // 2
            self.List[i] += x

    def getsum(self, s, t, i=0, left=0, right=float("inf")):
        #??¢?´¢????±?????????????????????§????????°0????????????
        if right <= s or t <= left:
            return 0
        #??¢?´¢????±?????????????????????§????????°??????????????????????????????
        elif s <= left <= right <= t:
            return self.List[i]
        #??¢?´¢????±????????????????????????????????????°????????????????????°
        else:
            l = self.getsum(s, t, i * 2 + 1, left, (left + right) // 2)
            r = self.getsum(s, t, i * 2 + 2, (left + right) // 2, right)
            return l + r

_input = sys.stdin.readlines()
n,q = map(int, _input[0].split())
qlist = map(lambda x:x.split(), _input[1:])
ST = SegmentTree(n)

for q in qlist:
    cmd, x, y = map(int, q)
    if cmd == 0:
        ST.add(x, y)
    elif cmd == 1:
        print(ST.getsum(x,y + 1, right = ST.TreeRange))

Fixed submission:
import math, sys

#??°????????????????????§????°????????????¨???????????°??????????????????????§????
class SegmentTree():
    def __init__(self, n):
        self.TreeRange = pow(2, math.ceil(math.log2(n)))
        self.List = [0] * (2 * self.TreeRange - 1)

    def add(self, i, x):
        i += self.TreeRange - 1
        self.List[i] += x
        while i > 0:
            i = (i - 1) // 2
            self.List[i] += x

    def getsum(self, s, t, i=0, left=0, right=float("inf")):
        #??¢?´¢????±?????????????????????§????????°0????????????
        if right <= s or t <= left:
            return 0
        #??¢?´¢????±?????????????????????§????????°??????????????????????????????
        elif s <= left <= right <= t:
            return self.List[i]
        #??¢?´¢????±????????????????????????????????????°????????????????????°
        else:
            l = self.getsum(s, t, i * 2 + 1, left, (left + right) // 2)
            r = self.getsum(s, t, i * 2 + 2, (left + right) // 2, right)
            return l + r

_input = sys.stdin.readlines()
n,q = map(int, _input[0].split())
qlist = map(lambda x:x.split(), _input[1:])
ST = SegmentTree(n)

for q in qlist:
    cmd, x, y = map(int, q)
    if cmd == 0:
        ST.add(x - 1, y)
    elif cmd == 1:
        print(ST.getsum(x - 1,y , right = ST.TreeRange))
Buggy python submission (verdict: Time Limit Exceeded):
n,E = map(int, input().split())
M = [[] for i in range(n)]
for i in range(E):
 s,t,w = map(int, input().split())
 M[s].append([t,w])
 M[t].append([s,w])

def prim():
 color = [0] * n
 d = [float("inf")] * n
 d[0] = 0
 
 while True:
  minv = float("inf")
  u = -1
  for i in range(n):
   if minv > d[i] and color[i] != 2:
    u = i
    minv = d[i]
  if u == -1: break
  color[u] = 2
  for v1, v2 in M[u]:
   if color[v1] != 2:
    if d[v1] > v2:
     d[v1] = v2
 return sum(d)
 
print(prim())

Fixed submission:
import heapq as pq
n,E = map(int, input().split())
M = [[] for i in range(n)]
for i in range(E):
 s,t,w = map(int, input().split())
 M[s].append([t,w])
 M[t].append([s,w])

def prim():
 color = [0] * n
 d = [float("inf")] * n
 d[0] = 0
 H = []
 pq.heappush(H, [0, 0])
 while H:
  u2,u1 = pq.heappop(H)
  color[u1] = 1
  if d[u1] < u2: continue
  for v1, v2 in M[u1]:
   if color[v1] == 1: continue
   if d[v1] > v2:
    d[v1] = v2
    pq.heappush(H, [d[v1], v1])
 return sum(d)
 
print(prim())