Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
from bisect import bisect
inf=float("inf")
a,b,q=map(int,input().split())
s=[int(input()) for _ in range(a)]
t=[int(input()) for _ in range(b)]
x=[int(input()) for _ in range(q)]
for i in range(q):
    west=inf
    east=inf
    c=inf
    d=inf
    j=bisect(s,x[i])
    k=bisect(t,x[i])
    if j!=a and k!=0:
        c=s[j]-t[k-1]+min(s[j]-x[i],x[i]-t[k-1])
    if k!=b and j!=0:
        d=t[k]-s[j-1]+min(x[i]-s[j-1],t[k]-x[i])
    if j!=0 and k!=0:
        west=max(x[i]-s[j-1],x[i]-t[k-1])
    if j!=a and k!=b:
        east=max(s[j]-x[i],t[k]-x[i])
    print(min(west,east,c,d))

Fixed submission:
from bisect import bisect
inf=float("inf")
a,b,q=map(int,input().split())
s=[int(input()) for _ in range(a)]
t=[int(input()) for _ in range(b)]
x=[int(input()) for _ in range(q)]
for i in range(q):
    west=inf
    east=inf
    c=inf
    d=inf
    j=bisect(s,x[i])
    k=bisect(t,x[i])
    if j!=a and k!=0:
        c=s[j]-t[k-1]+min(s[j]-x[i],x[i]-t[k-1])
    if k!=b and j!=0:
        d=t[k]-s[j-1]+min(x[i]-s[j-1],t[k]-x[i])
    if j!=0 and k!=0:
        west=max(x[i]-s[j-1],x[i]-t[k-1])
    if j!=a and k!=b:
        east=max(s[j]-x[i],t[k]-x[i])
    print(min(west,east,c,d))
Buggy python submission (verdict: Runtime Error):
from math import gcd
n=int(input())
a=list(map(int,input().split()))
ans=a[0]
for i in range(1,n):
    ans=gcd(a[i],a[i-1])
    a[i]=ans
print(ans)

Fixed submission:
def gcd(x,y):
    if x<y:
        x,y=y,x
    if y==0:
        return x
    else:
        return gcd(y,x%y)       
n=int(input())
a=list(map(int,input().split()))
ans=a[0]
for i in range(1,n):
    ans=gcd(a[i],a[i-1])
    a[i]=ans
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
#DP D
from functools import lru_cache
n,W=map(int,input().split())
wv=[list(map(int,input().split())) for _ in range(n)]
@lru_cache(maxsize=1000)
def dp(i, j):
    w,v=wv[i]
    if i==-1:
        return 0
    elif j<w:
        return dp(i-1, j)
    else:
        return max(dp(i-1, j),dp(i-1, j-w)+v)
print(dp(n-1,W))

Fixed submission:
#DP D
n,W=map(int,input().split())
wv=[list(map(int,input().split())) for _ in range(n)]
dp=[[0]*(W+1) for _ in range(n+1)]
for i in range(n):
    w,v=wv[i]
    for j in range(W+1):
        if j<w:
            dp[i+1][j]=dp[i][j]
        else:
            dp[i+1][j]=max(dp[i][j],dp[i][j-w]+v)
print(dp[-1][-1])

Buggy python submission (verdict: Time Limit Exceeded):
#DP D
from functools import lru_cache
n,W=map(int,input().split())
wv=[list(map(int,input().split())) for _ in range(n)]
@lru_cache(maxsize=1000)
def dp(i, j):
    w,v=wv[i]
    if i==-1:
        return 0
    elif j<w:
        return dp(i-1, j)
    else:
        return max(dp(i-1, j),dp(i-1, j-w)+v)
print(dp(n-1,W))

Fixed submission:
#DP D
n,W=map(int,input().split())
wv=[list(map(int,input().split())) for _ in range(n)]
dp=[[0]*(W+1) for _ in range(n+1)]
for i in range(n):
    w,v=wv[i]
    for j in range(W+1):
        if j<w:
            dp[i+1][j]=dp[i][j]
        else:
            dp[i+1][j]=max(dp[i][j],dp[i][j-w]+v)
print(dp[-1][-1])

