Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
N,M,L=map(int, input().split())
def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    for k in range(N):
        for i in range(N):
            for j in range(N):
                d[i][j]=min(d[i][j],d[i][k] + d[k][j])
    return d

d=[[float("inf")]*N for i in range(N)] 
#d[u][v] : 辺uvのコスト(存在しないときはinf)
for i in range(M):
    x,y,z=map(int,input().split())
    d[x-1][y-1]=z
    d[y-1][x-1]=z
for i in range(N):
    d[i][i]=0 #自身のところに行くコストは０
D=warshall_floyd(d)
E=[[float("inf")]*N for i in range(N)] 
for i in range(N):
  for j in range(N):
    if D[i][j]==0:
      E[i][j]=0
    elif D[i][j]<=L:
      E[i][j]=1
F=warshall_floyd(E)
N=int(input())
for i in range(N):
  x,y=map(int,input().split())
  if F[x-1][y-1]==float("inf"):
    print(-1)
  else:
    print(F[x-1][y-1]-1)

Fixed submission:
N,M,L=map(int, input().split())
def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    for k in range(N):
        for i in range(N):
            for j in range(N):
                d[i][j]=min(d[i][j],d[i][k] + d[k][j])
    return d

d=[[float("inf")]*N for i in range(N)] 
#d[u][v] : 辺uvのコスト(存在しないときはinf)
for i in range(M):
    x,y,z=map(int,input().split())
    d[x-1][y-1]=z
    d[y-1][x-1]=z
for i in range(N):
    d[i][i]=0 #自身のところに行くコストは０
D=warshall_floyd(d)
E=[[float("inf")]*N for i in range(N)] 
for i in range(N):
  for j in range(N):
    if D[i][j]==0:
      E[i][j]=0
    elif D[i][j]<=L:
      E[i][j]=1
F=warshall_floyd(E)
N=int(input())
for i in range(N):
  x,y=map(int,input().split())
  if F[x-1][y-1]==float("inf"):
    print(-1)
  else:
    print(F[x-1][y-1]-1)
Buggy python submission (verdict: Runtime Error):
S=input()
K=int(input())
A=[]
D=1
for i in range(len(S)-2):
  if S[i]==S[i+1]:
    D+=1
  else:
    A.append(D)
    D=1
