Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
n,x,y=map(int,input().split())
g=[[]*n for i in range(n)]
for i in range(n-1):
    g[i].append(i+1)
    g[i+1].append(i)
g[x-1].append(y-1)
g[y-1].append(x-1)

from collections import deque
distance=[]

for i in range(n):
    option=deque()
    option.append(i)
    completed=[False]*n
    memo=[0]*n
    while option:
        now=option.popleft()
        completed[now]=True
        for j in g[now]:
            if completed[j]==False and j not in option:
                memo[j]=memo[now]+1
                option.append(j)
    distance.append(memo)

ans=[0]*n
for i in range(n-1):
    for j in range(i+1,n):
        ans[distance[i][j]-1]+=1

for i in range(n-1):
    print(ans[i])
        

Fixed submission:
import heapq
import sys

input = sys.stdin.readline

def dijkstra_heap(s,edge):
    #始点sから各頂点への最短距離
    d = [10**20] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d

################################
n,s,t = map(int,input().split()) #n:頂点数　w:辺の数
w=n-1

edge = [[] for i in range(n)]
#edge[i] : iから出る道の[重み,行先]の配列
for i in range(w):
    x,y=i,i+1 #0-indexed
    edge[x].append([1,y])
    edge[y].append([1,x]) 
edge[s-1].append([1,t-1])
edge[t-1].append([1,s-1]) 

distance=dijkstra_heap(0,edge)
memo=[0]*n

for i in range(n-1):#i to j
    for j in range(i+1,n):
        if s-1<i<t-1:#s==2,t==4
            tmp=min(j-i,distance[i]+distance[j]-distance[s-1]*2)
        else:
            tmp=distance[j]-distance[i]

        memo[tmp]+=1
for i in range(1,n):
    print(memo[i])
Buggy python submission (verdict: Runtime Error):
a=list(map(int,input().split()))
import test
test.solve(a)

Fixed submission:
a=list(map(int,input().split()))
a=set(a)
if len(a)==2:
    print('Yes')
else:
    print('No')
Buggy python submission (verdict: Time Limit Exceeded):
n,k=map(int,input().split())
a=list(map(int,input().split()))
a=[(1+i)/2 for i in a]
b=[0]*(n-k+1)
for i in range(n-k+1):
    b[i]=(sum(a[i:i+k]))
print(max(b))

Fixed submission:
n,k=map(int,input().split())
a=list(map(int,input().split()))
#a=[(1+i)/2 for i in a]
import itertools
ac=itertools.accumulate(a)
ac=list(ac)

ans=0
for i in range(k-1,n):
    if i-k>=0:
        tmp=ac[i]-ac[i-k]
    else:
        tmp=ac[i]
    ans=max(ans,tmp)

print((ans+k)/2)
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    import sys
    input=sys.stdin.readline
    h,n=map(int,input().split())
    a=[[int(i) for i in input().split()]for i in range(n)]
    
    dp=[float('inf')]*(h+1) #0-9
    dp[0]=0
    mini=float('inf')
    for i in range(h+1):
        if dp[i]==float('inf'):
            continue
        for ata,mp in a:
            if i+ata>=h:
                tmp=dp[i]+mp
                mini=min(mini,tmp)
                continue
            dp[i+ata]=min(dp[i+ata],dp[i]+mp)
    print(mini)

if __name__=='__main__':
    main()

Fixed submission:

h,n=map(int,input().split())
a=[[int(i) for i in input().split()]for i in range(n)]
inf=10**9
dp=[inf]*(h+1) #0-9
dp[0]=0
mini=inf
for i in range(h+1):
    if dp[i]==inf:
        continue
    for ata,mp in a:
        if i+ata>=h:
            tmp=dp[i]+mp
            mini=min(mini,tmp)
            continue
        dp[i+ata]=min(dp[i+ata],dp[i]+mp)
print(mini)

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    import sys
    input=sys.stdin.readline
    h,n=map(int,input().split())
    a=[[int(i) for i in input().split()]for i in range(n)]
    
    dp=[float('inf')]*(h+1) #0-9
    dp[h]=0
    mini=float('inf')
    for i in reversed(range(0,h+1)):
        if dp[i]==float('inf'):
            continue
        for ata,mp in a:
            if i-ata<=0:
                tmp=dp[i]+mp
                mini=min(mini,tmp)
                continue
            dp[i-ata]=min(dp[i-ata],dp[i]+mp)
    print(mini)