Buggy python submission (verdict: Time Limit Exceeded):
#DP D
n,W=map(int,input().split())
wv=[list(map(int,input().split())) for _ in range(n)]
def dp(i, j):
    w,v=wv[i]
    if i==-1:
        return 0
    elif j<w:
        return dp(i-1, j)
    else:
        return max(dp(i-1, j),dp(i-1, j-w)+v)
print(dp(n-1,W))

Fixed submission:
#DP D
n,W=map(int,input().split())
wv=[list(map(int,input().split())) for _ in range(n)]
dp=[[0]*(W+1) for _ in range(n+1)]
for i in range(n):
    w,v=wv[i]
    for j in range(W+1):
        if j<w:
            dp[i+1][j]=dp[i][j]
        else:
            dp[i+1][j]=max(dp[i][j],dp[i][j-w]+v)
print(dp[-1][-1])

Buggy python submission (verdict: Runtime Error):
#DP D
n,W=map(int,input().split())
wv=[list(map(int,input().split())) for _ in range(n)]
dp=[[0]*(W+1) for _ in range(n+1)]
for i in range(n):
    w,v=wv[i]
    for j in range(W+1):
        if j<w:
            dp[i+1][j]=dp[i][j]
        else:
            dp[i+1][j]=max(dp[i][j],dp[i][j-w]+v)
for i in range(n+1):
print(dp[-1][-1])

Fixed submission:
#DP D
n,W=map(int,input().split())
wv=[list(map(int,input().split())) for _ in range(n)]
dp=[[0]*(W+1) for _ in range(n+1)]
for i in range(n):
    w,v=wv[i]
    for j in range(W+1):
        if j<w:
            dp[i+1][j]=dp[i][j]
        else:
            dp[i+1][j]=max(dp[i][j],dp[i][j-w]+v)
print(dp[-1][-1])
Buggy python submission (verdict: Time Limit Exceeded):
#DP E
n,W=map(int,input().split())
wv=[list(map(int,input().split())) for _ in range(n)]
m=0
for i in range(n):
    m+=wv[i][1]
inf=float("inf")
dp=[[inf]*(m+1) for _ in range(n+1)]
dp[0][0]=0
for i in range(n):
    w,v=wv[i]
    for j in range(m+1):
        if j<v:
            dp[i+1][j]=dp[i][j]
        else:
            dp[i+1][j]=min(dp[i][j],dp[i][j-v]+w)
ans=0
for i in range(m+1):
    if dp[n][i]<=W:
        ans=i
print(ans)

Fixed submission:
#DP E
n,W=map(int,input().split())
wv=[list(map(int,input().split())) for _ in range(n)]
m=0
for i in range(n):
    m+=wv[i][1]
inf=float("inf")
dp=[[inf]*(m+1) for _ in range(n+1)]
dp[0][0]=0
for i in range(n):
    w,v=wv[i]
    for j in range(m+1):
        if j<v:
            dp[i+1][j]=dp[i][j]
        else:
            dp[i+1][j]=min(dp[i][j],dp[i][j-v]+w)
ans=0
for i in range(m+1):
    if dp[n][i]<=W:
        ans=i
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
def f(i,j,k):
    return i+j*(N+1)+k*(N+1)**2

N=int(input())
A=list(map(int,input().split()))
cnt=[0,0,0,0]
for a in A:
    cnt[a]+=1
    
dp=[0]*(N+1)**3
dp[1]=N
for k in range(N+1):
    for j in range(N+1):
        for i in range(N+1):
            if i+j+k<=0 or i+j+k>N:
                continue
            dp[f(i,j,k)]=(i*dp[f(i-1,j,k)]+j*dp[f(i+1,j-1,k)]+k*dp[f(i,j+1,k-1)]+N)/(i+j+k)

print(dp[f(cnt[1],cnt[2],cnt[3])])

Fixed submission:
N=int(input())
A=list(map(int,input().split()))
cnt=[0,0,0,0]
for a in A:
    cnt[a]+=1
aaa=cnt[1]
bbb=cnt[2]
ccc=cnt[3]

dp=[[[0]*(N+1) for j in range(bbb+ccc+1)] for i in range(ccc+1)]

