Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
H,W=map(int,input().split())
G=[list(input()) for i in range(H)]
G_t=[list(x) for x in list(zip(*G))]
Paired_y=[False]*H
def Check(G,H,W):
  for y1 in range(H):
    if Paired_y[y1]:
      continue
    for y2 in range(H):
      if y1==y2 or Paired_y[y2]:
        continue
      Paired_x=[False]*W
      for x1 in range(W):
        if Paired_x[x1]:
          continue
        for x2 in range(W):
          if x1==x2 or Paired_x[x2]:
            continue
          if G[y1][x1]==G[y2][x2] and G[y1][x2]==G[y2][x1]:
            Paired_x[x1]=True
            Paired_x[x2]=True
            break
      if W%2==1:
        if Paired_x.count(False)==1:
          Paired_y[y1]=True
          Paired_y[y2]=True
      else:
        if Paired_x.count(False)==0:
          Paired_y[y1]=True
          Paired_y[y2]=True
  if H%2==1:
    if Paired_y.count(False)==1:
      return True
    else:
      return False
  else:
    if Paired_y.count(False)==0:
      return True
    else:
      return False
  
if Check(G,H,W) and Check(G_t,W,H):
  print("YES")
else:
  print("NO")

      
      
        
                         
      
    


Fixed submission:
H,W=map(int,input().split())
G=[list(input()) for i in range(H)]
G_t=[list(x) for x in list(zip(*G))]
def Check(G,H,W):
  Paired_y=[False]*H
  for y1 in range(H):
    if Paired_y[y1]:
      continue
    for y2 in range(H):
      if y1==y2 or Paired_y[y2]:
        continue
      Paired_x=[False]*W
      for x1 in range(W):
        if Paired_x[x1]:
          continue
        for x2 in range(W):
          if x1==x2 or Paired_x[x2]:
            continue
          if G[y1][x1]==G[y2][x2] and G[y1][x2]==G[y2][x1]:
            Paired_x[x1]=True
            Paired_x[x2]=True
            break
      if W%2==1:
        if Paired_x.count(False)==1:
          r=Paired_x.index(False)
          if G[y1][r]==G[y2][r]:
            Paired_y[y1]=True
            Paired_y[y2]=True
            break
      else:
        if Paired_x.count(False)==0:
          Paired_y[y1]=True
          Paired_y[y2]=True
          break
  if H%2==1:
    if Paired_y.count(False)==1:
      return True
    else:
      return False
  else:
    if Paired_y.count(False)==0:
      return True
    else:
      return False
  
if Check(G,H,W) and Check(G_t,W,H):
  print("YES")
else:
  print("NO")
Buggy python submission (verdict: Runtime Error):
H,W,D=map(int,input().split())
A=[[0,0]]*(H*W)
j=0
for i in range(H):
  for a in input().split():
    A[int(a)-1]=[i,j]
    j+=1
  j=0