if __name__=='__main__':
    main()

Fixed submission:

h,n=map(int,input().split())
a=[[int(i) for i in input().split()]for i in range(n)]
inf=10**9
dp=[inf]*(h+1) #0-9
dp[0]=0
mini=inf
for i in range(h+1):
    if dp[i]==inf:
        continue
    for ata,mp in a:
        if i+ata>=h:
            tmp=dp[i]+mp
            mini=min(mini,tmp)
            continue
        dp[i+ata]=min(dp[i+ata],dp[i]+mp)
print(mini)

Buggy python submission (verdict: Time Limit Exceeded):
h,n=map(int,input().split())
a=[[int(i) for i in input().split()]for i in range(n)]

dp=[float('inf')]*(h+1) #0-9
dp[h]=0
mini=float('inf')
for i in reversed(range(0,h+1)):
    if dp[i]==float('inf'):
        continue
    for ata,mp in a:
        if i-ata<=0:
            tmp=dp[i]+mp
            mini=min(mini,tmp)
            continue
        dp[i-ata]=min(dp[i-ata],dp[i]+mp)
print(mini)

Fixed submission:

h,n=map(int,input().split())
a=[[int(i) for i in input().split()]for i in range(n)]
inf=10**9
dp=[inf]*(h+1) #0-9
dp[0]=0
mini=inf
for i in range(h+1):
    if dp[i]==inf:
        continue
    for ata,mp in a:
        if i+ata>=h:
            tmp=dp[i]+mp
            mini=min(mini,tmp)
            continue
        dp[i+ata]=min(dp[i+ata],dp[i]+mp)