for k in range(ccc+1):
    for j in range(bbb+ccc-k+1):
        for i in range(N-k-j+1):
            tmp=i+j+k
            if tmp==0:
                continue
            else:
                dp[k][j][i]=N/tmp
                if i>0:
                    dp[k][j][i]+=i*dp[k][j][i-1]/tmp
                if j>0:
                    dp[k][j][i]+=j*dp[k][j-1][i+1]/tmp
                if k>0:
                    dp[k][j][i]+=k*dp[k-1][j+1][i]/tmp
                
print(dp[ccc][bbb][aaa])
Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
a=list(map(int,input().split()))
dp=[[0]*n for i in range(n)]
for i in range(n):
    if n%2==0:
        dp[i][i]=-a[i]
    else:
        dp[i][i]=a[i]
for l in range(1,n):
    if n%2==l%2:
        for right in range(l,n):
            left=right-l
            dp[left][right]=min(dp[left+1][right]-a[left],dp[left][right-1]-a[right])
    else:
        for right in range(l,n):
            left=right-l
            dp[left][right]=max(dp[left+1][right]+a[left],dp[left][right-1]+a[right])
print(dp[0][n-1])

Fixed submission:
n=int(input())
a=list(map(int,input().split()))
dp=[[0]*n for i in range(n)]
for i in range(n):
    if n%2==0:
        dp[i][i]=-a[i]
    else:
        dp[i][i]=a[i]
for l in range(1,n):
    if n%2==l%2:
        for right in range(l,n):
            left=right-l
            dp[left][right]=min(dp[left+1][right]-a[left],dp[left][right-1]-a[right])
    else:
        for right in range(l,n):
            left=right-l
            dp[left][right]=max(dp[left+1][right]+a[left],dp[left][right-1]+a[right])
print(dp[0][n-1])
Buggy python submission (verdict: Time Limit Exceeded):
n,k=map(int,input().split())
a=list(map(int,input().split()))
mod=10**9+7
dp=[0]*(k+1)
for i in range(a[0]+1):
    dp[i]=1
for i in range(1,n):
    u=a[i]
    h=dp[:]
    for j in range(u+1,k+1):
        h[j]=(dp[j]-dp[j-u-1])%mod
    for j in range(1,k+1):
        h[j]=(h[j]+h[j-1])%mod
    dp=h
print(dp[k])

Fixed submission:
n,k=map(int,input().split())
a=list(map(int,input().split()))
mod=10**9+7
dp=[0]*(k+1)
for i in range(a[0]+1):
    dp[i]=1
for i in range(1,n):
    u=a[i]
    h=dp[:]
    for j in range(u+1,k+1):
        h[j]=(dp[j]-dp[j-u-1])%mod
    for j in range(1,k+1):
        h[j]=(h[j]+h[j-1])%mod
    dp=h
print(dp[k])
Buggy python submission (verdict: Runtime Error):
n,k=map(int,input().split())
a=list(map(int,input().split()))
mod=10**9+7
dp=[0]*(k+1)
for i in range(a[0]+1):
    dp[i]=1
for i in range(1,n):
    u=a[i]
    h=dp[:]
    for j in range(u+1,k+1):
        h[j]=(dp[j]-dp[j-u-1])%mod
    for j in range(1,k+1):
        h[j]=(h[j]+h[j-1])%mod
    dp=h
print(dp[k])


Fixed submission:
import itertools
inf=float("inf")
n=int(input())
a=list(map(int,input().split()))
for i in range(1,n):
    a[i]+=a[i-1]
a.append(0)
dp=[[0]*n for i in range(n)]
for l in range(1,n):
    for right in range(l,n):
        left=right-l
        num=inf
        for mid in range(left,right):
            num=min(num,dp[left][mid]+dp[mid+1][right])
        dp[left][right]=num+a[right]-a[left-1]
print(dp[0][n-1])
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input=sys.stdin.readline

def main():
    N=int(input())
    A=[list(map(int,input().split())) for i in range(N)]

    mod=10**9+7
    qqq=2**N

    data=[[] for i in range(2**N)]
    que=[0]

    dp=[0]*qqq
    dp[0]=1

    flag=[0]*qqq
    flag[0]=1

    que=[0]
    i=0

    while que:
        H=[]
        h=[0]*qqq
        for u in que:
            if u==qqq-1:
                break
            for j in range(N):
                if u&(1<<j)==0 and A[i][j]==1:
                    num=u+(1<<j)
                    h[num]=(h[num]+dp[u])%mod
                    if flag[num]==0:
                        flag[num]=1
                        H.append(num)
        else:  
            dp=h
            que=H
            i+=1
            continue
        break
    print(dp[-1])

