Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
a,b,n=map(int,input().split())

def f(a,b,x):
    return (a*x)//b - a*(x//b)

print(f(min(b-1,n)))

Fixed submission:
a,b,n=map(int,input().split())

def f(x):
    return (a*x)//b - a*(x//b)

print(f(min(b-1,n)))

Buggy python submission (verdict: Time Limit Exceeded):
a,b,n=map(int,input().split())
ans=0
x=0
y=0
# while(x<=n or y<=n):
#     ans=max(ans,((a*x)//b - a*(x//b)),((a*y)//b - a*(y//b)))
#     x+=b
#     y=-(-x//a)

for i in range(n+1):
    ans=max(ans,((a*i)//b - a*(i//b)))
print(ans)


Fixed submission:
a,b,n=map(int,input().split())

def f(x):
    return (a*x)//b - a*(x//b)

print(f(min(b-1,n)))

Buggy python submission (verdict: Time Limit Exceeded):
a,b,n=map(int,input().split())
ans=0
x=0
y=0
while(x<=n or y<=n):
    ans=max(ans,((a*x)//b - a*(x//b)),((a*y)//b - a*(y//b)))
    x+=b
    y=-(-x//a)
print(ans)


Fixed submission:
a,b,n=map(int,input().split())

def f(x):
    return (a*x)//b - a*(x//b)

print(f(min(b-1,n)))

Buggy python submission (verdict: Time Limit Exceeded):
a,b,n=map(int,input().split())
ans=0
x=0
while(x<=n or -(-x//a)<=n):
    ans=max(ans,((a*x)//b - a*(x//b)))
    y=-(-x//a)
    ans=max(ans,((a*y)//b - a*(y//b)))
    x+=b
print(ans)


Fixed submission:
a,b,n=map(int,input().split())

def f(x):
    return (a*x)//b - a*(x//b)

print(f(min(b-1,n)))
Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
s=input()

def restword(a,b):
    w=[a,b]
    if('R' not in w):
        return 'R'
    elif('G' not in w):
        return 'G'
    else:
        return 'B'

ans=0
for i in range(n):
    for j in range(i+1,n):
        if(s[i]!=s[j]):
            sk=s[j+1:]
            rest_k=restword(s[i], s[j])
            ans_k=sk.count(rest_k)
            if(j+j-i < n and s[j+j-i]==rest_k):
                ans_k-=1
            ans+=ans_k
        else:
            continue

print(ans)

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

r=list(s).count('R')
g=list(s).count('G')
b=list(s).count('B')

ans=r*g*b
for i in range(n):
    for j in range(i+1,n):
        k=j+(j-i)
        if(k<n and s[i]!=s[j] and s[j]!=s[k] and s[k]!=s[i]):
#            print(i,j,k)
            ans-=1
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
s=input()

ans=0
for i in range(n):
    for j in range(i+1,n):
        if(s[i]!=s[j]):
            for k in range(j+1,n):
                if(k==j+j-i):
                    continue
                elif(s[i]!=s[k] and s[j]!=s[k]):
                    ans+=1
        else:
            continue

print(ans)

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

r=list(s).count('R')
g=list(s).count('G')
b=list(s).count('B')

ans=r*g*b
for i in range(n):
    for j in range(i+1,n):
        k=j+(j-i)
        if(k<n and s[i]!=s[j] and s[j]!=s[k] and s[k]!=s[i]):
#            print(i,j,k)
            ans-=1
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n,x,y=map(int,input().split())
ans=[0 for _ in range(n+1)]
d=[]
for i in range(n+1):
    d.append([abs(i-j) for j in range(n+1)])
#    print(d[i])
d[x][y]=1
d[y][x]=1

for i in range(1,n+1):
    for j in range(i+1,n+1):
        d[i][j]=min(d[i][j],d[i][x]+d[x][y]+d[y][j],d[i][y]+d[y][x]+d[x][j])
        ans[d[i][j]]+=1

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

Fixed submission:
n,x,y=map(int,input().split())
ans=[0 for _ in range(n+1)]
for i in range(1,n+1):
    for j in range(i+1,n+1):
        ans[min(abs(j-i),abs(x-i)+1+abs(y-j),abs(y-i)+1+abs(j-x))]+=1

for i in range(1,n):
    print(ans[i])
Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
h,w=map(int,input().split())
s=[]
for i in range(h):
    s.append(list(input()))

dp=[[99999999 for i in range(w)] for i in range(h)]

q=deque()
#i,j,ans
q.append([0,0,0])

while(len(q)>0):
    i,j,ans=q.popleft()

    if(s[i][j]=='#'):
        ans+=1

    if(dp[i][j]>ans):
        dp[i][j]=ans

    if(j<w-1):
        q.append([i,j+1,ans])

    if(i<h-1):
        q.append([i+1,j,ans])

print(dp[h-1][w-1])



Fixed submission:
h,w=map(int,input().split())
s=[]
for i in range(h):
    s.append(list(input()))

dp=[[99999999 for i in range(w)] for i in range(h)]


if(s[0][0]=='#'):
    dp[0][0]=1
else:
    dp[0][0]=0

for i in range(h):
    for j in range(w):

        if(s[i][j-1] != s[i][j]):
            left = dp[i][j-1]+1
        else:
            left = dp[i][j-1]

        if(s[i-1][j] != s[i][j]):
            top = dp[i-1][j]+1
        else:
            top = dp[i-1][j]

        dp[i][j] = min(dp[i][j],left,top)

print((dp[h-1][w-1]+1)//2)

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

ans=99999999999

def dfs(i,j,right,down,obst):
#    print(i,j,right,down,obst)
    global ans
    obst_ij=obst
    if(s[i][j]=='#'):
        obst_ij+=1

    if(right+down>=h+w-2):
        ans=min(ans,obst_ij)

    if(right<w-1):
        #→
        dfs(i,j+1,right+1,down,obst_ij)

    if(down<h-1):
        #↓
        dfs(i+1,j,right,down+1,obst_ij)

dfs(0,0,0,0,0)
print(ans)

Fixed submission:
h,w=map(int,input().split())
s=[]
for i in range(h):
    s.append(list(input()))

dp=[[99999999 for i in range(w)] for i in range(h)]


if(s[0][0]=='#'):
    dp[0][0]=1
else:
    dp[0][0]=0

for i in range(h):
    for j in range(w):

        if(s[i][j-1] != s[i][j]):
            left = dp[i][j-1]+1
        else:
            left = dp[i][j-1]

        if(s[i-1][j] != s[i][j]):
            top = dp[i-1][j]+1
        else:
            top = dp[i-1][j]

        dp[i][j] = min(dp[i][j],left,top)

print((dp[h-1][w-1]+1)//2)
Buggy python submission (verdict: Time Limit Exceeded):
s=input()
q=int(input())
is_reverse=False
for i in range(q):
    qi=list(input().split())
    if(len(qi)==1):
        is_reverse = not is_reverse
    elif(qi[1]=="1"):
        if(is_reverse):
            s=s+qi[2]
        else:
            s=qi[2]+s
    else:
        if(is_reverse):
            s=qi[2]+s
        else:
            s=s+qi[2]

if(is_reverse):
    print(s[::-1])
else:
    print(s)

Fixed submission:
s=input()
q=int(input())
is_reverse=False
pre=[]
post=[]
for i in range(q):
    qi=list(input().split())
    if(len(qi)==1):
        is_reverse = not is_reverse
    elif(qi[1]=="1"):
        if(is_reverse):
            post.append(qi[2])
        else:
            pre.append(qi[2])
    else:
        if(is_reverse):
            pre.append(qi[2])
        else:
            post.append(qi[2])

if(is_reverse):
    print(''.join(post)[::-1] + s[::-1] + ''.join(pre))
else:
    print(''.join(pre)[::-1] + s + ''.join(post))

Buggy python submission (verdict: Time Limit Exceeded):
s=input()
q=int(input())
is_reverse=False
for i in range(q):
    qi=list(input().split())
    if(qi[0]=="1"):
        is_reverse = not is_reverse
    elif(qi[1]=="1"):
        if(is_reverse):
            s=s+qi[2][::-1]
        else:
            s=qi[2]+s
    else:
        if(is_reverse):
            s=qi[2][::-1]+s
        else:
            s=s+qi[2]

if(is_reverse):
    print(s[::-1])
else:
    print(s)

Fixed submission:
s=input()
q=int(input())
is_reverse=False
pre=[]
post=[]
for i in range(q):
    qi=list(input().split())
    if(len(qi)==1):
        is_reverse = not is_reverse
    elif(qi[1]=="1"):
        if(is_reverse):
            post.append(qi[2])
        else:
            pre.append(qi[2])
    else:
        if(is_reverse):
            pre.append(qi[2])
        else:
            post.append(qi[2])

if(is_reverse):
    print(''.join(post)[::-1] + s[::-1] + ''.join(pre))
else:
    print(''.join(pre)[::-1] + s + ''.join(post))
Buggy python submission (verdict: Time Limit Exceeded):
n,a,b=map(int,input().split())
ncpre=1
MOD=1000000007
ans=0
for i in range(1,n+1):
    nci=ncpre*(n-(i-1))//i
    ncpre=nci
    if(i!=a and i!=b):
        ans = (ans + nci)%MOD
print(ans)

Fixed submission:
n,a,b=map(int,input().split())
MOD  = 1000000007

def comb(N,x):
    numerator = 1
    for i in range(N-x+1,N+1):
        numerator = numerator *i%MOD
    denominator = 1
    for j in range(1,x+1):
        denominator = denominator *j%MOD
    d = pow(denominator,MOD-2,MOD)
    return (numerator*d)%MOD


#実際に使うときは、MOD=10000007 などの剰余計算を組み込んで使うこと！
def repeated_square(x,n):
    #nを2進数で表して順序反転
    bit_n=bin(n)[2:][::-1]

    ans=1
    ni=x

    if(bit_n[0]=="1"):
        ans*=ni

    for i in range(1,len(bit_n)):
        ni=((ni%MOD)*(ni%MOD))%MOD

        #i桁目が1なら、x^(2^i)を加える
        if(bit_n[i]=="1"):
            ans=((ans%MOD)*(ni%MOD))%MOD

    return ans

alln=(repeated_square(2, n)-1)%MOD
print((alln-comb(n, a)-comb(n, b))%MOD)
Buggy python submission (verdict: Time Limit Exceeded):
from fractions import gcd
MOD=(10**9)+7
n=int(input())
a=list(map(int,input().split()))
a_lcm=a[-1]

for ai in a:
    a_lcm=(a_lcm*ai) // gcd(a_lcm, ai)

b=[]
sum_b=0
for ai in a:
    bi=a_lcm//ai
    b.append(bi)
    sum_b+=bi
print(sum_b%MOD)


Fixed submission:
from fractions import gcd
MOD=(10**9)+7
n=int(input())
a=list(map(int,input().split()))
a_lcm=a[-1]

for ai in a:
    a_lcm=(a_lcm*ai) // gcd(a_lcm, ai)

sum_b=0
for ai in a:
    bi=a_lcm//ai
    sum_b+=bi
print(sum_b%MOD)

Buggy python submission (verdict: Runtime Error):
from fractions import gcd
MOD=(10**9)+7
n=int(input())
a=list(map(int,input().split()))
a_lcm=a[0]
a_invsum=0

for ai in a:
    a_lcm=(a_lcm*ai) // gcd(a_lcm, ai)
    a_invsum+=1/ai
sum_b=round(a_invsum * a_lcm)
print(sum_b%MOD)


Fixed submission:
from fractions import gcd
MOD=(10**9)+7
n=int(input())
a=list(map(int,input().split()))
a_lcm=a[-1]

for ai in a:
    a_lcm=(a_lcm*ai) // gcd(a_lcm, ai)

sum_b=0
for ai in a:
    bi=a_lcm//ai
    sum_b+=bi
print(sum_b%MOD)

Buggy python submission (verdict: Time Limit Exceeded):
from fractions import gcd
MOD=(10**9)+7
n=int(input())
a=list(map(int,input().split()))
a_lcm=a[0]

for ai in a:
    a_lcm=(a_lcm*ai) // gcd(a_lcm, ai)

b=[]
for ai in a:
    b.append(a_lcm//ai)
sum_b=sum(b)
print(sum_b%MOD)


Fixed submission:
from fractions import gcd
MOD=(10**9)+7
n=int(input())
a=list(map(int,input().split()))
a_lcm=a[-1]

for ai in a:
    a_lcm=(a_lcm*ai) // gcd(a_lcm, ai)

sum_b=0
for ai in a:
    bi=a_lcm//ai
    sum_b+=bi
print(sum_b%MOD)

Buggy python submission (verdict: Time Limit Exceeded):
from fractions import gcd
MOD=(10**9)+7
n=int(input())
a=list(map(int,input().split()))
a_lcm=a[0]

for ai in a:
    a_lcm=(a_lcm*ai) // gcd(a_lcm, ai)

b=[]
sum_b=0
for ai in a:
    bi=a_lcm//ai
    b.append(bi)
    sum_b+=bi
print(sum_b%MOD)

Fixed submission:
from fractions import gcd
MOD=(10**9)+7
n=int(input())
a=list(map(int,input().split()))
a_lcm=a[-1]

for ai in a:
    a_lcm=(a_lcm*ai) // gcd(a_lcm, ai)

sum_b=0
for ai in a:
    bi=a_lcm//ai
    sum_b+=bi
print(sum_b%MOD)

Buggy python submission (verdict: Time Limit Exceeded):
from fractions import gcd
MOD=(10**9)+7
n=int(input())
a=list(map(int,input().split()))
a_lcm=a[0]

for ai in a:
    a_lcm=(a_lcm*ai) // gcd(a_lcm, ai)

b=[]
for ai in a:
    b.append(a_lcm//ai)
sum_b=sum(b)
print(sum_b%MOD)

Fixed submission:
from fractions import gcd
MOD=(10**9)+7
n=int(input())
a=list(map(int,input().split()))
a_lcm=a[-1]

for ai in a:
    a_lcm=(a_lcm*ai) // gcd(a_lcm, ai)

sum_b=0
for ai in a:
    bi=a_lcm//ai
    sum_b+=bi
print(sum_b%MOD)
Buggy python submission (verdict: Runtime Error):
n=int(input())
s=[]
t=[]
for i in range(n):
	st=list(input())
	s.append(st[0])
	t.append(st[1])
x=input()

print(sum(t[s.index(x):]))


Fixed submission:
n=int(input())
s=[]
t=[]
for i in range(n):
	st=list(input().split())
	s.append(st[0])
	t.append(int(st[1]))
x=input()

print(sum(t[s.index(x)+1:]))
Buggy python submission (verdict: Time Limit Exceeded):
import re
n=int(input())
s=input()
ans=0
for i in range(10):
    for j in range(10):
        for k in range(10):
            p=re.compile(r'.*'+str(i)+r'.*'+str(j)+r'.*'+str(k)+r'.*')
            x=p.match(s)
            if x:
                ans+=1
print(ans)

Fixed submission:
n=int(input())
s=input()
ans=0
for i in range(10):
    for j in range(10):
        for k in range(10):
            x=s.find(str(i))
            y=s.find(str(j),x+1)
            z=s.find(str(k),y+1)
            if(x!=-1 and y!=-1 and z!=-1):
                ans+=1
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import re
n=int(input())
s=input()
ans=0
for i in range(10):
    for j in range(10):
        for k in range(10):
            p=r'.*'+str(i)+r'.*'+str(j)+r'.*'+str(k)+r'.*'
            x=re.match(p, s)
            if x:
                ans+=1
print(ans)

Fixed submission:
n=int(input())
s=input()
ans=0
for i in range(10):
    for j in range(10):
        for k in range(10):
            x=s.find(str(i))
            y=s.find(str(j),x+1)
            z=s.find(str(k),y+1)
            if(x!=-1 and y!=-1 and z!=-1):
                ans+=1
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import re
n=int(input())
s=input()
ans=0
for i in range(10):
    for j in range(10):
        for k in range(10):
            p=r'.*'+str(i)+r'.*'+str(j)+r'.*'+str(k)+r'.*'
            x=re.search(p, s)
            if x:
                ans+=1
print(ans)

Fixed submission:
n=int(input())
s=input()
ans=0
for i in range(10):
    for j in range(10):
        for k in range(10):
            x=s.find(str(i))
            y=s.find(str(j),x+1)
            z=s.find(str(k),y+1)
            if(x!=-1 and y!=-1 and z!=-1):
                ans+=1
print(ans)
Buggy python submission (verdict: Runtime Error):
n=int(input())
a=list(map(int,input().split()))
MOD=1000000007
hats=[0,0,0]
ans=1
for i in range(n):
    ai=a[i]
    ans=((ans%MOD)*(hats.count(ai)%MOD))%MOD
    hats[hats.index(a[i])]+=1
print(ans)


Fixed submission:
n=int(input())
a=list(map(int,input().split()))
MOD=1000000007
hats=[0,0,0]
ans=1
for i in range(n):
    ai=a[i]
    ans=((ans%MOD)*hats.count(ai))%MOD
    if(ans==0):
        break
    hats[hats.index(ai)]+=1
#    print(ai,ans,hats)
print(ans%MOD)
Buggy python submission (verdict: Runtime Error):
from collections import deque
n=int(input())
g=[[] for _ in range(n+1)]
e=[]
for i in range(n-1):
    a,b=map(int,input().split())
    g[a].append(b)
    e.append(b)

q=deque([0])

color=[0 for _ in range(n)]
while(len(q)>0):
    ei=q.popleft()
    c=1
    for x in g[ei]:
        if c == color[ei]:
            c+=1

        color[x]=c
        c+=1
        q.append(x)

print(max(color))
for i in e:
    print(color[i])

Fixed submission:
from collections import deque
n=int(input())
g=[[] for _ in range(n+1)]
e=[]
for i in range(n-1):
    a,b=map(int,input().split())
    g[a-1].append(b-1)
    e.append(b-1)

q=deque([0])

color=[0 for _ in range(n)]
while(len(q)>0):
    ei=q.popleft()
    c=1
    for x in g[ei]:
        if c == color[ei]:
            c+=1

        color[x]=c
        c+=1
        q.append(x)

print(max(color))
for i in e:
    print(color[i])
Buggy python submission (verdict: Runtime Error):
import math
n=int(input())
a=list(map(int,input().split()))

sum_a=sum(a)
left_a=0
right_a=sum_a
ans=math.inf

for i in range(n):
    left_a+=a[i]
    right_a-=a[i]
    if(ans>abs(left_a-right_a)):
        ans=abs(left_a-right_a)
print(ans)

Fixed submission:
import math
n=int(input())
a=list(map(int,input().split()))

sum_a=sum(a)
left_a=0
right_a=sum_a
ans=200002*2020202020

for i in range(n):
    left_a+=a[i]
    right_a-=a[i]
    if(ans>abs(left_a-right_a)):
        ans=abs(left_a-right_a)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import bisect
n=int(input())
l=sorted(list(map(int,input().split())))
ans=0
for i in range(n-1):
    for j in range(i+1,n):
        min_c=max(j+1,bisect.bisect_right(l, l[j]-l[i])+1)
        max_c=bisect.bisect_left(l, l[j]+l[i])-1
        num=max_c-min_c+1
#        print(str(l[i])+" "+str(l[j])+":"+str(min_c)+" "+str(max_c)+":"+str(num))
        ans += num if num > 0 else 0
print(ans)


Fixed submission:
import bisect
n=int(input())
l=sorted(list(map(int,input().split())))
ans=0
for i in range(n-1):
    for j in range(i+1,n):
        min_c=j+1
        max_c=bisect.bisect_left(l, l[j]+l[i])-1
        num=max_c-min_c+1
#        print(str(l[i])+" "+str(l[j])+":"+str(min_c)+" "+str(max_c)+":"+str(num))
        ans += num if num > 0 else 0
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import bisect
n=int(input())
l=sorted(list(map(int,input().split())))
#print(l)
ans=0
for a in range(n-2):
    for b in range(a+1,n-1):
        c=l[b+1:]
        min_c= l[b]-l[a]+1
        max_c= l[a]+l[b]-1
#        print(str(l[a])+","+str(l[b])+" "+str(min_c) + ":" + str(max_c))
        if(min_c <= max_c):
            ans+=bisect.bisect_right(c, max_c) - bisect.bisect_left(c, min_c)
print(ans)


Fixed submission:
import bisect
n=int(input())
l=sorted(list(map(int,input().split())))
ans=0
for i in range(n-1):
    for j in range(i+1,n):
        min_c=j+1
        max_c=bisect.bisect_left(l, l[j]+l[i])-1
        num=max_c-min_c+1
#        print(str(l[i])+" "+str(l[j])+":"+str(min_c)+" "+str(max_c)+":"+str(num))
        ans += num if num > 0 else 0
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import bisect
n=int(input())
l=sorted(list(map(int,input().split())))
#print(l)
ans=0
for a in range(n-2):
    for b in range(a+1,n-1):
        min_c= max(l[b]-l[a]+1,l[b+1])
        max_c= l[a]+l[b]-1
#        print(str(l[a])+","+str(l[b])+" "+str(min_c) + ":" + str(max_c))
        if(min_c <= max_c):
            ans+=bisect.bisect_right(l, max_c) - bisect.bisect_left(l, min_c)
print(ans)

Fixed submission:
import bisect
n=int(input())
l=sorted(list(map(int,input().split())))
ans=0
for i in range(n-1):
    for j in range(i+1,n):
        min_c=j+1
        max_c=bisect.bisect_left(l, l[j]+l[i])-1
        num=max_c-min_c+1
#        print(str(l[i])+" "+str(l[j])+":"+str(min_c)+" "+str(max_c)+":"+str(num))
        ans += num if num > 0 else 0
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import fractions
a,b=map(int,input().split())
gcd_ab=fractions.gcd(a, b)
i=2
d={}
ans=1
while(gcd_ab!=1):
    if(gcd_ab%i == 0):
        val=d.get(i, 0)
        val+=1
        d[i]=val
        gcd_ab//=i
    else:
        i+=1
ans+=len(list(d.keys()))
print(ans)

Fixed submission:
import fractions
a,b=map(int,input().split())
gcd_ab=fractions.gcd(a, b)

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

ans=1
ans+=len(set(prime_factorize(gcd_ab)))
print(ans)

Buggy python submission (verdict: Runtime Error):
import math
a,b=map(int,input().split())
gcd_ab=math.gcd(a, b)
i=2
d={}
ans=1
while(gcd_ab!=1):
    if(gcd_ab%i == 0):
        val=d.get(i, 0)
        val+=1
        d[i]=val
        gcd_ab//=i
    else:
        i+=1
ans+=len(list(d.keys()))
print(ans)

Fixed submission:
import fractions
a,b=map(int,input().split())
gcd_ab=fractions.gcd(a, b)

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

ans=1
ans+=len(set(prime_factorize(gcd_ab)))
print(ans)
Buggy python submission (verdict: Runtime Error):
n=int(input())
print(10**n + 7)

Fixed submission:
h,w,a,b=map(int,input().split())

if(a>(w//2) and b>(h//2)):
    print('No')
else:
    for i in range(h):
        if(i<b):
            print(''.join(['0' for _ in range(a)]) + ''.join(['1' for _ in range(w-a)]))
        else:
            print(''.join(['1' for _ in range(a)]) + ''.join(['0' for _ in range(w-a)]))
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.sort()
    a[n-1] //= 2
print(sum(a))

Fixed submission:
import heapq

def int_minus(x):
    return -1 * int(x)

n,m=map(int,input().split())
a=list(map(int_minus,input().split()))
heapq.heapify(a)
for i in range(m):
    maxa=-1 * heapq.heappop(a)
    maxa = maxa // 2
    heapq.heappush(a, -1 * maxa)
print(-1 * sum(a))

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.sort()
    maxa=a[n-1]
    maxa = maxa // 2
    a[n-1] = maxa
print(sum(a))

Fixed submission:
import heapq

def int_minus(x):
    return -1 * int(x)

n,m=map(int,input().split())
a=list(map(int_minus,input().split()))
heapq.heapify(a)
for i in range(m):
    maxa=-1 * heapq.heappop(a)
    maxa = maxa // 2
    heapq.heappush(a, -1 * maxa)
print(-1 * sum(a))

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.sort()
    maxa=a[len(a)-1]
    maxa = maxa // 2
    a[len(a)-1] = maxa
print(sum(a))

Fixed submission:
import heapq

def int_minus(x):
    return -1 * int(x)

n,m=map(int,input().split())
a=list(map(int_minus,input().split()))
heapq.heapify(a)
for i in range(m):
    maxa=-1 * heapq.heappop(a)
    maxa = maxa // 2
    heapq.heappush(a, -1 * maxa)
print(-1 * sum(a))

Buggy python submission (verdict: Time Limit Exceeded):
n,m=map(int,input().split())
a=list(map(int,input().split()))
for i in range(m):
    maxa=max(a)
    maxind=a.index(maxa)
    maxa = maxa // 2
    a[maxind] = maxa
print(sum(a))

Fixed submission:
import heapq

def int_minus(x):
    return -1 * int(x)

n,m=map(int,input().split())
a=list(map(int_minus,input().split()))
heapq.heapify(a)
for i in range(m):
    maxa=-1 * heapq.heappop(a)
    maxa = maxa // 2
    heapq.heappush(a, -1 * maxa)
print(-1 * sum(a))
Buggy python submission (verdict: Time Limit Exceeded):
import sys
n,k=map(int,input().split())
s=input()
snum=[]
now_si=""
now_sinum=0
for i in range(len(s)):
    if(now_si!=s[i]):
        now_si=s[i]
        snum.append(now_sinum)
        now_sinum=1
    else:
        now_sinum+=1
else:
    snum.append(now_sinum)
snum.pop(0)
#print(snum)

if(len(snum)<3):
    print(sum(snum)-1)
    sys.exit()

for i in range(k):
    min_threesum=9999999999999
    min_threesum_j=9999999999999

    for j in range(len(snum)-3,-1,-1):
        threesum=snum[j]+snum[j+1]+snum[j+2]
        if(threesum==3):
            snum[j]+=snum[j+1]+snum[j+2]
            snum.pop(j+1)
            snum.pop(j+1)
            break
        elif(min_threesum>threesum):
            min_threesum=threesum
            min_threesum_j=j
    else:
        snum[min_threesum_j]+=snum[min_threesum_j+1]+snum[min_threesum_j+2]
        snum.pop(min_threesum_j+1)
        snum.pop(min_threesum_j+1)

#    print(snum)
    if(len(snum)<3):
        print(sum(snum)-len(snum))
        sys.exit()


print(sum(snum)-len(snum))

Fixed submission:
import sys
n,k=map(int,input().split())
s=input()
snum=[]
now_si=""
now_sinum=0
for i in range(len(s)):
    if(now_si!=s[i]):
        now_si=s[i]
        snum.append(now_sinum)
        now_sinum=1
    else:
        now_sinum+=1
else:
    snum.append(now_sinum)
snum.pop(0)

if(len(snum)<3):
    print(sum(snum)-1)
    sys.exit()

for i in range(k):
#    print(snum)
    if(len(snum)<3):
        snum=[sum(snum)]
        break

    snum[-3]+=snum[-2]+snum[-1]
    snum.pop(-1)
    snum.pop(-1)

print(sum(snum)-len(snum))