A.append(D)
B=[i for i in A if not i==1]
C=[(i//2) for i in B]
count=(sum(C)*K)

if S[0]==S[-1]:
  count+= (K-1)
if S[-1]==S[-2]:
  count+=1
  
print(count)

Fixed submission:
S=input()
K=int(input())
T=S+S
if len(set(S))!=1:
  A=[]
  D=1
  for i in range(len(S)-1):
    if S[i]==S[i+1]:
      D+=1
    else:
      A.append(D)
      D=1
  A.append(D)
  B=[i for i in A if not i==1]
  C=[(i//2) for i in B]
  Scount=(sum(C))

  E=[]
  H=1
  for j in range(len(T)-1):
    if T[j]==T[j+1]:
      H+=1
    else:
      E.append(H)
      H=1
  E.append(H)
  F=[j for j in E if not j==1]
  G=[(j//2) for j in F]
  Tcount=(sum(G))
  ans=(Tcount-Scount)*(K-1)+Scount
  print(ans)
else:
  print(K*len(S)//2)

Buggy python submission (verdict: Runtime Error):
S=input()
K=int(input())
count=0
if S[0] == S[-1]:
  count+= (K-1)  
if S[-1]==S[-2]:
  count+=1
A=[]
D=1
for i in range(len(S)-2):
  if S[i]==S[i+1]:
    D+=1
  else:
    A.append(D)
    D=1
A.append(D)
B=[i for i in A if not i==1]
C=[(i//2) for i in B]

print(sum(C)*K+count)  

Fixed submission:
S=input()
K=int(input())
T=S+S
if len(set(S))!=1:
  A=[]
  D=1
  for i in range(len(S)-1):
    if S[i]==S[i+1]:
      D+=1
    else:
      A.append(D)
      D=1
  A.append(D)
  B=[i for i in A if not i==1]
  C=[(i//2) for i in B]
  Scount=(sum(C))

  E=[]
  H=1
  for j in range(len(T)-1):
    if T[j]==T[j+1]:
      H+=1
    else:
      E.append(H)
      H=1
  E.append(H)
  F=[j for j in E if not j==1]
  G=[(j//2) for j in F]
  Tcount=(sum(G))
  ans=(Tcount-Scount)*(K-1)+Scount
  print(ans)
else:
  print(K*len(S)//2)
Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
A=list(map(int,input().split()))
ans=[A.index(i)+1 for i in range(1,N+1) ]
print(*ans)

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

print(*X)
Buggy python submission (verdict: Time Limit Exceeded):
N,K,Q=map(int,input().split())
List=[int(input()) for i in range(Q)]
for j in range(1,N+1):
  
  if (K-Q+List.count(j)) <1:
    print('No')
  else:
    print('Yes')

Fixed submission:
N,K,Q=map(int,input().split())
scores=[0 for i in range(N)]

for j in range(Q):
  A=int(input())
  scores[A-1]+=1
  
for score in scores:
  if K-Q+score>0:
    print('Yes')
  else:
    print('No')

Buggy python submission (verdict: Time Limit Exceeded):
N,K,Q=map(int,input().split())
List=[int(input()) for i in range(Q)]
for j in range(1,N+1):
  
  if (K-Q+List.count(j)) <1:
    print('No')
  else:
    print('Yes')

Fixed submission:
N,K,Q=map(int,input().split())
scores=[0 for i in range(N)]

for j in range(Q):
  A=int(input())
  scores[A-1]+=1
  
for score in scores:
  if K-Q+score>0:
    print('Yes')
  else:
    print('No')

Buggy python submission (verdict: Time Limit Exceeded):
N,K,Q=map(int,input().split())
List=[int(input()) for i in range(Q)]
for j in range(1,N+1):
  if (K-Q+List.count(j)) >0:
    print('Yes')
  else:
    print('No')

Fixed submission:
N,K,Q=map(int,input().split())
scores=[0 for i in range(N)]

for j in range(Q):
  A=int(input())
  scores[A-1]+=1
  
for score in scores:
  if K-Q+score>0:
    print('Yes')
  else:
    print('No')
Buggy python submission (verdict: Time Limit Exceeded):
N,M=map(int,input().split())
A=list(map(int,input().split()))
for i in range(M):
  A[A.index(max(A))]=((max(A))//2)
 
print(sum(A))

Fixed submission:
import heapq
N,M=map(int,input().split())
A=list(map(lambda x: int(x)*(-1), input().split()))
heapq.heapify(A)

for i in range(M):
  x=heapq.heappop(A)
  y=(((-1)*x)//2)*(-1)  
  heapq.heappush(A,y)
print((-1)*sum(A))
Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
S=input()
ans=0

def Z_algorithm(s):
    N = len(s)
    Z_alg = [0]*N

    Z_alg[0] = N
    i = 1
    j = 0
    while i < N:
        while i+j < N and s[j] == s[i+j]:
            j += 1
        Z_alg[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i+k < N and k + Z_alg[k]<j:
            Z_alg[i+k] = Z_alg[k]
            k += 1
        i += k
        j -= k
    return Z_alg

ans=0  
for i in range(N):
  d=S[i:]
  D=Z_algorithm(d)
  for j in range(N-i):
    ans=max(ans,min(j,D[j]))
print(ans)

Fixed submission:
N=int(input())
S=input()
ans=0

def Z_algorithm(s):
    N = len(s)
    Z_alg = [0]*N

    Z_alg[0] = N
    i = 1
    j = 0
    while i < N:
        while i+j < N and s[j] == s[i+j]:
            j += 1
        Z_alg[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i+k < N and k + Z_alg[k]<j:
            Z_alg[i+k] = Z_alg[k]
            k += 1
        i += k
        j -= k
    return Z_alg

ans=0  
for i in range(N):
  d=S[i:]
  D=Z_algorithm(d)
  for j in range(N-i):
    ans=max(ans,min(j,D[j]))
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
S=input()

def lcs(s,t):
  a=len(s)
  b=len(t)
  dp=[[0]*(b+1) for i in range(a+1)]
  for i in range(a):
    for j in range(b):
      if s[i]==t[j]:
        dp[i+1][j+1]=dp[i][j]+1
      else:
        dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j])
  return dp[-1][-1]

ans=0
for i in range(1,N):
  s=S[:i]
  t=S[i:]
  a=lcs(s,t)
  ans=max(a,ans)
print(ans)

Fixed submission:
N=int(input())
S=input()
ans=0

def Z_algorithm(s):
    N = len(s)
    Z_alg = [0]*N

    Z_alg[0] = N
    i = 1
    j = 0
    while i < N:
        while i+j < N and s[j] == s[i+j]:
            j += 1
        Z_alg[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i+k < N and k + Z_alg[k]<j:
            Z_alg[i+k] = Z_alg[k]
            k += 1
        i += k
        j -= k
    return Z_alg

ans=0  
for i in range(N):
  d=S[i:]
  D=Z_algorithm(d)
  for j in range(N-i):
    ans=max(ans,min(j,D[j]))
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
S=input()

def lcs(s,t):
  a=len(s)
  b=len(t)
  dp=[[0]*(b+1) for i in range(a+1)]
  for i in range(a):
    for j in range(b):
      if s[i]==t[j]:
        dp[i+1][j+1]=dp[i][j]+1
      else:
        dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j])
  return dp[-1][-1]

ans=0
for i in range(1,N):
  s=S[:i]
  t=S[i:]
  a=lcs(s,t)
  ans=max(a,ans)
print(ans)

Fixed submission:
N=int(input())
S=input()
ans=0

def Z_algorithm(s):
    N = len(s)
    Z_alg = [0]*N

    Z_alg[0] = N
    i = 1
    j = 0
    while i < N:
        while i+j < N and s[j] == s[i+j]:
            j += 1
        Z_alg[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i+k < N and k + Z_alg[k]<j:
            Z_alg[i+k] = Z_alg[k]
            k += 1
        i += k
        j -= k
    return Z_alg

ans=0  
for i in range(N):
  d=S[i:]
  D=Z_algorithm(d)
  for j in range(N-i):
    ans=max(ans,min(j,D[j]))
print(ans)
Buggy python submission (verdict: Runtime Error):
import bisect
from collections import defaultdict

S=list(input().strip())
T=list(input().strip())
L=len(S)

if set(T)>set(S):
  print(-1)
  exit()

d=defaultdict(list)
for i,s in enumerate(S):
  d[s].append(i)
start=-1
ans=0
for i in T:
  p=bisect.bisect_right(d[i],start)
  le=len(d[i])
  if p==le:
    ans+=(L-start-1)+(d[i][0]+1)
    start=d[i][0]    
  else:
    ans+=d[i][p]-start
    start=d[i][p]
print(ans)

Fixed submission:
import bisect
from collections import defaultdict

S=list(input().strip())
T=list(input().strip())
L=len(S)

if not set(T)<=set(S):
  print(-1)
  exit()

d=defaultdict(list)
for i,s in enumerate(S):
  d[s].append(i)
start=-1
ans=0
for i in T:
  p=bisect.bisect_right(d[i],start)
  le=len(d[i])
  if p==le:
    ans+=(L-start-1)+(d[i][0]+1)
    start=d[i][0]    
  else:
    ans+=d[i][p]-start
    start=d[i][p]
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
A=[sorted(input()) for i in range(N)]

#Nのみを見ればよい
ans=0
for i in range(1,N):
  for j in range(i):
    if A[i]==A[j]:
      ans+=1
print(ans)

Fixed submission:
N=int(input())
m=dict()
ans=0
for	i in range(N):
  s=input()
  s=''.join(sorted(s))
  if s in m:
    ans += m[s]
    m[s] += 1
  else:
    m[s] = 1
print(ans)
Buggy python submission (verdict: Runtime Error):
import heapq
N, M = map(int, input().split())
X = sorted([list(map(int, input().split())) for _ in range(N)], key = lambda x: x[0])

hq = []
ans, j = 0, 0

for i in range(1, M + 1): 
    while (j < N) and (X[j][0] <= i):
        heappush(hq, -X[j][1]) 
        j += 1
    if len(hq):
        ans += -heappop(hq)

print(ans)

Fixed submission:
import heapq
N,M=map(int, input().split())
X=sorted([list(map(int, input().split())) for _ in range(N)], key=lambda x:x[0])

a=[]
ans, j = 0, 0

for i in range(1, M + 1):
  #M-1~Mから0~MまでのM日間について後ろから考える
  while (j < N) and (X[j][0] <= i):
    #i=1　1日で報酬が受け取れるものを取り出し最大の物をプラス　2日以内で報酬が…の繰り返し
    heapq.heappush(a, -X[j][1])  
    j += 1
  if len(a):
    ans += -heapq.heappop(a)  
    
print(ans)
Buggy python submission (verdict: Runtime Error):
N=int(input())
A=list(map(int,input().split()))

if A[0]-A[1]==1:
  A[0]-=1

for i in range(1,N-1):
  if A[i]-A[i+1]==1:
    A[i]-=1
    if A[i-1]-A[i]==1:
      print('No')
      exit()
 
  elif A[i]-A[i+1]>1:
    print('No')
    exit()
print('Yes')
print(A)

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

for i in range(N-1):
  if A[N-2-i]-A[N-1-i]==1:
    A[N-2-i]-=1
  elif A[N-2-i]-A[N-1-i]>1:
    print('No')
    exit()
print('Yes')
Buggy python submission (verdict: Time Limit Exceeded):
S=input()
l=len(S)
mod=10**9+7
dp=[[0 for j in range(13)] for i in range(l+1)]
dp[0][0]=1

for i in range(l):
  if S[i]=='?':
    for k in range(13): 
      for j in range(10):      
        dp[i+1][(k*10+j)%13]+=dp[i][k]%mod
  else:
    for k in range(13):
      dp[i+1][(k*10 + int(S[i]))%13]+=dp[i][k]%mod
      
print(dp[-1][5]%mod)

Fixed submission:
S=input()
l=len(S)
mod=10**9+7
dp=[[0 for j in range(13)] for i in range(l+1)]
dp[0][0]=1

for i in range(l):
  if S[i]=='?':
    for k in range(13): 
      for j in range(10):      
        dp[i+1][(k*10+j)%13]+=dp[i][k]%mod
  else:
    for k in range(13):
      dp[i+1][(k*10 + int(S[i]))%13]+=dp[i][k]%mod
      
print(dp[-1][5]%mod)
Buggy python submission (verdict: Runtime Error):
N=int(input())
A=list(map(int, input().split()))
A=sorted(A)
if N%3!=0:
  if A==[0]*N:
    print('Yes')
  else:
    print('No')
else:
  B=A[0]+A[1]
  for i in range(N):
    d=B[i]^B[i+1]^B[i+2]
    if d!=0:
      print('No')
      exit()
  print('Yes')

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

a=A[0]
for i in range(N-1):
  a=a^A[i+1]
if a==0:
  print("Yes")
else:
  print("No")
Buggy python submission (verdict: Runtime Error):
N=int(input())
A=list(map(int,input().split()))
S=sum(A)
B=[0]*N
B[0]=S-2*sum(A[1::2])
for i in range(n-1):
    B[i+1]=2*A[i]-B[i]
print(*B)

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

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

import sys
sys.setrecursionlimit(100000)
nCr = {}
def cmb(n, r):
  if r == 0 or r == n: return 1
  if r == 1: return n
  if (n,r) in nCr: return nCr[(n,r)]
  nCr[(n,r)] = cmb(n-1,r) + cmb(n-1,r-1)
  return nCr[(n,r)]

if A==B:
  print(1)
else:
  for i in range(B):
    x=cmb((A-B+1),(i+1))*cmb((B-1),i)
    print(x%(10**9+7))


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

import sys
sys.setrecursionlimit(100000)
nCr = {}
def cmb(n, r):
  if r == 0 or r == n: return 1
  if r == 1: return n
  if (n,r) in nCr: return nCr[(n,r)]
  nCr[(n,r)] = cmb(n-1,r) + cmb(n-1,r-1)
  return nCr[(n,r)]


for i in range(B):
  if i+1>A-B+1:
    print(0)
  else:
    x=cmb((A-B+1),(i+1))*cmb((B-1),i)
    print(x%(10**9+7))
Buggy python submission (verdict: Runtime Error):
N,X=map(int,input().split())
A=list(map(int,input().split()))
D=0
cnt=1
for i in range(X+1):
  D+=A[i]
  if D <= X:
    cnt+=1
  else:
    print(cnt)
    exit()

Fixed submission:
N,X=map(int,input().split())
A=list(map(int,input().split()))
D=0
cnt=1
if sum(A)<= X:
  print(N+1)
  exit()
else:
  for i in range(X+1):
    D+=A[i]
    if D <= X:
      cnt+=1
    else:
      print(cnt)
      exit()
Buggy python submission (verdict: Runtime Error):
N=int(input())
A=[list(map(int,input().split())) for i in range(N)]
B={}
for a,b in A:
  for c,d in A:
    if a>c:
      e=a-c
      f=b-d
    else:
      e=c-a
      f=d-b
    if e!=0 or f!=0:
      if (e,f) in B:
        B[(e,f)]+=1
      else:
        B[(e,f)]=1
        
a=max(B.values())
print(N-a//2)

Fixed submission:
N=int(input())
if N==1:
  print(1)
  exit()
  
A=[list(map(int,input().split())) for i in range(N)]
B={}
for a,b in A:
  for c,d in A:
    e=a-c
    f=b-d
    if e!=0 or f!=0:
      if (e,f) in B:
        B[(e,f)]+=1
      else:
        B[(e,f)]=1
a=max(B.values())
print(N-a)
Buggy python submission (verdict: Time Limit Exceeded):
H,W=map(int,input().split())
S=[input() for _ in range(H)]
ans=0
for i in range(H):
  for j in range(W):
    cnt=1
    a=i
    b=j
    if S[a][b]=='.':
      while a+1 < H and S[a+1][b]=='.':
        cnt+=1
        a+=1
      a=i
      while 0 <= a-1 and S[a-1][b]=='.':
        cnt+=1
        a-=1
      a=i
      while b+1 < W and S[a][b+1]=='.':
        cnt+=1
        b+=1
      b=j
      while 0 <= b-1 and S[a][b-1]=='.':
        cnt+=1
        b-=1
      b=j
    ans=max(cnt,ans)
print(ans)       

Fixed submission:
import numpy as np
H,W=map(int, input().split())
S=np.array([list(input()) for i in range(H)]) == '.'
us=np.zeros((H,W), dtype=int)   
ds=np.zeros((H,W), dtype=int)   
ls=np.zeros((H,W), dtype=int)    
rs=np.zeros((H,W), dtype=int)  

for h in range(1,H):
    us[h, :]=(us[h-1, :]+1) * S[h-1, :]
for h in range(H-2, -1, -1):
    ds[h, :]=(ds[h+1, :]+1) * S[h+1, :]
for w in range(1,W):
    ls[:, w]=(ls[:, w-1]+1) * S[:, w-1]
for w in range(W-2, -1, -1):
    rs[:, w]=(rs[:, w+1]+1) * S[:, w+1]

ans = ((us+ds+ls+rs)*S).max()+1
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
H,W=map(int,input().split())
S=[input() for _ in range(H)]
ans=0
for i in range(H):
  for j in range(W):
    cnt=1
    a=i
    b=j
    if S[a][b]=='.':
      while a+1 < H and S[a+1][b]=='.':
        cnt+=1
        a+=1
      a=i
      while 0 <= a-1 and S[a-1][b]=='.':
        cnt+=1
        a-=1
      a=i
      while b+1 < W and S[a][b+1]=='.':
        cnt+=1
        b+=1
      b=j
      while 0 <= b-1 and S[a][b-1]=='.':
        cnt+=1
        b-=1
      b=j
    ans=max(cnt,ans)
print(ans)       

Fixed submission:
import numpy as np
H,W=map(int, input().split())
S=np.array([list(input()) for i in range(H)]) == '.'
us=np.zeros((H,W), dtype=int)   
ds=np.zeros((H,W), dtype=int)   
ls=np.zeros((H,W), dtype=int)    
rs=np.zeros((H,W), dtype=int)  

for h in range(1,H):
    us[h, :]=(us[h-1, :]+1) * S[h-1, :]
for h in range(H-2, -1, -1):
    ds[h, :]=(ds[h+1, :]+1) * S[h+1, :]
for w in range(1,W):
    ls[:, w]=(ls[:, w-1]+1) * S[:, w-1]
for w in range(W-2, -1, -1):
    rs[:, w]=(rs[:, w+1]+1) * S[:, w+1]

ans = ((us+ds+ls+rs)*S).max()+1
print(ans)
Buggy python submission (verdict: Runtime Error):
L=input()
N=len(L)
dp=[[0,0]for _ in range(N)]
dp[0][0]=1 #以下が確定（0）
dp[0][1]=2 #以下が確定してない（1,0）と逆
mod=10**9+7
for i in range(1,N):
  dp[i][0]+=3*dp[i-1][0]
  dp[i][0]%=mod
  if L[i]=='0':
    dp[i][1]+=dp[i-1][1]
  else:
    dp[i][0]+=dp[i-1][1]　#(両方0)を配給する1パターン
    dp[i][1]+=dp[i-1][1]*2　#（1,0）とその逆
  dp[i][0]%=mod
  dp[i][1]%=mod
print(sum(dp[-1])%mod)

Fixed submission:
L=input()
N=len(L)
dp=[[0,0]for _ in range(N)]
dp[0][0]=1
dp[0][1]=2
mod=10**9+7
for i in range(1,N):
  dp[i][0]+=3*dp[i-1][0]
  dp[i][0]%=mod
  if L[i]=='0':
    dp[i][1]+=dp[i-1][1]
  else:
    dp[i][0]+=dp[i-1][1]
    dp[i][1]+=dp[i-1][1]*2
  dp[i][0]%=mod
  dp[i][1]%=mod
print(sum(dp[-1])%mod)
Buggy python submission (verdict: Runtime Error):
N=int(input())
A=[[]for i in range(N)]
X=[list(map(int, input().split())) for _ in range(N-1)]
for i in range(N-1):
  a=X[i][0]
  b=X[i][1]
  a-=1
  b-=1
  A[a].append(b)
  A[b].append(a)
D=list(map(int, input().split()))
D=sorted(D)[::-1]
from collections import deque
d=deque(D)
E=[-1]*N
def f(now,pre):
  for i in A[now]:
    if i!=pre and E[i]==-1:
      E[i]=d.popleft()
      f(i,now)
E[0]=d.popleft()
f(0,0)
print(sum(D[1:]))
print(*E)

Fixed submission:
import sys 
sys.setrecursionlimit(10**6)
N=int(input())
A=[[]for i in range(N)]
X=[list(map(int, input().split())) for _ in range(N-1)]
for i in range(N-1):
  a=X[i][0]
  b=X[i][1]
  a-=1
  b-=1
  A[a].append(b)
  A[b].append(a)
D=list(map(int, input().split()))
D=sorted(D)[::-1]
from collections import deque
d=deque(D)
E=[-1]*N
def f(now,pre):
  for i in A[now]:
    if i!=pre and E[i]==-1:
      E[i]=d.popleft()
      f(i,now)
E[0]=d.popleft()
f(0,0)
print(sum(D[1:]))
print(*E)
Buggy python submission (verdict: Runtime Error):
import bisect
n,k=map(int, input().split())
V=list(map(int, input().split()))
ans=0
for i in range(k+1):
  for j in range(k+1-i):
    if i+j>n:
      break  
    #手に取りだしたもの
    A=sorted(V[:i]+V[n-j:])
    a=min(n-i-j,bisect.bisect_left(A, 0))
    ans=max(ans,sum(S[a:]))
print(ans)

Fixed submission:
import bisect
n,k=map(int, input().split())
V=list(map(int, input().split()))
ans=0
for i in range(k+1):
  for j in range(k+1-i):
    if i+j>n:
      break  
    #手に取りだしたもの
    A=sorted(V[:i]+V[n-j:])
    a=min(k-i-j,bisect.bisect_left(A, 0))
    ans=max(ans,sum(A[a:]))
print(ans)
Buggy python submission (verdict: Runtime Error):
N=int(input())
A=[list(map(int,input().split())) for _ in range(N-1)]
C=[0]*N
D=[[] for i in range(N)]
for u,v,w in A:
  u-=1
  v-=1
  D[u].append((v,w))
  D[v].append((u,w))

def dfs(n,v,k):
  for i in D[n]:
    if k%2!=0:
      C[n]=1
    if v==i[0]:
      continue
    dfs(i[0],n,k+i[1])       
        
dfs(0,0,0)

for i in C:
  print(i)

Fixed submission:
import sys
sys.setrecursionlimit(10**7)

N=int(input())
A=[list(map(int,input().split())) for _ in range(N-1)]
C=[0]*N
D=[[] for i in range(N)]
for u,v,w in A:
  u-=1
  v-=1
  D[u].append((v,w))
  D[v].append((u,w))

def dfs(n,v,k):
  for i in D[n]:
    if k%2!=0:
      C[n]=1
    if v!=i[0]:
      dfs(i[0],n,k+i[1])       
        
dfs(0,0,0)

for i in C:
  print(i)

Buggy python submission (verdict: Runtime Error):
N=int(input())
A=[list(map(int,input().split())) for _ in range(N-1)]
C=[0]*N
D=[[] for i in range(N)]
for u,v,w in A:
  u-=1
  v-=1
  D[u].append((v,w))
  D[v].append((u,w))

def dfs(n,v,k):
  for i in D[n]:
    if k%2!=0:
      C[n]=1
    if v!=i[0]:
      dfs(i[0],n,k+i[1])       
        
dfs(0,0,0)

for i in C:
  print(i)

Fixed submission:
import sys
sys.setrecursionlimit(10**7)

N=int(input())
A=[list(map(int,input().split())) for _ in range(N-1)]
C=[0]*N
D=[[] for i in range(N)]
for u,v,w in A:
  u-=1
  v-=1
  D[u].append((v,w))
  D[v].append((u,w))

def dfs(n,v,k):
  for i in D[n]:
    if k%2!=0:
      C[n]=1
    if v!=i[0]:
      dfs(i[0],n,k+i[1])       
        
dfs(0,0,0)

for i in C:
  print(i)
Buggy python submission (verdict: Runtime Error):
N,Q=map(int,input().split())
S=input()
A=[list(map(int,input().split())) for i in range(Q)]
X=[0]*(N+1)
cnt=1
for i in range(N): 
  if S[i]=='A' and S[i+1]=='C':
    X[i+1]=cnt
    cnt+=1
  else:
    X[i+1]=cnt
    
for i in range(Q):
  a=A[i][0]
  b=A[i][1]
  print(X[b]-X[a])

Fixed submission:
N,Q=map(int,input().split())
S=input()
A=[list(map(int,input().split())) for i in range(Q)]

X=[0]*(N)
cnt=0
for i in range(N-1): 
  if S[i]=='A' and S[i+1]=='C':
    cnt+=1
    X[i+1]=cnt
  else:
    X[i+1]=cnt
    
for i in range(Q):
  a=A[i][0]-1
  b=A[i][1]-1
  print(X[b]-X[a])

Buggy python submission (verdict: Time Limit Exceeded):
N,Q=map(int,input().split())
S=input()
A=[list(map(int,input().split())) for i in range(Q)]
X=[0]*(N+1)
for i in range(N-1):
  if S[i]=='A':
    if S[i+1]=='C':
      X[i+1]=1
for i in range(Q):
  a=A[i][0]
  b=A[i][1]
  print(sum(X[a:b]))

Fixed submission:
N,Q=map(int,input().split())
S=input()
A=[list(map(int,input().split())) for i in range(Q)]

X=[0]*(N)
cnt=0
for i in range(N-1): 
  if S[i]=='A' and S[i+1]=='C':
    cnt+=1
    X[i+1]=cnt
  else:
    X[i+1]=cnt
    
for i in range(Q):
  a=A[i][0]-1
  b=A[i][1]-1
  print(X[b]-X[a])
Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
mod=10**9+7
memo=[{} for _ in range(N+1)]

def ok(x, y, z, nx):
  if y=='A' and z=='G' and nx=='C':
    return False
  if x=='A' and z=='G' and nx=='C':
    return False
  if y=='G' and z=='A' and nx=='C':
    return False
  if y=='A' and z=='C' and nx=='G':
    return False
  if x=='A' and y=='G' and nx=='C':
    return False
  return True

def f(num,A):
  if num==N:
    return 1
  else:
    x,y,z=A[0],A[1],A[2]
    if (x,y,z) in memo[num]:
      return  memo[num][(x,y,z)]
    else:
      s=0
      for i in ['A','C','G','T']:
        if ok(x,y,z,i):
          s+=f(num+1,(y,z,i))
      #memo[num][(x,y,z)]=s%mod
      return s%mod
print(f(0,'ZZZ'))


Fixed submission:
N=int(input())
mod=10**9+7
memo=[{} for _ in range(N+1)]

def ok(x,y,z,nx):
  if y=='A' and z=='G' and nx=='C':
    return False
  if x=='A' and z=='G' and nx=='C':
    return False
  if y=='G' and z=='A' and nx=='C':
    return False
  if y=='A' and z=='C' and nx=='G':
    return False
  if x=='A' and y=='G' and nx=='C':
    return False
  return True

def dfs(idx,lis):
    if idx==N:
      return 1
    x,y,z=lis[0],lis[1],lis[2]
    if (x,y,z) in memo[idx]:
        return memo[idx][(x,y,z)]
    ret=0
    for nx in ['A','G','C','T']:
        if ok(x,y,z,nx):
            ret+=dfs(idx+1,(y,z,nx))
    memo[idx][(x,y,z)]=ret%mod
    return ret%mod

print(dfs(0,'DDD'))
Buggy python submission (verdict: Runtime Error):
N=int(input())
A=[int(input()) for _ in range(N)]
mod=10**9+7
B=[A[0]-1]
for i in range(1,N):
  if A[i]!=A[i-1]:
    B.append(A[i]-1)
n=len(B)
used=[-1]*N
used[B[0]]=0
dp=[0]*n
dp[0]=1
for i in range(1,n):
  if used[B[i]]==-1:
    dp[i]=dp[i-1]
  else:
    a=used[B[i]]
    dp[i]=(dp[i-1]+dp[a])%mod
  used[B[i]]=i
print(dp[-1])

Fixed submission:
N=int(input())
A=[int(input()) for _ in range(N)]
mod=10**9+7
B=[A[0]-1]
for i in range(1,N):
  if A[i]!=A[i-1]:
    B.append(A[i]-1)
n=len(B)
used=[-1]*(max(A)+1)
used[B[0]]=0
dp=[0]*n
dp[0]=1
for i in range(1,n):
  if used[B[i]]==-1:
    dp[i]=dp[i-1]
  else:
    a=used[B[i]]
    dp[i]=(dp[i-1]+dp[a])%mod
  used[B[i]]=i
print(dp[-1])