if __name__=="__main__":
    main()

Fixed submission:
import sys
input=sys.stdin.readline

N=int(input())
A=[list(map(int,input().split())) for i in range(N)]
mod=10**9+7

dp=[0]*2**N
que=[0]

data=[[] for i in range(N+1)]
for i in range(2**N):
    cnt=0
    for j in range(N):
        if i&(1<<j)==0:
            continue
        cnt+=1
    data[cnt].append(i)
    
for j in range(N):
    if A[0][j]==1:
        num=1<<j
        dp[num]+=1
                
for i in range(N):
    for j in range(N):
        if A[i][j]==1:
            num=1<<j
            for u in data[i]:
                dp[u^num]=(dp[u^num]+dp[u])%mod

print(dp[-1])
Buggy python submission (verdict: Time Limit Exceeded):
from bisect import bisect_left
import itertools
N=int(input())
A=list(map(int,input().split()))
B=[0]*N
A.sort()
t=0
for i in range(N):
    while True:
        if 2**t<=A[i]<2**(t+1):
            break
        t+=1
    B[i]=2**(t+1)-A[i]
i=N-1
count=0
while i>0:
    b=bisect_left(A,B[i])
    if A[b]==B[i] and b!=i:
        A.pop(b)
        B.pop(b)
        count+=1
        i-=2
    else:
        A=A[:i]
        B=B[:i]
        i-=1
print(count) 

Fixed submission:
from bisect import bisect_left
N=int(input())
A=list(map(int,input().split()))
B=[0]*N
A.sort()
t=0
for i in range(N):
    while 2**t<=A[i]:
        if 2**t<=A[i]<2**(t+1):
            break
        t+=1
    B[i]=2**(t+1)-A[i]
i=N-1
count=0
flag=[0]*N
for i in range(N-1,0,-1):
    if flag[i]==1:
        continue
    flag[i]=1
    b=bisect_left(A,B[i])
    if A[b]==B[i] and flag[b]==0:
        flag[i]=1
        flag[b]=1
        A[b]-=1
        count+=1
print(count)

Buggy python submission (verdict: Time Limit Exceeded):
from bisect import bisect_left
N=int(input())
A=list(map(int,input().split()))
B=[0]*N
A.sort()
t=0
for i in range(N):
    while True:
        if 2**t<=A[i]<2**(t+1):
            break
        t+=1
    B[i]=2**(t+1)-A[i]
i=N-1
count=0
while i>0:
    b=bisect_left(A,B[i])
    if A[b]==B[i] and b!=i:
        A=A[:b]+A[b+1:i]
        B=B[:b]+B[b+1:i]
        count+=1
        i-=2
    else:
        A=A[:i]
        B=B[:i]
        i-=1
print(count) 

Fixed submission:
from bisect import bisect_left
N=int(input())
A=list(map(int,input().split()))
B=[0]*N
A.sort()
t=0
for i in range(N):
    while 2**t<=A[i]:
        if 2**t<=A[i]<2**(t+1):
            break
        t+=1
    B[i]=2**(t+1)-A[i]
i=N-1
count=0
flag=[0]*N
for i in range(N-1,0,-1):
    if flag[i]==1:
        continue
    flag[i]=1
    b=bisect_left(A,B[i])
    if A[b]==B[i] and flag[b]==0:
        flag[i]=1
        flag[b]=1
        A[b]-=1
        count+=1
print(count)

Buggy python submission (verdict: Time Limit Exceeded):
from bisect import bisect_left
import itertools
N=int(input())
A=list(map(int,input().split()))
B=[0]*N
A.sort()
t=0
for i in range(N):
    while True:
        if 2**t<=A[i]<2**(t+1):
            break
        t+=1
    B[i]=2**(t+1)-A[i]
i=N-1
count=0
while i>0:
    b=bisect_left(A,B[i])
    if A[b]==B[i] and b!=i:
        A=list(itertools.chain(A[:b],A[b+1:i]))
        B=list(itertools.chain(B[:b],B[b+1:i]))
        count+=1
        i-=2
    else:
        A=A[:i]
        B=B[:i]
        i-=1