Q=int(input())
S=[[0]*((H*W-1-i)//D+1) for i in range(D)]
for i in range(D):
  for k in range((H*W-1-i)//D):
    x1=A[D*k+i-1][0]
    x2=A[D*(k+1)+i-1][0]
    y1=A[D*k+i-1][1]
    y2=A[D*(k+1)+i-1][1]
    S[i][k+1]+=S[i][k]+abs(x1-x2)+abs(y1-y2)
ans=0
for q in range(Q):
  l,r=map(int,input().split())
  m=l%D
  ans=S[m][(r-m)//D]-S[m][(l-m)//D]
  print(ans)
  ans=0

Fixed submission:
H,W,D=map(int,input().split())
A=[[0,0]]*(H*W)
j=0
for i in range(H):
  for a in input().split():
    A[int(a)-1]=[i,j]
    j+=1
  j=0
Q=int(input())
S=[[0]*((H*W-1-i)//D+1) for i in range(D)]
for i in range(D):
  for k in range((H*W-1-i)//D):
    x1=A[D*k+i][0]
    x2=A[D*(k+1)+i][0]
    y1=A[D*k+i][1]
    y2=A[D*(k+1)+i][1]
    S[i][k+1]+=S[i][k]+abs(x1-x2)+abs(y1-y2)
ans=0
for q in range(Q):
  l,r=map(int,input().split())
  m=(l-1)%D
  ans=S[m][(r-1-m)//D]-S[m][(l-1-m)//D]
  print(ans)
  ans=0

Buggy python submission (verdict: Runtime Error):
H,W,D=map(int,input().split())
A=[[0,0]]*(H*W)
j=0
for i in range(H):
  for a in input().split():
    A[int(a)-1]=[i,j]
    j+=1
  j=0
Q=int(input())
S=[[0]*(((H*W-1)-i)//D+1) for i in range(D)]
for i in range(D):
  for k in range((H*W-1-i)//D):
    x1=A[D*k+i-1][0]
    x2=A[D*(k+1)+i-1][0]
    y1=A[D*k+i-1][1]
    y2=A[D*(k+1)+i-1][1]
    S[i][k+1]+=S[i][k]+abs(x1-x2)+abs(y1-y2)
ans=0
for q in range(Q):
  l,r=map(int,input().split())
  if l!=l%D:
    ans=S[l%D][(r-l%D)//D]-S[l%D][(l-l%D)//D]
  else:
    ans=S[l%D][(r-l%D)//D]
  print(ans)
  ans=0

Fixed submission:
H,W,D=map(int,input().split())
A=[[0,0]]*(H*W)
j=0
for i in range(H):
  for a in input().split():
    A[int(a)-1]=[i,j]
    j+=1
  j=0
Q=int(input())
S=[[0]*((H*W-1-i)//D+1) for i in range(D)]
for i in range(D):
  for k in range((H*W-1-i)//D):
    x1=A[D*k+i][0]
    x2=A[D*(k+1)+i][0]
    y1=A[D*k+i][1]
    y2=A[D*(k+1)+i][1]
    S[i][k+1]+=S[i][k]+abs(x1-x2)+abs(y1-y2)
ans=0
for q in range(Q):
  l,r=map(int,input().split())
  m=(l-1)%D
  ans=S[m][(r-1-m)//D]-S[m][(l-1-m)//D]
  print(ans)
  ans=0

Buggy python submission (verdict: Time Limit Exceeded):
H,W,D=map(int,input().split())
A=[[0,0]]*(H*W)
j=0
for i in range(H):
  for a in input().split():
    A[int(a)-1]=[i,j]
    j+=1
  j=0
Q=int(input())
ans=0
for q in range(Q):
  l,r=map(int,input().split())
  for k in range((r-l)//D):
    x1=A[l+D*k-1][0]
    x2=A[l+D*(k+1)-1][0]
    y1=A[l+D*k-1][1]
    y2=A[l+D*(k+1)-1][1]
    ans+=abs(x1-x2)
    ans+=abs(y1-y2)
  print(ans)
  ans=0

Fixed submission:
H,W,D=map(int,input().split())
A=[[0,0]]*(H*W)
j=0
for i in range(H):
  for a in input().split():
    A[int(a)-1]=[i,j]
    j+=1
  j=0
Q=int(input())
S=[[0]*((H*W-1-i)//D+1) for i in range(D)]
for i in range(D):
  for k in range((H*W-1-i)//D):
    x1=A[D*k+i][0]
    x2=A[D*(k+1)+i][0]
    y1=A[D*k+i][1]
    y2=A[D*(k+1)+i][1]
    S[i][k+1]+=S[i][k]+abs(x1-x2)+abs(y1-y2)
ans=0
for q in range(Q):
  l,r=map(int,input().split())
  m=(l-1)%D
  ans=S[m][(r-1-m)//D]-S[m][(l-1-m)//D]
  print(ans)
  ans=0
Buggy python submission (verdict: Time Limit Exceeded):
from itertools import accumulate
from operator import add
N,K=map(int,input().split())
L=2*K
Map=[[0]*L for i in range(L)]

for i in range(N):
  x,y,c=input().split()
  x,y=int(x),int(y)
  if c=="W":
    x-=K
  x,y=x%L,y%L
  if y>=K:
    x,y=(x-K)%L,y-K
    
  Map[x][y]+=1
  Map[x][y-K]+=-1
  if x!=K:
    Map[x-K][y-K]+=1
    Map[x-K][y]+=-1
  if x>K:
    Map[0][y]+=1
    Map[0][y-K]+=-1

Map=[accumulate(i) for i in Map]
Map=[accumulate(i) for i in zip(*Map)]
Map=list(map(list,zip(*Map)))
Map=[map(add, Map[i][:K], Map[i-K][K:]) for i in range(L)]

print(max(map(max,Map)))

    
  
  


Fixed submission:
from itertools import accumulate
from operator import add
N,K=map(int,input().split())
L=2*K
Map=[[0]*L for i in range(L)]

for i in range(N):
  x,y,c=input().split()
  x,y=int(x),int(y)
  if c=="W":
    x-=K
  x,y=x%L,y%L
  if y>=K:
    x,y=(x-K)%L,y-K
    
  Map[x][y]+=1
  Map[x][y-K]+=-1
  if x!=K:
    Map[x-K][y-K]+=1
    Map[x-K][y]+=-1
  if x>K:
    Map[0][y]+=1
    Map[0][y-K]+=-1

Map=[accumulate(i) for i in Map]
Map=[accumulate(i) for i in zip(*Map)]
Map=list(map(list,zip(*Map)))
Map=[map(add, Map[i][:K], Map[i-K][K:]) for i in range(L)]

print(max(map(max,Map)))
Buggy python submission (verdict: Runtime Error):
N=int(input())
List=[int(input()) for i in range(N)]
List.sort(key=lambda x:x)
n=1
So=[]
while n<=List[N-1]:
  if n in List:
    So.append(n)
  n+=1
print(len(So))

Fixed submission:
S=input()
print("2018/"+S[5:])
Buggy python submission (verdict: Runtime Error):
N=int(input())
List=list(map(int,input().split()))
Flag=0
Counter=-1
Element=0
while Flag<1:
  while Element<N:
      if List[Element]%2==1:
        Flag=1
      List[Element]=List[Element]/2
      Element+=1
  Element=0
  Counter+=1
print(Counter)

Fixed submission:
s=input()
C=0
N=0
while C<3:
  if s[C]=="1":
    N+=1
  C+=1
print(N)
Buggy python submission (verdict: Runtime Error):
N,C=map(int,input().split())
Time=[[0]*(10**5+1) for c in range(C)]
for i in range(N):
  s,t,c=map(int,input().split())  
  Time[c-1][s-1:t] = [1]*(t-s+1)
Times=max(map(sum,zip(*Time)))
print(Times)

Fixed submission:
N,A,B=map(int,input().split())
print(min(A*N,B))
Buggy python submission (verdict: Runtime Error):
N,M=map(int,input().split())
G=[[] for i in range(N)]
for i in range(M):
  a,b=map(int,input().split())
  a-=1
  b-=1
  G[a].append(b)
  G[b].append(a)
color=[-1]*N  
def dfs(x):
  for i in G[x]:
    if color[i]==-1:
      color[i]=1^color[x]
      dfs(i)
    elif color[i]==color[x]:
      print((N*(N-1))//2-M)
      exit()
color[0]=0
dfs(0)
b=0
for i in range(N):
  b+=color[i]
print(b*(N-b)-M)
      
     
      

Fixed submission:
import sys
sys.setrecursionlimit(10**7)
N,M=map(int,input().split())
G=[[] for i in range(N)]
for i in range(M):
  a,b=map(int,input().split())
  a-=1
  b-=1
  G[a].append(b)
  G[b].append(a)
color=[-1]*N  
def dfs(x):
  for i in G[x]:
    if color[i]==-1:
      color[i]=1^color[x]
      dfs(i)
    elif color[i]==color[x]:
      print((N*(N-1))//2-M)
      exit()
color[0]=0
dfs(0)
b=0
for i in range(N):
  b+=color[i]
print(b*(N-b)-M)
Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
Sister=[int(input()) for i in range(N)]
set_Sister=set(Sister)
Paper=0
for i in set_Sister:
  if Sister.count(i)%2==1:
    Paper+=1
print(Paper)

Fixed submission:
N=int(input())
Sister={}
Paper=0
for i in range(N):
  index=int(input())
  if index not in Sister:
    Sister[index]=1
  else:
    Sister[index]+=1
for i in Sister:
  if Sister[i]%2==1:
    Paper+=1
print(Paper)

Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
Sister=[int(input()) for i in range(N)]
set_Sister=set(Sister)
Paper=[]
for i in set_Sister:
  if Sister.count(i)%2==1:
    Paper.append(i)
print(len(Paper))

Fixed submission:
N=int(input())
Sister={}
Paper=0
for i in range(N):
  index=int(input())
  if index not in Sister:
    Sister[index]=1
  else:
    Sister[index]+=1
for i in Sister:
  if Sister[i]%2==1:
    Paper+=1
print(Paper)

Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
Sister=[int(input()) for i in range(N)]
Paper=[i for i in Sister if Sister.count(i)%2==1]
print(len(Paper))

Fixed submission:
N=int(input())
Sister={}
Paper=0
for i in range(N):
  index=int(input())
  if index not in Sister:
    Sister[index]=1
  else:
    Sister[index]+=1
for i in Sister:
  if Sister[i]%2==1:
    Paper+=1
print(Paper)

Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
Sister=[int(input()) for i in range(N)]
Paper=[i for i in Sister if Sister.count(i)%2==1]
print(len(Paper))

Fixed submission:
N=int(input())
Sister={}
Paper=0
for i in range(N):
  index=int(input())
  if index not in Sister:
    Sister[index]=1
  else:
    Sister[index]+=1
for i in Sister:
  if Sister[i]%2==1:
    Paper+=1
print(Paper)

Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
Paper=[]
for i in range(N):
  A=int(input())
  if A in Paper:
    Paper.remove(A)
  else:
    Paper.append(A)
print(len(Paper))

Fixed submission:
N=int(input())
Sister={}
Paper=0
for i in range(N):
  index=int(input())
  if index not in Sister:
    Sister[index]=1
  else:
    Sister[index]+=1
for i in Sister:
  if Sister[i]%2==1:
    Paper+=1
print(Paper)
Buggy python submission (verdict: Runtime Error):
def gcd(a,b):
  if a<b:
    a,b=b,a
  while b>0:
    a,b=b,a%b
  return int(a)
def lcm(a,b):
  return int(a*b/gcd(a,b))
N=int(input())
T=1
for i in range(N):
  ti=int(input())
  T=lcm(T,ti)
print(T)

Fixed submission:
def gcd(a,b):
  if a<b:
    a,b=b,a
  while b>0:
    a,b=b,a%b
  return int(a)
N=int(input())
T=1
for i in range(N):
  ti=int(input())
  T=T*ti//gcd(T,ti)
print(T)

Buggy python submission (verdict: Runtime Error):
def gcd(a,b):
  while b>0:
    a,b=b,a%b
  return int(a)
def lcm(a,b):
  return int(a*b/gcd(a,b))
N=int(input())
T=1
for i in range(N):
  ti=int(input())
  T=lcm(T,ti)
print(T)

Fixed submission:
def gcd(a,b):
  if a<b:
    a,b=b,a
  while b>0:
    a,b=b,a%b
  return int(a)
N=int(input())
T=1
for i in range(N):
  ti=int(input())
  T=T*ti//gcd(T,ti)
print(T)

Buggy python submission (verdict: Runtime Error):
def gcd(a,b):
  while b>0:
    a,b=b,a%b
  return int(a)
def lcm(a,b):
  return int(a*b/gcd(a,b))
N=int(input())
List_T=[int(input()) for i in range(N)]
T=1
n=1
for i in List_T:
  T=lcm(T,i)
print(T)

Fixed submission:
def gcd(a,b):
  if a<b:
    a,b=b,a
  while b>0:
    a,b=b,a%b
  return int(a)
N=int(input())
T=1
for i in range(N):
  ti=int(input())
  T=T*ti//gcd(T,ti)
print(T)

Buggy python submission (verdict: Runtime Error):
def gcd(a,b):
  while a>=1 and b>=1:
    a,b=b,a%b
  return int(a)
def lcm(a,b):
  return int(a*b/gcd(a,b))
N=int(input())
List_T=[int(input()) for i in range(N)]
T=1
n=1
for i in List_T:
  T=lcm(T,i)
print(T)

Fixed submission:
def gcd(a,b):
  if a<b:
    a,b=b,a
  while b>0:
    a,b=b,a%b
  return int(a)
N=int(input())
T=1
for i in range(N):
  ti=int(input())
  T=T*ti//gcd(T,ti)
print(T)

Buggy python submission (verdict: Runtime Error):
def gcd(a,b):
  while b>=1:
    a,b=b,a%b
  return int(a)
def lcm(a,b):
  return int(a*b/gcd(a,b))
N=int(input())
List_T=[int(input()) for i in range(N)]
T=1
n=1
for i in List_T:
  T=lcm(T,i)
print(int(T))

Fixed submission:
def gcd(a,b):
  if a<b:
    a,b=b,a
  while b>0:
    a,b=b,a%b
  return int(a)
N=int(input())
T=1
for i in range(N):
  ti=int(input())
  T=T*ti//gcd(T,ti)
print(T)

Buggy python submission (verdict: Runtime Error):
def gcd(a,b):
  while b>=1:
    a,b=b,a%b
  return a
def lcm(a,b):
  return a*b/gcd(a,b)
N=int(input())
List_T=[int(input()) for i in range(N)]
T=1
for i in List_T:
  T=lcm(T,i)
print(int(T))


Fixed submission:
def gcd(a,b):
  if a<b:
    a,b=b,a
  while b>0:
    a,b=b,a%b
  return int(a)
N=int(input())
T=1
for i in range(N):
  ti=int(input())
  T=T*ti//gcd(T,ti)
print(T)

Buggy python submission (verdict: Runtime Error):
def gcd(a,b):
  while b>=1:
    a,b=b,a%b
  return a
def lcm(a,b):
  return a*b/gcd(a,b)
N=int(input())
List_T=[int(input()) for i in range(N)]
T=1
n=1
for i in List_T:
  T=lcm(T,i)
print(int(T))

Fixed submission:
def gcd(a,b):
  if a<b:
    a,b=b,a
  while b>0:
    a,b=b,a%b
  return int(a)
N=int(input())
T=1
for i in range(N):
  ti=int(input())
  T=T*ti//gcd(T,ti)
print(T)
Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
a=[int(i) for i in input().split()]
ans=0
while True:
  f=0
  for i in range(N):
    if a[i]>=N:
      d=a[i]//N
      ans+=d
      a[i]%=N
      for j in range(N):
        if i!=j:
          a[j]+=d
      f=1
      break
  if f==0:
    break
print(ans)
      
  
        

Fixed submission:
N=int(input())
a=[int(i) for i in input().split()]
ans=0
while True:
  f=0
  for i in range(N):
    if a[i]>=N:
      d=a[i]//N
      ans+=d
      a[i]%=N
      for j in range(N):
        if i!=j:
          a[j]+=d
    else:
      f+=1
  if f==N:
    break
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
graph=[[] for i in range(N)]
for i in range(N-1):
  a,b=map(int,input().split())
  graph[a-1].append(b-1)
  graph[b-1].append(a-1)
root=[[0]]
depth=[-1]*N
depth[0]=0
while root:
  R=root.pop()
  s=R[-1]
  if s==N-1:
    one_to_N=R
    break
  for t in graph[s]:
    if depth[t]==-1:
      depth[t]=depth[s]+1
      root.append(R+[t])
d=len(one_to_N)
if d%2==1:
  a,b=one_to_N[d//2],one_to_N[d//2+1]
else:
  a,b=one_to_N[d//2-1],one_to_N[d//2]
graph[a].remove(b)
graph[b].remove(a)

dfs_stack=[0]
tree=[0]
depth1=[-1]*N
depth1[0]=0
while dfs_stack:
  s1=dfs_stack.pop()
  for t1 in graph[s1]:
    if depth1[t1]==-1:
      depth1[t1]=1
      dfs_stack.append(t1)
      tree.append(t1)
  
F=len(tree)

if F>N-F:
  print("Fennec")
else:
  print("Snuke")


Fixed submission:
N=int(input())
graph=[[] for i in range(N)]
for i in range(N-1):
  a,b=map(int,input().split())
  graph[a-1].append(b-1)
  graph[b-1].append(a-1)
dfs_stack_Fennec=[0]
dfs_stack_Snuke=[N-1]
depth_Fennec=[-1]*N
depth_Snuke=[-1]*N
depth_Fennec[0]=0
depth_Snuke[N-1]=0
while dfs_stack_Fennec or dfs_stack_Snuke:
  s1=dfs_stack_Fennec.pop()
  s2=dfs_stack_Snuke.pop()
  for t1 in graph[s1]:
    if depth_Fennec[t1]==-1:
      depth_Fennec[t1]=depth_Fennec[s1]+1
      dfs_stack_Fennec.append(t1)
  for t2 in graph[s2]:
    if depth_Snuke[t2]==-1:
      depth_Snuke[t2]=depth_Snuke[s2]+1
      dfs_stack_Snuke.append(t2)
ans=0
for i in range(N):
  if depth_Fennec[i]<=depth_Snuke[i]:
    ans+=1
if 2*ans>N:
  print("Fennec")
else:
  print("Snuke")
Buggy python submission (verdict: Runtime Error):
N=int(input())
a=[int(i)-1 for i in input().split()]
count=[0]*N
for i in range(N):
  count[a[i]]+=1
  if count[a[i]]==2:
    D=a[i]
    break
flag=False
k=0
mod=10**9+7
for i in range(N+1):
  if a[i]==D and not flag:
    flag=True
  elif a[i]==D and flag:
    break
  elif flag:
    k+=1
    
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 comb(x,y):
  if x<y or y<0:
    return 0
  else:
    return (Factorial[x]*inverseFactorial[y]*inverseFactorial[x-y])%mod

dp=[[0]*3 for i in range(N+2)]
dp[0][0]=1

for i in range(N+1):
  dp[i+1][0]=comb(N-1,i+1)
  dp[i+1][1]=-comb(N-k-1,i)+2*dp[i][0]
  if i>=1:
    dp[i+1][2]=dp[i-1][0]
  print(sum(dp[i+1])%mod)


Fixed submission:
N=int(input())
a=[int(i)-1 for i in input().split()]
count=[0]*N
for i in range(N+1):
  count[a[i]]+=1
  if count[a[i]]==2:
    D=a[i]
    break
flag=False
k=0
mod=10**9+7
for i in range(N+1):
  if a[i]==D and not flag:
    flag=True
  elif a[i]==D and flag:
    break
  elif flag:
    k+=1
    
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 comb(x,y):
  if x<y or y<0:
    return 0
  else:
    return (Factorial[x]*inverseFactorial[y]*inverseFactorial[x-y])%mod

dp=[[0]*3 for i in range(N+2)]
dp[0][0]=1

for i in range(N+1):
  dp[i+1][0]=comb(N-1,i+1)
  dp[i+1][1]=-comb(N-k-1,i)+2*dp[i][0]
  if i>=1:
    dp[i+1][2]=dp[i-1][0]
  print(sum(dp[i+1])%mod)
Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
A=[int(i) for i in input().split()]
score=[0]*(N+1)
score[0]=sum(A[0:N])-sum(sorted(A[N:3*N])[0:N])
former=sorted(A[0:N-1])
latter=A[N:3*N]
for i in range(1,N+1):
  score[i]=score[i-1]+A[N+i-1]-A[N+i-2]
  if former!=[]:
    if former[0]<A[N+i-2]:
      score[i]+=A[N+i-2]-former[0]
      del former[0]
      former.append(A[N+i-2])
      former.sort(key=lambda x:x)
  if sorted(latter)[N-1]>=A[N+i-1]:
    score[i]+=A[N+i-1]-sorted(latter)[N]
  del latter[0]
print(max(score))


Fixed submission:
import heapq
import copy
N=int(input())
A=list(map(int,input().split()))
ca=copy.deepcopy(A)
fsl=[0 for i in range(N+1)]
f=ca[:N]
heapq.heapify(f)
fs=sum(f)
fsl[0]=fs
for i in range(N,2*N):
    heapq.heappush(f,A[i])
    fs=fs+A[i]-heapq.heappop(f)
    fsl[i-N+1]=fs
lsl=[0 for i in range(N+1)]
l=list(map(lambda x:-x,ca[2*N:]))
heapq.heapify(l)
ls=sum(l)
lsl[-1]=ls
for i in range(N,2*N):
    heapq.heappush(l,-A[3*N-i-1])
    ls=ls-A[3*N-i-1]-heapq.heappop(l)
    lsl[2*N-i-1]=ls
ans=-10**20
for i in range(N+1):
  ans=max(ans,fsl[i]+lsl[i])
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N,M=map(int,input().split())
Q=[[int(i) for i in input().split()] for i in range(M)]
Q.sort(key=lambda x:x[1])
mod=10**9+7
dp=[[[0]*max(1,c) for c in range(max(1,b+1))] for b in range(N+1)]
                           
for a in range(N+1):
  for b in range(max(1,a)):
    for c in range(max(1,b)):
      dp[a].append([[0]*(c+1) for i in range(b+1)])
dp[0][0][0]=1
k=0
for a in range(N+1):
  check=[]
  if k<=M-1:
    while a==Q[k][1]:
      l,r,x=Q[k]
      check.append((l,r,x))
      k+=1
      if k==M:
        break
  for b in range(max(1,a)):
    for c in range(max(1,b)):
      for l,r,x in check:
        if x==1:
          if not b<l:
            dp[a][b][c]=0
            continue
        elif x==2:
          if not (b>=l and c<l):
            dp[a][b][c]=0
            continue
        elif x==3:
          if not c>=l:
            dp[a][b][c]=0
            continue
      dp[a][b][c]%=mod
      if a<=N-1:
        dp[a+1][b][c]+=dp[a][b][c]
        dp[a+1][a][c]+=dp[a][b][c]
        dp[a+1][a][b]+=dp[a][b][c]
ans=0
for b in range(N):
  for c in range(b):
    ans+=dp[N][b][c]
    ans%=mod
print(ans)


Fixed submission:
N,M=map(int,input().split())
Q=[[int(i) for i in input().split()] for i in range(M)]
Q.sort(key=lambda x:x[1])
mod=10**9+7
dp=[[[0]*max(1,c) for c in range(max(1,b+1))] for b in range(N+1)]
dp[0][0][0]=1
k=0
for a in range(N+1):
  check=[]
  if k<=M-1:
    while a==Q[k][1]:
      l,r,x=Q[k]
      check.append((l,r,x))
      k+=1
      if k==M:
        break
  for b in range(max(1,a)):
    for c in range(max(1,b)):
      for l,r,x in check:
        if x==1:
          if not b<l:
            dp[a][b][c]=0
            continue
        elif x==2:
          if not (b>=l and c<l):
            dp[a][b][c]=0
            continue
        elif x==3:
          if not c>=l:
            dp[a][b][c]=0
            continue
      dp[a][b][c]%=mod
      if a<=N-1:
        dp[a+1][b][c]+=dp[a][b][c]
        dp[a+1][a][c]+=dp[a][b][c]
        dp[a+1][a][b]+=dp[a][b][c]
ans=0
for b in range(N):
  for c in range(max(1,b)):
    ans+=dp[N][b][c]
    ans%=mod
print(ans)
Buggy python submission (verdict: Runtime Error):
n=int(input())
mod=10**9+7
dp=[0]*(n+1)
S=[0]*(n+1)
dp[0]=1
dp[1]=1
dp[2]=1
S[0]=1
for i in range(n):
  if i+1>=3:
    dp[i+1]=2*dp[i]-dp[i-1]+dp[i-2]
  dp[i+1]%=mod
  S[i+1]=S[i]+(n-1)*dp[i]
  S[i+1]%=mod
ans=S[n]
for i in range(1,n):
  ans+=((n-1)**2)*dp[i-1]
  ans%=mod
print(ans)
#print(S)
#print(dp)

Fixed submission:
n=int(input())
if n==1:
  print(1)
  exit()
mod=10**9+7
dp=[0]*(n+1)
S=[0]*(n+1)
dp[0]=1
dp[1]=1
dp[2]=1
S[0]=1
for i in range(n):
  if i+1>=3:
    dp[i+1]=2*dp[i]-dp[i-1]+dp[i-2]
  dp[i+1]%=mod
  S[i+1]=S[i]+(n-1)*dp[i]
  S[i+1]%=mod
ans=S[n]
for i in range(1,n):
  ans+=((n-1)**2)*dp[i-1]
  ans%=mod
print(ans)
#print(S)
#print(dp)