Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
mod=10**9+7
inv2=5*10**8+4
B,W=map(int,input().split())
 
Factorial=[1]*(B+W+1)
for i in range(1,B+W+1):
  Factorial[i]=Factorial[i-1]*(i)%mod
def power(x,y):
  if y==0:
    return 1
  elif y==1:
    return x%mod
  elif y%2==0:
    return power(x,y//2)**2%mod
  else:
    return (power(x,y//2)**2)*x%mod
 
inverseFactorial=[1]*(B+W+1)
inverseFactorial[B+W]=power(Factorial[B+W],mod-2)
for i in range(0,B+W)[::-1]:
  inverseFactorial[i]=(inverseFactorial[i+1]*(i+1))%mod
  
def comb(x,y):
  if x<y or y<0:
    return 0
  else:
    return (Factorial[x]*inverseFactorial[y]*inverseFactorial[x-y])%mod
w,b=[0]*(B+W+1),[0]*(B+W+1)
for i in range(1,B+W+1):
  w[i]=(w[i-1]+comb(i-1,W-1)*power(2,B+W-i))%mod
  b[i]=(b[i-1]+comb(i-1,B-1)*power(2,B+W-i))%mod
ans=[0]*(B+W+1)
#print(w)
#print(b)
for i in range(1,B+W+1):
  ans[i]=(power(2,B+W)+w[i-1]-b[i-1])*power(inv2,B+W+1)
  print(ans[i]%mod)

Fixed submission:
mod=10**9+7
inv2=5*(10**8)+4
B,W=map(int,input().split())
 
Factorial=[1]*(B+W+1)
for i in range(1,B+W+1):
  Factorial[i]=Factorial[i-1]*(i)%mod
def power(x,y):
  if y==0:
    return 1
  elif y==1:
    return x%mod
  elif y%2==0:
    return power(x,y//2)**2%mod
  else:
    return (power(x,y//2)**2)*x%mod
 
inverseFactorial=[1]*(B+W+1)
inverseFactorial[B+W]=power(Factorial[B+W],mod-2)
for i in range(0,B+W)[::-1]:
  inverseFactorial[i]=(inverseFactorial[i+1]*(i+1))%mod
  
def comb(x,y):
  if x<y or y<0:
    return 0
  else:
    return (Factorial[x]*inverseFactorial[y]*inverseFactorial[x-y])%mod
w,b=[0]*(B+W+1),[0]*(B+W+1)
p2=[1]*(B+W+1)
for i in range(1,B+W+1):
  p2[i]=(p2[i-1]*2)%mod
bunbo=power(inv2,B+W+1)  

for i in range(1,B+W+1):
  w[i]=(w[i-1]+comb(i-1,W-1)*p2[B+W-i])%mod
  b[i]=(b[i-1]+comb(i-1,B-1)*p2[B+W-i])%mod
ans=[0]*(B+W+1)
#print(w)
#print(b)
for i in range(1,B+W+1):
  ans[i]=(p2[B+W]+w[i-1]-b[i-1])*bunbo
  print(ans[i]%mod)
Buggy python submission (verdict: Runtime Error):
N,M=map(int,input().split())
A=[int(i) for i in input().split()]
Match=[0,2,5,5,4,5,6,3,7,6]
A.sort(reverse=True)
dp=[0]*(N+1)
dp[0]=1
for i in range(1,N+1):
  for a in A:
    if i>=Match[a]:
      dp[i]|=dp[i-Match[a]]<<1

for k in range(N)[::-1]:
  if dp[N]&(1<<k):
    S=k
    break
ans=[]
m=0
for k in range(S):
  if dp[N-Match[A[m]]]&(1<<(S-k-1)) and N-Match[A[m]]>=0:
    ans.append(str(A[m]))
    N-=Match[A[m]]
  else:
    for l in range(m+1,len(A)):
      if dp[N-Match[A[l]]]&(1<<(S-k-1)) and N-Match[A[l]]>=0:
        m=l
        ans.append(str(A[m]))
        N-=Match[A[m]]
        break
print("".join(ans))


Fixed submission:
N,M=map(int,input().split())
A=[int(i) for i in input().split()]
Match=[0,2,5,5,4,5,6,3,7,6]
A.sort(reverse=True)
dp=[0]*(N+1)
dp[0]=1
for i in range(1,N+1):
  for a in A:
    if i>=Match[a]:
      dp[i]|=dp[i-Match[a]]<<1

for k in range(N)[::-1]:
  if dp[N]&(1<<k):
    S=k
    break
ans=[]
m=0
for k in range(S):
  if N-Match[A[m]]>=0:
    if dp[N-Match[A[m]]]&(1<<(S-k-1)):
      ans.append(str(A[m]))
      N-=Match[A[m]]
    else:
      for l in range(m+1,len(A)):
        if N-Match[A[l]]>=0:
          if dp[N-Match[A[l]]]&(1<<(S-k-1)):
            m=l
            ans.append(str(A[m]))
            N-=Match[A[m]]
            break
  else:
    for l in range(m+1,len(A)):
      if N-Match[A[l]]>=0:
        if dp[N-Match[A[l]]]&(1<<(S-k-1)):
          m=l
          ans.append(str(A[m]))
          N-=Match[A[m]]
          break
print("".join(ans))

Buggy python submission (verdict: Runtime Error):
N,M=map(int,input().split())
A=[int(i) for i in input().split()]
Match=[0,2,5,5,4,5,6,3,7,6]
A.sort(reverse=True)
dp=[0]*(N+1)
dp[0]=1
for i in range(1,N+1):
  for a in A:
    if i>=Match[a]:
      dp[i]|=dp[i-Match[a]]<<1

for k in range(N)[::-1]:
  if dp[N]&(1<<k):
    S=k
    break
ans=[]
m=0
for k in range(S):
  if dp[N-Match[A[m]]]&(1<<(S-k-1)):
    ans.append(str(A[m]))
    N-=Match[A[m]]
  else:
    for l in range(m+1,len(A)):
      if dp[N-Match[A[l]]]&(1<<(S-k-1)):
        m=l
        ans.append(str(A[m]))
        N-=Match[A[m]]
        break
print("".join(ans))


Fixed submission:
N,M=map(int,input().split())
A=[int(i) for i in input().split()]
Match=[0,2,5,5,4,5,6,3,7,6]
A.sort(reverse=True)
dp=[0]*(N+1)
dp[0]=1
for i in range(1,N+1):
  for a in A:
    if i>=Match[a]:
      dp[i]|=dp[i-Match[a]]<<1

for k in range(N)[::-1]:
  if dp[N]&(1<<k):
    S=k
    break
ans=[]
m=0
for k in range(S):
  if N-Match[A[m]]>=0:
    if dp[N-Match[A[m]]]&(1<<(S-k-1)):
      ans.append(str(A[m]))
      N-=Match[A[m]]
    else:
      for l in range(m+1,len(A)):
        if N-Match[A[l]]>=0:
          if dp[N-Match[A[l]]]&(1<<(S-k-1)):
            m=l
            ans.append(str(A[m]))
            N-=Match[A[m]]
            break
  else:
    for l in range(m+1,len(A)):
      if N-Match[A[l]]>=0:
        if dp[N-Match[A[l]]]&(1<<(S-k-1)):
          m=l
          ans.append(str(A[m]))
          N-=Match[A[m]]
          break
print("".join(ans))
Buggy python submission (verdict: Runtime Error):
N,M=map(int,input().split())
G1=[[] for i in range(N)]
G2=[[] for i in range(N)]
not_root=[False]*N
for i in range(N+M-1):
  a,b=map(int,input().split())
  G1[a-1].append(b-1)
  G2[b-1].append(a-1)
  not_root[b-1]=True
for i in range(N):
  if not not_root[i]:
    root=i
    break
Tree=[-2]*N
Tree[root]=-1
def dfs(x):
  for b in G1[x]:
    if Tree[b]>=-1:
      continue
    flag=0
    for a in G2[b]:
      if Tree[a]<-1:
        flag=1
        break
    if flag==0:
      Tree[b]=x
      dfs(b)
dfs(root)
for i in range(N):
  print(Tree[i]+1)
  

Fixed submission:
import sys
sys.setrecursionlimit(10**8)
N,M=map(int,input().split())
G1=[[] for i in range(N)]
G2=[[] for i in range(N)]
not_root=[False]*N
for i in range(N+M-1):
  a,b=map(int,input().split())
  G1[a-1].append(b-1)
  G2[b-1].append(a-1)
  not_root[b-1]=True
for i in range(N):
  if not not_root[i]:
    root=i
    break
Tree=[-2]*N
Tree[root]=-1
def dfs(x):
  for b in G1[x]:
    if Tree[b]>=-1:
      continue
    flag=0
    for a in G2[b]:
      if Tree[a]<-1:
        flag=1
        break
    if flag==0:
      Tree[b]=x
      dfs(b)
dfs(root)
for i in range(N):
  print(Tree[i]+1)
Buggy python submission (verdict: Runtime Error):
H,W,N=map(int,input().split())
ans=W
Y=[0]*W
ob=[float("inf")]*W
for i in range(N):
  x,y=map(int,input().split())
  ob[x-1]=min(ob[x-1],y-1)
for i in range(1,W):
  if ob[i]==Y[i-1]+1:
    Y[i]=Y[i-1]
  else:
    Y[i]=Y[i-1]+1
for i in range(1,W):
  if ob[i]<=Y[i]:
    ans=min(ans,i)
print(ans)


Fixed submission:
H,W,N=map(int,input().split())
ans=H
Y=[0]*H
ob=[float("inf")]*H
for i in range(N):
  x,y=map(int,input().split())
  ob[x-1]=min(ob[x-1],y-1)
for i in range(1,H):
  if ob[i]==Y[i-1]+1:
    Y[i]=Y[i-1]
  else:
    Y[i]=Y[i-1]+1
for i in range(1,H):
  if ob[i]<=Y[i]:
    ans=min(ans,i)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
import sys
input=sys.stdin.readline
S=input()
D_stack=[]
D,C=[-1]*(N+1),[-1]*(N+1)
m=0
for i in range(N):
  if S[i]=="D":
    D_stack.append((i,m))
    D[i]=m
  if S[i]=="C":
    C[i]=m
  if S[i]=="M":
    m+=1
Q=int(input())
K=[int(i) for i in input().split()]
for q in range(Q):
  ans=0
  k=K[q]
  r,c,s,pre_m=0,1,0,0
  for p,m in D_stack:
    if r<=p:
      r=p+1
      c,s=1,0
    else:
      s-=(c-1)*(m-pre_m)
      c-=1
    pre_m=m
    while r-p<k and r<=N:
      if C[r]>=0:
        ans+=c*(C[r]-m)-s
      if D[r]>=0:
        c+=1
        s+=D[r]-m
      r+=1
  print(ans)


Fixed submission:
N=int(input())
import sys
input=sys.stdin.readline
S=input()
C_stack=[]
D=[0]*(N+1)
M=[0]*(N+1)
DM=[0]*(N+1)
m=0
for i in range(1,N+1):
  if S[i-1]=="D":
    D[i]=D[i-1]+1
  else:
    D[i]=D[i-1]
  if S[i-1]=="C":
    C_stack.append(i)
  if S[i-1]=="M":
    DM[i]=DM[i-1]+D[i-1]
    M[i]=M[i-1]+1
  else:
    DM[i]=DM[i-1]
    M[i]=M[i-1]

Q=int(input())
K=[int(i) for i in input().split()]
for q in range(Q):
  ans=0
  k=K[q]
  for c in C_stack:
    ans+=DM[c]-DM[max(0,c-k)]-D[max(0,c-k)]*(M[c]-M[max(0,c-k)])
  print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
S=input()
D_stack=[]
D,C=[-1]*(N+1),[-1]*(N+1)
m=0
for i in range(N):
  if S[i]=="D":
    D_stack.append((i,m))
    D[i]=m
  if S[i]=="C":
    C[i]=m
  if S[i]=="M":
    m+=1
Q=int(input())
K=[int(i) for i in input().split()]
for q in range(Q):
  ans=0
  k=K[q]
  l,r,c,s,pre_m=0,0,1,0,0
  for p,m in D_stack:
    if r<=p:
      r=p+1
      c,s=1,0
    else:
      s-=(c-1)*(m-pre_m)
      c-=1
    pre_m=m
    while r-p<k and r<=N:
      if C[r]>=0:
        ans+=c*(C[r]-m)-s
      if D[r]>=0:
        c+=1
        s+=D[r]-m
      r+=1
  print(ans)


Fixed submission:
N=int(input())
import sys
input=sys.stdin.readline
S=input()
C_stack=[]
D=[0]*(N+1)
M=[0]*(N+1)
DM=[0]*(N+1)
m=0
for i in range(1,N+1):
  if S[i-1]=="D":
    D[i]=D[i-1]+1
  else:
    D[i]=D[i-1]
  if S[i-1]=="C":
    C_stack.append(i)
  if S[i-1]=="M":
    DM[i]=DM[i-1]+D[i-1]
    M[i]=M[i-1]+1
  else:
    DM[i]=DM[i-1]
    M[i]=M[i-1]

Q=int(input())
K=[int(i) for i in input().split()]
for q in range(Q):
  ans=0
  k=K[q]
  for c in C_stack:
    ans+=DM[c]-DM[max(0,c-k)]-D[max(0,c-k)]*(M[c]-M[max(0,c-k)])
  print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
X,Y=map(int,input().split())
print(X+Y//2-1)
for i in range(20**7):
  i+=1


Fixed submission:
X,Y=map(int,input().split())
print(X+Y//2)

Buggy python submission (verdict: Time Limit Exceeded):
X,Y=map(int,input().split())
print(X+Y//2)
for i in range(20**7):
  i+=1



Fixed submission:
X,Y=map(int,input().split())
print(X+Y//2)

Buggy python submission (verdict: Runtime Error):
X,Y=map(int,input())
print(X+Y//2)
for i in range(20**7):
  pass



Fixed submission:
X,Y=map(int,input().split())
print(X+Y//2)

Buggy python submission (verdict: Runtime Error):
X,Y=map(int,input())
print(X+Y//2)


Fixed submission:
X,Y=map(int,input().split())
print(X+Y//2)
Buggy python submission (verdict: Time Limit Exceeded):
N,M=map(int,input().split())
S=input()
T=input()
list_S=list(S)
list_T=list(T)
Number_i=[i for i in range(N)]
Number_j=[j for j in range(M)]
Kaburi_i=[]
Kaburi_j=[]
counter=0
Flag=0
for i in Number_i:
  if i*M/N in Number_j:
    Kaburi_i.append(i)
    Kaburi_j.append(int(i*M/N))
Kaburi_Size=len(Kaburi_i)
while counter<=Kaburi_Size-1:
  if list_S[Kaburi_i[counter]]==list_T[Kaburi_j[counter]]:
    pass
  else:
    Flag=1
    break
  counter+=1
def gcd(a,b):
  while b>0:
    a,b=b,a%b
  return a
if Flag==1:
  print(-1)
else:
  print(int(N*M/gcd(N,M)))
  
  
  





Fixed submission:
N,M=map(int,input().split())
S=input()
T=input()
list_S=list(S)
list_T=list(T)
Number_i=[i for i in range(N)]
Number_iMN=[]
for i in Number_i:
  Number_iMN.append(i*M/N)
Number_j=[j for j in range(M)]
Kaburi_j=list(set(Number_iMN)&set(Number_j))
Kaburi_i=[]
for j in Kaburi_j:
  Kaburi_i.append(int(j*N/M))
counter=0
Flag=0
Kaburi_Size=len(Kaburi_i)
while counter<=Kaburi_Size-1:
  if list_S[int(Kaburi_i[counter])]==list_T[int(Kaburi_j[counter])]:
    pass
  else:
    Flag=1
    break
  counter+=1
def gcd(a,b):
  while b>0:
    a,b=b,a%b
  return a
if Flag==1:
  print(-1)
else:
  print(int(N*M/gcd(N,M)))
Buggy python submission (verdict: Runtime Error):
N=int(input())
a=int(input())
b=int(input())
if N==1:
  print("Hello World")
else:
  print(A+B)

Fixed submission:
N=int(input())
if N==1:
  print("Hello World")
  exit()
a=int(input())
b=int(input())
print(a+b)
Buggy python submission (verdict: Runtime Error):
A,B=map(int,input())
if (A*B)%2==0:
  print("No")
else:
  print("Yes")

Fixed submission:
A,B=map(int,input().split())
if (A*B)%2==0:
  print("No")
else:
  print("Yes")
Buggy python submission (verdict: Runtime Error):
H,W=map(int,input().split())
Map=[[int(i) for i in input().split()] for i in range(H)]
Tell=[]
for y in range(H): 
  for x in range(W):
    if Map[y][x]%2==1:
      if x==W-1:
        Map[y][x]=1
      elif Map[y][x+1]%2==0:
        Map[y][x]=0
        Map[y][x+1]=1
        Tell.append(str(y+1)+" "+str(x+1)+" "+str(y+1)+" "+str(x+2))
      else:
        Map[y][x]=0
        Map[y][x+1]=0
        Tell.append(str(y+1)+" "+str(x+1)+" "+str(y+1)+" "+str(x+2))
for y in range(H):
  if Map[y][W-1]==1:
    if y==H-1:
      pass
    if Map[y+1][W-1]==0:
      Map[y][W-1]=0
      Map[y+1][W-1]=1
      Tell.append(str(y+1)+" "+str(x+1)+" "+str(y+2)+" "+str(x+1))
    if Map[y+1][W-1]==1:
      Map[y][W-1]=0
      Map[y+1][W-1]=0
      Tell.append(str(y+1)+" "+str(x+1)+" "+str(y+2)+" "+str(x+1))
print(len(Tell))
for t in Tell:
  print(t)
   
      
     
    
     

Fixed submission:
H,W=map(int,input().split())
Map=[[int(i) for i in input().split()] for i in range(H)]
Tell=[]
for y in range(H): 
  for x in range(W):
    if Map[y][x]%2==1:
      if x==W-1:
        Map[y][x]=1
      elif Map[y][x+1]%2==0:
        Map[y][x]=0
        Map[y][x+1]=1
        Tell.append(str(y+1)+" "+str(x+1)+" "+str(y+1)+" "+str(x+2))
      else:
        Map[y][x]=0
        Map[y][x+1]=0
        Tell.append(str(y+1)+" "+str(x+1)+" "+str(y+1)+" "+str(x+2))
    else:
      Map[y][x]=0
for y in range(H):
  if Map[y][W-1]==1:
    if y==H-1:
      pass
    elif Map[y+1][W-1]==0:
      Map[y][W-1]=0
      Map[y+1][W-1]=1
      Tell.append(str(y+1)+" "+str(x+1)+" "+str(y+2)+" "+str(x+1))
    elif Map[y+1][W-1]==1:
      Map[y][W-1]=0
      Map[y+1][W-1]=0
      Tell.append(str(y+1)+" "+str(x+1)+" "+str(y+2)+" "+str(x+1))
print(len(Tell))
for t in Tell:
  print(t)
Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
A=[int(i) for i in input().split()]
sorted_A=sorted(A)

def add(B,a,n):
    x = a
    while x<=n:
        B[x]+=1
        x+=x&(-x)
        
def sums(B,a):
    x=a
    S=0
    while x!=0:
        S+=B[x]
        x-=x&(-x)
    return S
  
def invnumber(n,A):
  S=[0]*n
  A=sorted([(A[i],i) for i in range(n)])
  for i in range(1,n):
     S[A[i][1]]=i
  B=[0]*(n*2+1)
  invs=0
  for i in range(n):
      s=S[i]+n
      invs+=sums(B,s)
      add(B,s,n*2)
  return n*(n-1)//2-invs
  
def Check(x):
  S=[0]
  for i in range(N):
    if A[i]>sorted_A[x]:
      S.append(S[-1]+1)
    else:
      S.append(S[-1]-1)
  return invnumber(N+1,S)
      
l,r=0,N-1
while l<r:
  m=(l+r)//2
  if Check(m)>(N*(N+1)//4):
    r=m
  else:
    l=m+1
print(sorted_A[l])


Fixed submission:
N=int(input())
A=[int(i) for i in input().split()]
sorted_A=sorted(A)

def add(B,a,n):
    x = a
    while x<=n:
        B[x]+=1
        x+=x&(-x)
        
def sums(B,a):
    x=a
    S=0
    while x!=0:
        S+=B[x]
        x-=x&(-x)
    return S
  
  
  
def invnumber(n,A):
  B=[0]*(n*2+1)
  invs=0
  for i in range(n):
      s=A[i]+n
      invs+=sums(B,s)
      add(B,s,n*2)
  return n*(n-1)//2-invs
  
def Check(x):
  S=[0]
  for i in range(N):
    if A[i]>sorted_A[x]:
      S.append(S[-1]+1)
    else:
      S.append(S[-1]-1)
  return invnumber(N+1,S)
      
l,r=0,N-1
while l<r:
  m=(l+r)//2
  if Check(m)>N*(N+1)//4:
    r=m
  else:
    l=m+1
print(sorted_A[l])
Buggy python submission (verdict: Runtime Error):
N=int(input())
a=[int(i) for i in input().split()]
ans=0
flag=0
for i in range(1,N):
  if flag==0 and a[i]==a[i-1]:
    ans+=1
    a[i]=a[i+1]+1
print(ans)

Fixed submission:
N=int(input())
a=[int(i) for i in input().split()]
a.append(1)
ans=0
for i in range(1,N):
  if a[i]==a[i-1]:
    ans+=1
    a[i]=a[i+1]+1
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
S=input()
Sf=S[:N]
Sb=S[N:2*N]
Sb=Sb[::-1]
ans=0
for i in range(2**N):
  R=[]
  B=[]
  for k in range(N):
    if i&(1<<k):
      R.append(Sf[k])
    else:
      B.append(Sf[k])
  dp=[[0]*(N+1) for i in range(N+1)]
  dp[0][0]=1
  f=True
  for k in range(1,N+1):
    for j in range(N):
      if j<len(R):
        if Sb[k-1]==R[j]:
          dp[k][j+1]+=dp[k-1][j]
      if 0<=k-j-1<len(B):
        if Sb[k-1]==B[k-j-1]:
          dp[k][j]+=dp[k-1][j]
  ans+=sum(dp[N])
print(ans)
   
      
    

Fixed submission:
N=int(input())
S=input()
Sf=S[:N]
Sb=S[N:2*N]
Sb=Sb[::-1]
ans=0
for i in range(2**N):
  R=[]
  B=[]
  for k in range(N):
    if i&(1<<k):
      R.append(Sf[k])
    else:
      B.append(Sf[k])
  dp=[[0]*(N+1) for i in range(N+1)]
  dp[0][0]=1
  f=True
  for k in range(1,N+1):
    for j in range(k):
      if j<len(R):
        if Sb[k-1]==R[j]:
          dp[k][j+1]+=dp[k-1][j]
      if 0<=k-j-1<len(B):
        if Sb[k-1]==B[k-j-1]:
          dp[k][j]+=dp[k-1][j]
  ans+=sum(dp[N])
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
A=[int(i) for i in input().split()]
C=[]
l=0
C.append(([(0,-1),(A[0],0)]))
for i in range(1,2**N):
  s=set()
  s.add((A[i],i))
  for k in range(l+1):
    if i&(1<<k):
      a,b=C[i^(1<<k)]
      s.add(a)
      s.add(b)
  s=sorted(list(s))
  C.append([s[-2],s[-1]])
  if i==2**(l+1)-1:
    l+=1
ans=[0]
for i in range(1,2**N):
  a,b=C[i]
  ans.append(max(ans[-1],a[0]+b[0]))
  print(ans[-1])

Fixed submission:
N=int(input())
A=[int(i) for i in input().split()]
C=[]
l=0
C.append(([(0,-1),(A[0],0)]))
for i in range(1,2**N):
  biggest,second=(A[i],i),(0,-1)
  for k in range(l+1):
    if i&(1<<k):
      for a in C[i^(1<<k)]:
        if a[0]>biggest[0]:
          second=biggest
          biggest=a
        elif a[0]>second[0] and biggest!=a:
          second=a
  C.append([second,biggest])
  if i==2**(l+1)-1:
    l+=1
ans=[0]
for i in range(1,2**N):
  a,b=C[i]
  ans.append(max(ans[-1],a[0]+b[0]))
  print(ans[-1])
Buggy python submission (verdict: Time Limit Exceeded):
N,M=map(int,input().split())
dp_ppp=[-1000000]*(N+1)
dp_mpp=[-1000000]*(N+1)
dp_pmp=[-1000000]*(N+1)
dp_ppm=[-1000000]*(N+1)
dp_mmp=[-1000000]*(N+1)
dp_mpm=[-1000000]*(N+1)
dp_pmm=[-1000000]*(N+1)
dp_mmm=[-1000000]*(N+1)
dp_ppp[0]=0
dp_mpp[0]=0
dp_pmp[0]=0
dp_ppm[0]=0
dp_mmp[0]=0
dp_mpm[0]=0
dp_pmm[0]=0
dp_mmm[0]=0
for i in range(N):
  x,y,z=map(int,input().split())
  for j in range(min(i+1,M),0,-1):
    if dp_ppp[j-1]>=0:
      dp_ppp[j]=max([dp_ppp[j],dp_ppp[j-1]+x+y+z])
    if dp_mpp[j-1]>=0:
      dp_mpp[j]=max([dp_mpp[j],dp_mpp[j-1]-x+y+z])
    if dp_pmp[j-1]>=0:
      dp_pmp[j]=max([dp_pmp[j],dp_pmp[j-1]+x-y+z])
    if dp_ppm[j-1]>=0:
      dp_ppm[j]=max([dp_ppm[j],dp_ppm[j-1]+x+y-z])
    if dp_mmp[j-1]>=0:
      dp_mmp[j]=max([dp_mmp[j],dp_mmp[j-1]-x-y+z])
    if dp_mpm[j-1]>=0:
      dp_mpm[j]=max([dp_mpm[j],dp_mpm[j-1]-x+y-z])
    if dp_pmm[j-1]>=0:
      dp_pmm[j]=max([dp_pmm[j],dp_pmm[j-1]+x-y-z])
    if dp_mmm[j-1]>=0:
      dp_mmm[j]=max([dp_mmm[j],dp_mmm[j-1]-x-y-z])

ans=max([dp_ppp[M],dp_mpp[M],dp_pmp[M],dp_ppm[M],dp_mmp[M],dp_mpm[M],dp_pmm[M],dp_mmm[M]])
if ans>0:
  print(ans)
else:
  print(0)

Fixed submission:
import sys
input=sys.stdin.readline
N,M=map(int,input().split())
dp_ppp=[]
dp_mpp=[]
dp_pmp=[]
dp_ppm=[]
dp_mmp=[]
dp_mpm=[]
dp_pmm=[]
dp_mmm=[]
for i in range(N):
  x,y,z=map(int,input().split())
  dp_ppp.append(x+y+z)
  dp_mpp.append(-x+y+z)
  dp_pmp.append(x-y+z)
  dp_ppm.append(x+y-z)
  dp_mmp.append(-x-y+z)
  dp_mpm.append(-x+y-z)
  dp_pmm.append(x-y-z)
  dp_mmm.append(-x-y-z)
dp_ppp.sort(key=lambda x:-x)
dp_mpp.sort(key=lambda x:-x)
dp_pmp.sort(key=lambda x:-x)
dp_ppm.sort(key=lambda x:-x)
dp_mmp.sort(key=lambda x:-x)
dp_mpm.sort(key=lambda x:-x)
dp_pmm.sort(key=lambda x:-x)
dp_mmm.sort(key=lambda x:-x)
ppp=sum(dp_ppp[0:M])
mpp=sum(dp_mpp[0:M])
pmp=sum(dp_pmp[0:M])
ppm=sum(dp_ppm[0:M])
mmp=sum(dp_mmp[0:M])
mpm=sum(dp_mpm[0:M])
pmm=sum(dp_pmm[0:M])
mmm=sum(dp_mmm[0:M])
ans=max([ppp,mpp,pmp,ppm,mmp,mpm,pmm,mmm])
print(ans)
Buggy python submission (verdict: Runtime Error):
from fractions import gcd
N,A,B,K=map(int,input().split())
mod=998244353

Factorial=[1]*(N+1)
for i in range(1,N+1):
  Factorial[i]=Factorial[i-1]*(i)%mod
def power(x,y):
  if y==0:
    return 1
  elif y==1:
    return x%mod
  elif y%2==0:
    return power(x,y//2)**2%mod
  else:
    return (power(x,y//2)**2)*x%mod

inverseFactorial=[1]*(N+1)
inverseFactorial[N]=power(Factorial[N],mod-2)
for i in range(0,N)[::-1]:
  inverseFactorial[i]=(inverseFactorial[i+1]*(i+1))%mod
  
def f(i,j):
  if i>j:
    i,j=j,i
  res=0
  if j<=N:
    for k in range(max(0,i+j-N),i+1):
      res+=Factorial[N]*inverseFactorial[i-k]*inverseFactorial[j-k]*inverseFactorial[k]*inverseFactorial[N-i-j+k]
  return res%mod
      
ans=0
g=gcd(A,B)
if K%g==0:
  A,B,K=A//g,B//g,K//g
else:
  print(0)
  exit()
for i in range(K//A+1):
  if (K-A*i)%B==0:
    x0=i
    y0=(K-A*i)//B
    break
m=0
while y0-A*m>=0:
  ans+=f(x0+B*m,y0-A*m)
  ans%=mod
  m+=1
    
print(ans%mod-1)

  

Fixed submission:
N=int(input())
ans=float("inf")
for i in range(1,N):
  A,B=str(i),str(N-i)
  S=0
  for a in range(len(A)):
    S+=int(A[a])
  for b in range(len(B)):
    S+=int(B[b])
  ans=min(ans,S)
print(ans)
Buggy python submission (verdict: Runtime Error):
class Unionfind:
  def __init__(self,n):
    self.Tree=[i for i in range(n)]
    self.rank=[0]*n

  def find(self,x):
    if x==self.Tree[x]:
      return x
    else:
      root=self.find(self.Tree[x])
      self.Tree[x]=root
      return root

  def unite(self,x,y):
    s1=self.find(x)
    s2=self.find(y)
    if s1==s2:
      pass
    else:
      if self.rank[s1]>self.rank[s2]:
        self.Tree[s2]=s1
      elif self.rank[s1]<self.rank[s2]:
        self.Tree[s1]=s2
      else:
        self.Tree[s2]=s1
        self.rank[s1]+=1
        
        
      
        
T=Unionfind(N)
for m in range(M):
  x,y=map(int,input().split())
  T.unite(x-1,y-1)
ans=0
for i in range(N):
  if T.find(P_list[i]-1)==T.find(i):
    ans+=1
print(ans)


Fixed submission:
N,M=map(int,input().split())
P_list=[int(p) for p in input().split()]
Tree=[i for i in range(N)]
def find(x):
  if x==Tree[x]:
    return x
  else:
    root=find(Tree[x])
    Tree[x]=root
    return root
def unite(x,y):
  s1=find(x)
  s2=find(y)
  if s1==s2:
    pass
  else:
    Tree[s1]=s2
for m in range(M):
  x,y=map(int,input().split())
  unite(x-1,y-1)
ans=0
for i in range(N):
  if find(P_list[i]-1)==find(i):
    ans+=1
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N,M=map(int,input().split())
P_list=[int(p) for p in input().split()]
Tree=[-1]*N
def find(x):
  while Tree[x]>=0:
    x=Tree[x]
  return x
def unite(x,y):
  s1=find(x)
  s2=find(y)
  if s1==s2:
    pass
  else:
    if Tree[s1]<Tree[s2]:
      Tree[s2]=s1
    elif Tree[s2]>Tree[s1]:
      Tree[s1]=s2
    else:
      Tree[s1]+=-1
      Tree[s2]=s1
  return
for m in range(M):
  x,y=map(int,input().split())
  unite(x-1,y-1)
ans=0
for i in range(N):
  if find(P_list[i]-1)==find(i):
    ans+=1
print(ans)
    
  

Fixed submission:
N,M=map(int,input().split())
P_list=[int(p) for p in input().split()]
Tree=[i for i in range(N)]
def find(x):
  if x==Tree[x]:
    return x
  else:
    root=find(Tree[x])
    Tree[x]=root
    return root
def unite(x,y):
  s1=find(x)
  s2=find(y)
  if s1==s2:
    pass
  else:
    Tree[s1]=s2
for m in range(M):
  x,y=map(int,input().split())
  unite(x-1,y-1)
ans=0
for i in range(N):
  if find(P_list[i]-1)==find(i):
    ans+=1
print(ans)