print(count)

Fixed submission:
from bisect import bisect_left
N=int(input())
A=list(map(int,input().split()))
B=[0]*N
A.sort()
t=0
for i in range(N):
    while 2**t<=A[i]:
        if 2**t<=A[i]<2**(t+1):
            break
        t+=1
    B[i]=2**(t+1)-A[i]
i=N-1
count=0
flag=[0]*N
for i in range(N-1,0,-1):
    if flag[i]==1:
        continue
    flag[i]=1
    b=bisect_left(A,B[i])
    if A[b]==B[i] and flag[b]==0:
        flag[i]=1
        flag[b]=1
        A[b]-=1
        count+=1
print(count)
Buggy python submission (verdict: Time Limit Exceeded):
n=input()
l=len(n)
n=int(n)
data=[["0"]*l for i in range(4**l)]
for i in range(4**l):
    k=i
    for j in range(l):
        a=k//4**(l-1-j)
        if a==1:
            data[i][j]="3"
        if a==2:
            data[i][j]="5"
        if a==3:
            data[i][j]="7"
        k%=4**(l-1-j)
ans=0
for u in data:
    num=int("".join(u))
    if num<=n:
        num=str(num)
        if "0" not in num and "3" in num and "5" in num and "7" in num:
            ans+=1
print(ans)

Fixed submission:
n=input()
l=len(n)
n=int(n)
data=[["0"]*l for i in range(4**l)]
for i in range(4**l):
    k=i
    for j in range(l):
        a=k//4**(l-1-j)
        if a==1:
            data[i][j]="3"
        if a==2:
            data[i][j]="5"
        if a==3:
            data[i][j]="7"
        k%=4**(l-1-j)
ans=0
for u in data:
    num=int("".join(u))
    if num<=n:
        num=str(num)
        if "0" not in num and "3" in num and "5" in num and "7" in num:
            ans+=1
print(ans)
Buggy python submission (verdict: Runtime Error):
n=int(input())
data=[0]*(n+1)
for i in range(2,n+1):
    for j in range(2,int(i**(1/2))+1):
        if i%j==0:
            break
    else:
        count=0
        for j in range(i,n+1):
            k=j
            while k%i==0:
                k//=i
                data[i]+=1
if data[2]>=74:
    ans=1
else:
    ans=0
count3=0
count5=0
count15=0
count25=0
for i in range(n+1):
    if data[i]>=2:
        count3+=1
for i in range(n+1):
    if data[i]>=4:
        count5+=1
for i in range(n+1):
    if data[i]>=14:
        count15+=1
for i in range(n+1):
    if data[i]>=24:
        count25+=1
ans+=count25*(count3-1)
ans+=count15*(count5-1)
ans+=(count3-2)*count5*(count5-1)//2
print(ans)

Fixed submission:
import sys
n=int(input())
data=[0]*(n+1)
for i in range(2,n+1):
    for j in range(2,int(i**(1/2))+1):
        if i%j==0:
            break
    else:
        count=0
        for j in range(i,n+1):
            k=j
            while k%i==0:
                k//=i
                data[i]+=1
if n==1:
    print(0)
    sys.exit()
if data[2]>=74:
    ans=1
else:
    ans=0
count3=0
count5=0
count15=0
count25=0
for i in range(n+1):
    if data[i]>=2:
        count3+=1
for i in range(n+1):
    if data[i]>=4:
        count5+=1
for i in range(n+1):
    if data[i]>=14:
        count15+=1
for i in range(n+1):
    if data[i]>=24:
        count25+=1
ans+=count25*(count3-1)
ans+=count15*(count5-1)
ans+=(count3-2)*count5*(count5-1)//2
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
#ID
n,m=map(int,input().split())
p=[0]
y=[0]
z=[0]
for i in range(1,m+1):
    P,Y=map(int,input().split())
    p.append(P)
    y.append(Y)
    z.append(i)
for i in range(2,m+1):
    k=i
    for j in range(i-1):
        if y[k]<y[k-1]:
            y[k],y[k-1]=y[k-1],y[k]
            z[k],z[k-1]=z[k-1],z[k]
            p[k],p[k-1]=p[k-1],p[k]
            k-=1
        else:
            break