print(mini)
Buggy python submission (verdict: Runtime Error):
a=input()
n=len(a)
if n%2==0:
    a1=a[:n//2]
    a2=a[n//2:]
else:
    a1=a[:n//2]
    a2=a[(n//2)+1:]
cnt=0
for x,i in enumerate(a1):
    if i!=a2[-x+1]:
        cnt+=1
print(cnt)

Fixed submission:
a=input()
n=len(a)
if len(a)%2==0:
    a1=a[:n//2]
    a2=a[n//2:]
    a2=a2[::-1]
else:
    a1=a[:n//2]
    a2=a[n//2+1:]
    a2=a2[::-1]
cnt=0
for i in range(len(a1)):
    if a1[i]!=a2[i]:
        cnt+=1
print(cnt)
Buggy python submission (verdict: Runtime Error):
x=int(input())
if x<=99:
    print(0)
    exit()
dp=[0]*(x+1)
for i in range(100):
    dp[i]=0
for i in range(100,106):
    dp[i]=1
for i in range(106,x+1):
    if dp[i-100]==1 or dp[i-101]==1 or dp[i-102]==1 or dp[i-103]==1 or dp[i-104]==1 or dp[i-105]==1:
        dp[i]=1
print(dp[-1])

Fixed submission:
x=int(input())
if x<=99:
    print(0)
    exit()
if x<=105:
    print(1)
    exit()
dp=[0]*(x+1)
for i in range(100):
    dp[i]=0
for i in range(100,106):
    dp[i]=1
for i in range(106,x+1):
    if dp[i-100]==1 or dp[i-101]==1 or dp[i-102]==1 or dp[i-103]==1 or dp[i-104]==1 or dp[i-105]==1:
        dp[i]=1
print(dp[-1])
Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
a=list(map(int,input().split()))
for i in range(1,n+1):
    print(a.index(i)+1,end=" ")

Fixed submission:
n=int(input())
a=list(map(int,input().split()))
b={}
cnt=1;
for i in a:
    b[i]=cnt
    cnt+=1
for i in range(1,n+1):
    print(b[i], end=" ")

Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
a=list(map(int,input().split()))
for i in range(1,n+1):
    b=a.index(i)+1
    print(b,end=" ")

Fixed submission:
n=int(input())
a=list(map(int,input().split()))
b={}
cnt=1;
for i in a:
    b[i]=cnt
    cnt+=1
for i in range(1,n+1):
    print(b[i], end=" ")

Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
a=list(map(int,input().split()))
for i in range(1,n+1):
    b=a.index(i)+1
    print(b,end=" ")

Fixed submission:
n=int(input())
a=list(map(int,input().split()))
b={}
cnt=1;
for i in a:
    b[i]=cnt
    cnt+=1
for i in range(1,n+1):
    print(b[i], end=" ")
Buggy python submission (verdict: Time Limit Exceeded):
n,k,q=(map(int,input().split()))
l=[int(input()) for i in range(q)]
y=k-q
for i in range(1,n+1):
    print("Yes" if y+l.count(i)>0 else "No")

Fixed submission:
n,k,q=map(int, input().split())
p=[-q+k]*n
for i in range(0,q):
    p[int(input())-1]+=1
for i in range(0,n):
    print("Yes" if p[i]>0 else "No")

Buggy python submission (verdict: Time Limit Exceeded):
n,k,q=(map(int,input().split()))
l=[int(input()) for i in range(q)]
x=len(l)
for i in range(1,n+1):
    print("Yes" if k-(x-l.count(i))>0 else "No")

Fixed submission:
n,k,q=map(int, input().split())
p=[-q+k]*n
for i in range(0,q):
    p[int(input())-1]+=1
for i in range(0,n):
    print("Yes" if p[i]>0 else "No")

Buggy python submission (verdict: Time Limit Exceeded):
n,k,q=(map(int,input().split()))
l=[int(input()) for i in range(q)]
for i in range(1,n+1):
    print("Yes" if k-(len(l)-l.count(i))>0 else "No")

Fixed submission:
n,k,q=map(int, input().split())
p=[-q+k]*n
for i in range(0,q):
    p[int(input())-1]+=1
for i in range(0,n):
    print("Yes" if p[i]>0 else "No")

Buggy python submission (verdict: Time Limit Exceeded):
n,k,q=(map(int,input().split()))
l=[int(input()) for i in range(q)]
for i in range(1,n+1):
    print("Yes" if k-(len(l)-l.count(i))>0 else "No")

Fixed submission:
n,k,q=map(int, input().split())
p=[-q+k]*n
for i in range(0,q):
    p[int(input())-1]+=1
for i in range(0,n):
    print("Yes" if p[i]>0 else "No")
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    n,q=map(int,input().split())
    a=[[None for i in range(n)]for i in range(n)]
    for i in range(n-1):
        x,y=map(int,input().split())
        a[x-1][y-1]=True
        a[y-1][x-1]=True
    cnt=[0]*n
    for i in range(q):
        x,y=map(int,input().split())
        cnt[x-1]+=y
    
    from collections import deque 
    d=deque()
    d.append(0)
    completed=[False]*n
    
    while d:
        now=d.popleft()
        completed[now]=True
        for x,aa in enumerate(a[now]):
            if aa==True and completed[x]==False:
                cnt[x]+=cnt[now]
                d.append(x)
    print(*cnt)

if __name__=="__main__":
    main()

Fixed submission:
def main():
    n,q=map(int,input().split())
    from collections import deque,defaultdict
    dic=defaultdict(list)
    for i in range(n-1):
        x,y=map(int,input().split())
        dic[x-1].append(y-1)
        dic[y-1].append(x-1)
    cnt=[0]*n
    for i in range(q):
        x,y=map(int,input().split())
        cnt[x-1]+=y
    
    d=deque()
    d.append(0)
    completed=[False]*n
    while d:
        now=d.popleft()
        completed[now]=True
        for x in dic[now]:
            if completed[x]==False:
                cnt[x]+=cnt[now]
                d.append(x)
    print(*cnt)

if __name__=="__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
a=[input().split() for i in range(n)]
import collections as c
import itertools
d=list(itertools.combinations(range(n),2))
cnt=0
for i in d:
    x=c.Counter(a[i[0]][0])
    y=c.Counter(a[i[1]][0])
    if x==y:
        cnt+=1
print(cnt)

Fixed submission:
n=int(input())
import math
d={}
for i in range(n):
    a="".join(sorted(input()))
    if a not in d:
        d[a]=1
    else:
        d[a]+=1
ans=0
for i in d.values():
  ans+=i*(i-1)//2
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
a=[input().split() for i in range(n)]
import collections as c
import itertools
d=list(itertools.combinations(range(n),2))
cnt=0
for i in d:
    x=c.Counter(a[i[0]][0])
    y=c.Counter(a[i[1]][0])
    if x==y:
        cnt+=1
print(cnt)

Fixed submission:
n=int(input())
import math
d={}
for i in range(n):
    a="".join(sorted(input()))
    if a not in d:
        d[a]=1
    else:
        d[a]+=1
ans=0
for i in d.values():
  ans+=i*(i-1)//2
print(ans)
Buggy python submission (verdict: Runtime Error):
a,b,c,d=map(int,input().split())
import math
cc=b//c-(a-1)//c
dd=b//d-(a-1)//d
gcd=math.gcd(c,d)
lcm=c*d//gcd
cd=b//lcm-(a-1)//lcm
print((b-a+1)-(cc+dd-cd))

Fixed submission:
a,b,c,d=map(int,input().split())
import fractions as f
cc=b//c-(a-1)//c
dd=b//d-(a-1)//d
gcd=f.gcd(c,d)
lcm=c*d//gcd
cd=b//lcm-(a-1)//lcm
print((b-a+1)-(cc+dd-cd))

Buggy python submission (verdict: Runtime Error):
a,b,c,d=map(int,input().split())
import math
cc=b//c-(a-1)//c
dd=b//d-(a-1)//d
gcd=math.gcd(c,d)
lcm=c*d//gcd
cd=b//lcm-a//lcm
print((b-a+1)-(cc+dd-cd))


Fixed submission:
a,b,c,d=map(int,input().split())
import fractions as f
cc=b//c-(a-1)//c
dd=b//d-(a-1)//d
gcd=f.gcd(c,d)
lcm=c*d//gcd
cd=b//lcm-(a-1)//lcm
print((b-a+1)-(cc+dd-cd))

Buggy python submission (verdict: Runtime Error):
a,b,c,d=map(int,input().split())
import math
cc=b//c-(a-1)//c
dd=b//d-(a-1)//d
gcd=math.gcd(c,d)
lcm=c*d//gcd
cd=b//lcm-a//lcm
print((b-a+1)-(cc+dd-cd))

Fixed submission:
a,b,c,d=map(int,input().split())
import fractions as f
cc=b//c-(a-1)//c
dd=b//d-(a-1)//d
gcd=f.gcd(c,d)
lcm=c*d//gcd
cd=b//lcm-(a-1)//lcm
print((b-a+1)-(cc+dd-cd))

Buggy python submission (verdict: Runtime Error):
a,b,c,d=map(int,input().split())
import math
cc=b//c-(a-1)//c
dd=b//d-(a-1)//d
gcd=math.gcd(c,d)
lcm=c*d//gcd
cd=b//lcm-a//lcm
print((b-a+1)-(cc+dd-cd))

Fixed submission:
a,b,c,d=map(int,input().split())
import fractions as f
cc=b//c-(a-1)//c
dd=b//d-(a-1)//d
gcd=f.gcd(c,d)
lcm=c*d//gcd
cd=b//lcm-(a-1)//lcm
print((b-a+1)-(cc+dd-cd))
Buggy python submission (verdict: Runtime Error):
n=int(input())
x=[0]*n
y=[0]*n

for i in range(n):
    x[i],y[i]=map(int,input().split())
dis=[]
for i in range(n-1):
    for j in range(i+1,n):
        dis.append((x[j]-x[i],y[j]-y[i]))
        
from collections import Counter
c=Counter(dis).most_common()[0]
print(n-c[1])


Fixed submission:
n=int(input())
if n==1:
    print(1)
    exit()
    
x=[0]*n
y=[0]*n

for i in range(n):
    x[i],y[i]=map(int,input().split())
dis=[]
for i in range(n):
    for j in range(n):
        if i==j:
            continue
        dis.append((x[j]-x[i],y[j]-y[i]))
        
from collections import Counter
c=Counter(dis).most_common()[0]
print(n-c[1])

Buggy python submission (verdict: Runtime Error):
n=int(input())
a=[[int(i) for i in input().split()] for i in range(n)]
x_dis=[0]*(n-1)
y_dis=[0]*(n-1)

for i in range(n-1):
    x_dis[i]=a[i+1][0]-a[i][0]
    y_dis[i]=a[i+1][1]-a[i][1]

import collections

cx=collections.Counter(x_dis).most_common()[0]
cy=collections.Counter(y_dis).most_common()[0]

print(n-min(cx[1],cy[1]))

Fixed submission:
n=int(input())
if n==1:
    print(1)
    exit()
    
x=[0]*n
y=[0]*n

for i in range(n):
    x[i],y[i]=map(int,input().split())
dis=[]
for i in range(n):
    for j in range(n):
        if i==j:
            continue
        dis.append((x[j]-x[i],y[j]-y[i]))
        
from collections import Counter
c=Counter(dis).most_common()[0]
print(n-c[1])
Buggy python submission (verdict: Time Limit Exceeded):
s=list(input())
n=len(s)

cnt=0
i=0
while i<n-2:
    if s[i]=="A" and s[i+1]=="B" and s[i+2]=="C":
        s[i]="B"
        s[i+1]="C"
        s[i+2]="A"
        cnt+=1
        if i!=0:
            i-=1
    else:
        i+=1

print(cnt)

Fixed submission:
s=input()
n=len(s)

cnt=0
ans=0

for i in range(n-1):
    if s[i]=="A":
        cnt+=1
    elif s[i:i+2]=="BC":
        ans+=cnt
    elif i>0 and s[i-1:i+1]=="BC":
        pass
    else:
        cnt=0

print(ans)
Buggy python submission (verdict: Runtime Error):
cnt=0
for i in range(len(n)):
    if n[0]==0:
        if i%2==0 and n[i]!=0 :
            cnt+=1
        if i&2==1 and n[i]!=1 :
            cnt+=1
    else:
        if i%2==0 and n[i]!=1 :
            cnt+=1
        if i&2==1 and n[i]!=0 :
            cnt+=1
print(cnt-1)

Fixed submission:
n=input()
cnt=0
for i in range(len(n)):
    if n[0]=="0":
        if i%2==0 and n[i]=="1" :
            cnt+=1
        if i%2==1 and n[i]=="0" :
            cnt+=1
    else:
        if i%2==0 and n[i]=="0" :
            cnt+=1
        if i%2==1 and n[i]=="1" :
            cnt+=1
print(cnt)
Buggy python submission (verdict: Runtime Error):
n,q=map(int,input().split())
a=input()
l=[[int(i) for i in input().split()]for i in range(q)]
ac=[]
for x,aa in enumerate(a):
    if aa=="A" and a[x+1]=="C":
        ac.append(x+1)
ac=set(ac)
for i in l:
    cnt=0
    for j in ac:
        if i[0]<=j<i[1]:
            cnt+=1
    print(cnt)

Fixed submission:
n,q=map(int,input().split())
s=input()
b=[0]*(n+1)
y=0
for x,i in enumerate(s):
    if i=="A" and x!=n-1 and s[x+1]=="C":
        y+=1
    b[x+1]=y
for i in range(q):
    a0,a1=map(int,input().split())
    print(b[a1-1]-b[a0-1])

Buggy python submission (verdict: Time Limit Exceeded):
n,q=map(int,input().split())
s=input()
b=[]
x=0
for i in range(10**5):
    ind=s.find("AC",x)
    if ind==-1:
        break
    b.append(ind+1)
    x=ind+1
for i in range(q):
    cnt=0
    a=list(map(int,input().split()))
    for j in b:
        if a[0]<=j<a[1]:
            cnt+=1
    print(cnt)

Fixed submission:
n,q=map(int,input().split())
s=input()
b=[0]*(n+1)
y=0
for x,i in enumerate(s):
    if i=="A" and x!=n-1 and s[x+1]=="C":
        y+=1
    b[x+1]=y
for i in range(q):
    a0,a1=map(int,input().split())
    print(b[a1-1]-b[a0-1])

Buggy python submission (verdict: Time Limit Exceeded):
n,q=map(int,input().split())
s=input()
b=[]
x=0
for i in range(10**5):
    ind=s.find("AC",x)
    if ind==-1:
        break
    b.append(ind+1)
    x=ind+1
for i in range(q):
    cnt=0
    a=list(map(int,input().split()))
    for j in b:
        if a[0]<=j<a[1]:
            cnt+=1
    print(cnt)

Fixed submission:
n,q=map(int,input().split())
s=input()
b=[0]*(n+1)
y=0
for x,i in enumerate(s):
    if i=="A" and x!=n-1 and s[x+1]=="C":
        y+=1
    b[x+1]=y
for i in range(q):
    a0,a1=map(int,input().split())
    print(b[a1-1]-b[a0-1])

Buggy python submission (verdict: Time Limit Exceeded):
n,q=map(int,input().split())
s=input()
for i in range(q):
    a=list(map(int,input().split()))
    print(s.count('AC',a[0]-1,a[1]))

Fixed submission:
n,q=map(int,input().split())
s=input()
b=[0]*(n+1)
y=0
for x,i in enumerate(s):
    if i=="A" and x!=n-1 and s[x+1]=="C":
        y+=1
    b[x+1]=y
for i in range(q):
    a0,a1=map(int,input().split())
    print(b[a1-1]-b[a0-1])

Buggy python submission (verdict: Time Limit Exceeded):
n,q=map(int,input().split())
s=input()
for i in range(q):
    a=list(map(int,input().split()))
    print(s.count('AC',a[0]-1,a[1]))

Fixed submission:
n,q=map(int,input().split())
s=input()
b=[0]*(n+1)
y=0
for x,i in enumerate(s):
    if i=="A" and x!=n-1 and s[x+1]=="C":
        y+=1
    b[x+1]=y
for i in range(q):
    a0,a1=map(int,input().split())
    print(b[a1-1]-b[a0-1])
Buggy python submission (verdict: Runtime Error):
a,b,c=map(int, input().split())
al=[]
bl=[]
for i in range(1,a+1):
    if a%i==0:
        al.append(i)
for i in range(1,b+1):
    if b%i==0:
        bl.append(i))
co=sorted(list(set(al)&set(bl)))
print(co[-c])

Fixed submission:
a,b,c=map(int, input().split())
al=[]
bl=[]
for i in range(1,a+1):
    if a%i==0:
        al.append(i)
for i in range(1,b+1):
    if b%i==0:
        bl.append(i)
co=sorted(list(set(al)&set(bl)))
print(co[-c])
Buggy python submission (verdict: Runtime Error):
n=input()
s=len(n)
if s%2==0:
    l0=n[:s//2].count("0")
    l1=s//2-l0
    r0=n[s//2:].count("0")
    r1=s//2-r0
    print(min(l0,r1)*2+min(l1,r0)*2)
if s%2==1:
    l0=n[:s//2].count("0")
    l1=s//2-l0
    r0=n[s//2+1:].count("0")
    r1=s//2-r0
    tmp=min(l0,r1)*2+min(l1,r0)*2
    if n[s//2]=="0":
        if ri-l0>0 or r0-l1>0:
            tmp+=2
    else:
        if l0-r1>0 or l1-r0>0:
            tmp+=2
    print(tmp)

Fixed submission:
n=input()
s=len(n)
if s%2==0:
    l0=n[:s//2].count("0")
    l1=s//2-l0
    r0=n[s//2:].count("0")
    r1=s//2-r0
    print(min(l0,r1)*2+min(l1,r0)*2)
if s%2==1:
    l0=n[:s//2].count("0")
    l1=s//2-l0
    r0=n[s//2+1:].count("0")
    r1=s//2-r0
    tmp=min(l0,r1)*2+min(l1,r0)*2
    if n[s//2]=="0":
        if r1-l0>0 or r0-l1>0:
            tmp+=2
    else:
        if l0-r1>0 or l1-r0>0:
            tmp+=2
    print(tmp)
Buggy python submission (verdict: Runtime Error):
n=int(input())
a=list(map(int,input().split()))
import math
mini=float('inf')
for i in range(n-1):
    x=math.gcd(a[i],a[i+1])
    mini=min(mini,x)
print(mini)

Fixed submission:
n=int(input())
a=list(map(int,input().split()))
import fractions as f
mini=float('inf')
for i in range(n-1):
    x=f.gcd(a[i],a[i+1])
    mini=min(mini,x)
print(mini)
Buggy python submission (verdict: Time Limit Exceeded):
n,k=map(int,input().split())
a=list(map(int,input().split()))
dp=[float('inf')]*n
dp[0]=0
for i in range(0,n):
    for j in range(1,k+1):
        if i+j>n-1:
            continue
        dp[i+j]=min(dp[i+j],dp[i]+abs(a[i]-a[i+j]))
print(dp[-1])

Fixed submission:
n,k=map(int,input().split())
a=list(map(int,input().split()))
dp=[float('inf')]*n
dp[0]=0
for i in range(0,n):
    for j in range(1,k+1):
        if i+j>n-1:
            continue
        dp[i+j]=min(dp[i+j],dp[i]+abs(a[i]-a[i+j]))
print(dp[-1])

Buggy python submission (verdict: Time Limit Exceeded):
n,k=map(int,input().split())
a=list(map(int,input().split()))
dp=[float('inf')]*n
dp[0]=0
for i in range(0,n):
    for j in range(1,k+1):
        if i+j>n-1:
            continue
        tmp=dp[i]+abs(a[i]-a[i+j])
        dp[i+j]=min(dp[i+j],tmp)
print(dp[-1])

Fixed submission:
n,k=map(int,input().split())
a=list(map(int,input().split()))
dp=[float('inf')]*n
dp[0]=0
for i in range(0,n):
    for j in range(1,k+1):
        if i+j>n-1:
            continue
        dp[i+j]=min(dp[i+j],dp[i]+abs(a[i]-a[i+j]))
print(dp[-1])
Buggy python submission (verdict: Runtime Error):
def knapsack(N,W,weight,value):
    #初期化
    inf=float("inf")
    dp=[[-inf for i in range(W+1)] for j in range(N+1)]
    for i in range(W+1): 
        dp[0][i]=0
    #DP
    for i in range(N):
        for w in range(W+1):
            if weight[i]<=w: #dp[i][w-weight[i]の状態にi番目の荷物が入る可能性がある
                dp[i+1][w]=max(dp[i][w-weight[i]]+value[i], dp[i][w])
            else: #入る可能性はない
                dp[i+1][w]=dp[i][w]
    return dp[N][W]

n,w=map(int,input().split())
weight=[0]*n
value=[0]*n
for i in range(n):
    weight[i],value[i]=map(int,input().split())

print(knapsack(n,w,a,b))

Fixed submission:
n,w=map(int,input().split())
a=[[int(i) for i in input().split()]for i in range(n)]
dp=[[0 for i in range(w+1)]for i in range(n+1)]
for i in range(n):
    for sum_w in range(1,w+1):
        if sum_w-a[i][0]>=0:
            dp[i+1][sum_w]=max(dp[i][sum_w],dp[i][sum_w-a[i][0]]+a[i][1])
        else:
            dp[i+1][sum_w]=dp[i][sum_w]
print(dp[n][w])

Buggy python submission (verdict: Time Limit Exceeded):
n,w=map(int,input().split())
a=[[int(i) for i in input().split()]for i in range(n)]
dp=[[0 for i in range(w+1)]for i in range(n+1)]
for i in range(n):
    for sum_w in range(1,w+1):
        if sum_w-a[i][0]>=0:
            dp[i+1][sum_w]=max(dp[i][sum_w],dp[i][sum_w-a[i][0]]+a[i][1])
        else:
            dp[i+1][sum_w]=dp[i][sum_w]
print(dp[n][w])

Fixed submission:
n,w=map(int,input().split())
a=[[int(i) for i in input().split()]for i in range(n)]
dp=[[0 for i in range(w+1)]for i in range(n+1)]
for i in range(n):
    for sum_w in range(1,w+1):
        if sum_w-a[i][0]>=0:
            dp[i+1][sum_w]=max(dp[i][sum_w],dp[i][sum_w-a[i][0]]+a[i][1])
        else:
            dp[i+1][sum_w]=dp[i][sum_w]
print(dp[n][w])