t=[1]*(n+1)
ID=[0]*(m+1)
for i in range(1,m+1):
    ID[z[i]]=str(p[i]*(10**6)+t[p[i]]).zfill(12)
    t[p[i]]+=1
for i in range(1,m+1):
    print(ID[i])

Fixed submission:
#ID
from collections import deque
n,m=map(int,input().split())
s=[]
for i in range(m):
    p,y=map(int,input().split())
    s.append([y,p,i+1])
s=sorted(s)
s=deque(s)
s.appendleft(0)
t=[1]*(n+1)
ID=[0]*(m+1)
for i in range(1,m+1):
    ID[s[i][2]]=str(s[i][1]*(10**6)+t[s[i][1]]).zfill(12)
    t[s[i][1]]+=1
for i in range(1,m+1):
    print(ID[i])
Buggy python submission (verdict: Runtime Error):
def gcd(x,y):
    if x<y:
        x,y=y,x
    if y==0:
        return x
    else:
        return gcd(y,x%y)

N,M=map(int,input().split())
S=input()
T=input()
L=N*M//gcd(N,M)
n=L//N
m=L//M
l=n*m//gcd(n,m)
i=l//n
j=l//m
for k in range(N//i):
    if S[i*k]==T[j*k]:
        continue
    else:
        print(-1)
        sys.exit()
print(L)

Fixed submission:
import sys
def gcd(x,y):
    if x<y:
        x,y=y,x
    if y==0:
        return x
    else:
        return gcd(y,x%y)

N,M=map(int,input().split())
S=input()
T=input()
L=N*M//gcd(N,M)
n=L//N
m=L//M
l=n*m//gcd(n,m)
i=l//n
j=l//m
for k in range(N//i):
    if S[i*k]==T[j*k]:
        continue
    else:
        print(-1)
        sys.exit()
print(L)
Buggy python submission (verdict: Runtime Error):
n,m=map(int,input().split())
mod=10**9+7
from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

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
lst=prime_factorize(m)
if m!=1:
    li=[1]
for i in range(1,len(lst)):
    if lst[i]==lst[i-1]:
        li[-1]+=1
    else:
        li.append(1)
ans=1
for u in li:
    a=n-1+u
    x=cmb(a,u)%mod
    ans=(ans*x)%mod
print(ans)

Fixed submission:
n,m=map(int,input().split())
mod=10**9+7
from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

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
lst=prime_factorize(m)
if m!=1:
    li=[1]
else:
    li=[0]
for i in range(1,len(lst)):
    if lst[i]==lst[i-1]:
        li[-1]+=1
    else:
        li.append(1)
ans=1
for u in li:
    a=n-1+u
    x=cmb(a,u)%mod
    ans=(ans*x)%mod
print(ans)
Buggy python submission (verdict: Runtime Error):
import sys
n,k=map(int,input().split())
x=list(map(int,input().split()))
left=[]
right=[]
origin=0
for u in x:
    if u<0:
        left.append(abs(u))
    elif u==0:
        origin+=1
    else:
        right.append(u)
left.sort()
ans=float("inf")
k-=origin
if k==0:
    print(0)
    sys.exit()
r=len(right)
l=len(left)
for i in range(k):
    if i<r and k-i-2<l:
        y=right[i]+left[k-i-2]+min(right[i],left[k-i-2])
        ans=min(ans,y)
print(ans)

Fixed submission:
import sys
n,k=map(int,input().split())
x=list(map(int,input().split()))
left=[]
right=[]
origin=0
for u in x:
    if u<0:
        left.append(abs(u))
    elif u==0:
        origin+=1
    else:
        right.append(u)
left.sort()
k-=origin
if k==0:
    print(0)
    sys.exit()
r=len(right)
l=len(left)
ans=float("inf")
if k<=r:
    ans=right[k-1]
if k<=l:
    ans=min(ans,left[k-1])
for i in range(k-1):
    if i<r and k-i-2<l:
        y=right[i]+left[k-i-2]+min(right[i],left[k-i-2])
        ans=min(ans,y)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n,m=map(int,input().split())
xyz=[list(map(int,input().split())) for i in range(n)]
lst=[]
for i in range(8):
    if i&1==1:
        a=1
    else:
        a=-1
    if (i>>1)&1==1:
        b=1
    else:
        b=-1
    if (i>>2)&1==1:
        c=1
    else:
        c=-1
    h=[0]
    for u in xyz:
        x,y,z=u
        h.append(a*x+b*y+c*z)
    lst.append(h)
ans=0
for u in lst:
    dp=[[0]*(m+1) for i in range(n+1)]
    for i in range(1,n+1):
        d=u[i]
        for j in range(1,m+1):
            dp[i][j]=max(dp[i-1][j],dp[i-1][j-1]+d)
    ans=max(ans,dp[n][m])
print(ans)

Fixed submission:
n,m=map(int,input().split())
xyz=[list(map(int,input().split())) for i in range(n)]
lst=[]
for i in range(8):
    if i&1==1:
        a=1
    else:
        a=-1
    if (i>>1)&1==1:
        b=1
    else:
        b=-1
    if (i>>2)&1==1:
        c=1
    else:
        c=-1
    h=[]
    for u in xyz:
        x,y,z=u
        h.append(a*x+b*y+c*z)
    lst.append(h)
ans=0
for u in lst:
    u.sort(reverse=True)
    e=0
    for i in range(m):
        e+=u[i]
    ans=max(ans,e)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
s=input()
n=len(s)
k=int(input())
lst=list(s)
lst.sort()
ans=[]
for i in range(min(k,n)):
    a=lst[i]
    for j in range(n):
        if s[j]==a:
            for l in range(min(5,n-j)):
                ans.append(s[j:j+l+1])
ans.sort()
t=1
while t<len(ans):
    if ans[t]==ans[t-1]:
        ans.pop(t)
    else:
        t+=1
print(ans[k-1])


Fixed submission:
s=input()
n=len(s)
k=int(input())
lst=list(s)
lst.sort()
ans=[]
for i in range(min(k,n)):
    a=lst[i]
    count=0
    for j in range(n):
        if s[j]==a:
            count+=1
            for l in range(min(5,n-j)):
                ans.append(s[j:j+l+1])
    if count>=5:
        break
ans.sort()
t=1
while t<len(ans):
    if ans[t]==ans[t-1]:
        ans.pop(t)
    else:
        t+=1
print(ans[k-1])

Buggy python submission (verdict: Time Limit Exceeded):
s=input()
n=len(s)
k=int(input())
lst=list(s)
lst.sort()
ans=[]
for i in range(min(k,n)):
    a=lst[i]
    for j in range(n):
        if s[j]==a:
            for l in range(min(5,n-j)):
                ans.append(s[j:j+l+1])
ans.sort()
t=1
while t<len(ans):
    if ans[t]==ans[t-1]:
        ans.pop(t)
    else:
        t+=1
print(ans[k-1])

Fixed submission:
s=input()
n=len(s)
k=int(input())
lst=list(s)
lst.sort()
ans=[]
for i in range(min(k,n)):
    a=lst[i]
    count=0
    for j in range(n):
        if s[j]==a:
            count+=1
            for l in range(min(5,n-j)):
                ans.append(s[j:j+l+1])
    if count>=5:
        break
ans.sort()
t=1
while t<len(ans):
    if ans[t]==ans[t-1]:
        ans.pop(t)
    else:
        t+=1
print(ans[k-1])
Buggy python submission (verdict: Runtime Error):
Q=int(input())
ab=[list(map(int,input().split())) for _ in range(Q)]

for a,b in ab:
    
    if a>b:
        a,b=b,a
    if a==b:
        print(2*(a-1))
        continue
        
    c = math.ceil((a*b)**0.5-1)
    
    if c*(c+1)>=a*b:
        print(2*(c-1))
    else:
        print(2*c-1)

Fixed submission:
import math
Q = int(input())
ans = []

for i in range(Q):
    a,b = map(int,input().split())
    if a>b:
        a,b = b,a
    if a == b:
        ans.append((a-1)*2)
        continue
    c = math.ceil((a*b)**0.5-1)
    
    ans.append(c*2-1)
    if a <= c:
        ans[-1] -= 1
    if c*(c+1) < a*b and a != c+1 != b:
        ans[-1] +=1
for i in ans:
    print(i)