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

mod = 10**9+7

m = N
fac = [1]*m
ninv = [1]*m
finv = [1]*m
for i in range(2,m):
    fac[i] = fac[i-1]*i%mod
    ninv[i] = (-(mod//i)*ninv[mod%i])%mod
    finv[i] = finv[i-1]*ninv[i]%mod

def comb(n,k):
    if n<0 or k<0 or k>n:return 0
    return (fac[n]*finv[k]%mod)*finv[n-k]%mod

for i in range(1,K+1):
    print(comb(N-K+1,i)*comb(K-1,i-1)%mod)

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

mod = 10**9+7

m = N+1
fac = [1]*m
ninv = [1]*m
finv = [1]*m
for i in range(2,m):
    fac[i] = fac[i-1]*i%mod
    ninv[i] = (-(mod//i)*ninv[mod%i])%mod
    finv[i] = finv[i-1]*ninv[i]%mod

def comb(n,k):
    if n<0 or k<0 or k>n:return 0
    return (fac[n]*finv[k]%mod)*finv[n-k]%mod

for i in range(1,K+1):
    print(comb(N-K+1,i)*comb(K-1,i-1)%mod)

Buggy python submission (verdict: Runtime Error):
N,K = map(int,input().split())

mod = 10**9+7

m = N
fac = [1]*m
ninv = [1]*m
finv = [1]*m
for i in range(2,m):
    fac[i] = fac[i-1]*i%mod
    ninv[i] = (-(mod//i)*ninv[mod%i])%mod
    finv[i] = finv[i-1]*ninv[i]%mod

def comb(n,k):
    if n<0 or k<0 or k>n:return 0
    return (fac[n]*finv[k]%mod)*finv[n-k]%mod

for i in range(1,K+1):
    print(comb(N-K+1,i)*comb(K-1,i-1)%mod)

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

mod = 10**9+7

m = N+1
fac = [1]*m
ninv = [1]*m
finv = [1]*m
for i in range(2,m):
    fac[i] = fac[i-1]*i%mod
    ninv[i] = (-(mod//i)*ninv[mod%i])%mod
    finv[i] = finv[i-1]*ninv[i]%mod

def comb(n,k):
    if n<0 or k<0 or k>n:return 0
    return (fac[n]*finv[k]%mod)*finv[n-k]%mod

for i in range(1,K+1):
    print(comb(N-K+1,i)*comb(K-1,i-1)%mod)
Buggy python submission (verdict: Runtime Error):
N=int(input())
xy=[list(map(int,input().split())) for _ in [0]*N]

pq = dict()
for i in range(N):
    for j in range(N):
        if i==j:continue
        p = xy[i][0] - xy[j][0]
        q = xy[i][1] - xy[j][1]
        pq[(p,q)] = pq.get((p,q),0)+1

print(N - max(pq.values()))

Fixed submission:
N=int(input())
xy=[list(map(int,input().split())) for _ in [0]*N]

pq = {0:0}
for i in range(N):
    for j in range(N):
        if i==j:continue
        p = xy[i][0] - xy[j][0]
        q = xy[i][1] - xy[j][1]
        pq[(p,q)] = pq.get((p,q),0)+1

print(N - max(pq.values()))

Buggy python submission (verdict: Runtime Error):
N=int(input())
xy=[list(map(int,input().split())) for _ in [0]*N]

dx = [[10**10]*N for _ in [0]*N]
dy = [[10**10]*N for _ in [0]*N]
ps = set()
qs = set()
for i in range(N):
    for j in range(N):
        if i==j:continue
        dx[i][j] = xy[i][0] - xy[j][0]
        dy[i][j] = xy[i][1] - xy[j][1]
        ps.add(dx[i][j])
        qs.add(dy[i][j])
for i in range(N):
    dx[i] = set(dx[i]) - set(10**10)
    dy[i] = set(dy[i]) - set(10**10)

ans = 0
for p in ps:
    for q in qs:
        cnt = 0
        for i in range(N):
            if (p in dx[i]) and (q in dy[i]):
                cnt += 1
        ans = max(ans,cnt)

print(N-ans)

Fixed submission:
N=int(input())
xy=[list(map(int,input().split())) for _ in [0]*N]

pq = {0:0}
for i in range(N):
    for j in range(N):
        if i==j:continue
        p = xy[i][0] - xy[j][0]
        q = xy[i][1] - xy[j][1]
        pq[(p,q)] = pq.get((p,q),0)+1

print(N - max(pq.values()))

Buggy python submission (verdict: Runtime Error):
N=int(input())
xy=[list(map(int,input().split())) for _ in [0]*N]

dx = [[10**10]*N for _ in [0]*N]
dy = [[10**10]*N for _ in [0]*N]
ps = set()
qs = set()
for i in range(N):
    for j in range(N):
        if i==j:continue
        dx[i][j] = xy[i][0] - xy[j][0]
        dy[i][j] = xy[i][1] - xy[j][1]
        ps.add(dx[i][j])
        qs.add(dy[i][j])
for i in range(N):
    dx[i] = set(dx[i]) - set(10**10)
    dy[i] = set(dy[i]) - set(10**10)

ans = 0
for p in ps:
    for q in qs:
        cnt = 0
        for i in range(N):
            if (p in dx[i]) and (q in dy[i]):
                cnt += 1
        ans = max(ans,cnt)

print(N-ans)

Fixed submission:
N=int(input())
xy=[list(map(int,input().split())) for _ in [0]*N]

pq = {0:0}
for i in range(N):
    for j in range(N):
        if i==j:continue
        p = xy[i][0] - xy[j][0]
        q = xy[i][1] - xy[j][1]
        pq[(p,q)] = pq.get((p,q),0)+1

print(N - max(pq.values()))
Buggy python submission (verdict: Time Limit Exceeded):
R,G,B,N = map(int,input().split())

ans = 0
for r in range(N//R+1):
    for g in range(N//G+1):
        bB = N - r*R - g*G
        if bB%B == 0 and 0<=(bB//B):
            ans += 1
print(ans)

Fixed submission:
R,G,B,N = map(int,input().split())

ans = 0
for r in range(N//R+1):
    for g in range(N//G+1):
        bB = N - r*R - g*G
        if bB%B == 0 and 0<=(bB//B):
            ans += 1
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
S = (input())

a = []
pc = "."
pi = 0
for i,c in enumerate(S):
    if pc!=c:
        a.append(i-pi)
        pi = i
        pc = c
else:
    a.append(i+1-pi)

ans = N
l = len(a)
for i in range(0,(l+1)//2):
    ans = min(ans,sum(a[1:1+i*2:2])+sum(a[2+i*2::2]))
print(ans)

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

a = []
pc = "."
pi = 0
for i,c in enumerate(S):
    if pc!=c:
        a.append(i-pi)
        pi = i
        pc = c
else:
    a.append(i+1-pi)

l = len(a)
w = 0
b = sum(a[2::2])
ans = w+b
for i in range(1,(l+1)//2):
    #ans = min(ans,sum(a[1:1+i*2:2])+sum(a[2+i*2::2]))
    if -1+i*2 < l:
        w += a[-1+i*2]
    if i*2 < l:
        b -= a[i*2]
    ans = min(ans,w+b)
print(ans)
Buggy python submission (verdict: Runtime Error):
N,K = list(map(int,input().split()))
S = input()
n = []
p = S[0]
c = 1
for s in S[1:]:
    if s != p:
        n.append(c)
        p = s
        c = 0
    c+=1
n.append(c)
ans = n[0]
if S[0]=="0":
    for i in range(1,len(n)-2*K+1,2):
        ans = max(ans,sum(n[i:i+2*K+1]))
    n[1]+=n[0]
    n.pop(0)
    K -=1
for i in range(0,len(n)-2*K,2):
    ans = max(ans,sum(n[i:i+2*K+1]))
print(ans)

Fixed submission:
N,K = list(map(int,input().split()))
S = input()
n = []
p = S[0]
c = 1
for s in S[1:]:
    if s != p:
        n.append(c)
        p = s
        c = 0
    c+=1
n.append(c)
ans = max(n)
sum_n = [0]
for i in n:
    sum_n.append(i+sum_n[-1])
if S[0]=="0":
    for i in range(1,len(n)-2*K+1,2):
        ans = max(ans,sum_n[min(i+2*K+1,len(sum_n)-1)]-sum_n[i])
    sum_n.pop(1)
    n.pop(0)
    K -=1
for i in range(0,len(n)-2*K+1,2):
    ans = max(ans,sum_n[min(i+2*K+1,len(sum_n)-1)]-sum_n[i])
if (len(n)-2*K+1)<=0:
    ans = max(ans,sum_n[-1])
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
X,Y,Z,K = map(int,input().split())
*A, = map(int,input().split())
*B, = map(int,input().split())
*C, = map(int,input().split())
AB = sorted(a+b for a in A for b in B)[::-1][:K]
ABC = sorted(ab+c for ab in AB for c in C)[::-1][:K]
print(*ABC,sep="\n")

Fixed submission:
X,Y,Z,K = list(map(int,input().split()))
A = sorted(list(map(int,input().split())),reverse=True)
B = sorted(list(map(int,input().split())),reverse=True)
C = sorted(list(map(int,input().split())),reverse=True)

ma,mb,mc = A[0],B[0],C[0]
sA = [a-ma for a in A] + [-10**15]
sB = [b-mb for b in B] + [-10**15]
sC = [c-mc for c in C] + [-10**15]

ia,ib,ic = 0,0,0
while min(10**5,(X)*(Y)*(Z)) > (ia+1)*(ib+1)*(ic+1):
    m = max(sA[ia+1],sB[ib+1],sC[ic+1])
    if ia < (X-1) and sA[ia+1] == m:
        ia = min(ia+1,X-1)
    if ib < (Y-1) and sB[ib+1] == m:
        ib = min(ib+1,Y-1)
    if ic < (Z-1) and sC[ic+1] == m:
        ic = min(ic+1,Z-1)
ans = []
for a in A[:ia+1]:
    for b in B[:ib+1]:
        for c in C[:ic+1]:
            ans.append(a+b+c)
ans.sort(reverse=True)
for out in ans[:K]:
    print(out)

Buggy python submission (verdict: Time Limit Exceeded):
X,Y,Z,K = list(map(int,input().split()))
A = sorted(list(map(int,input().split())),reverse=True)
B = sorted(list(map(int,input().split())),reverse=True)
C = sorted(list(map(int,input().split())),reverse=True)

ma,mb,mc = A[0],B[0],C[0]
sA = [a-ma for a in A] + [-10**15]
sB = [b-mb for b in B] + [-10**15]
sC = [c-mc for c in C] + [-10**15]

ia,ib,ic = 0,0,0
while min(10**7,(X)*(Y)*(Z)) > (ia+1)*(ib+1)*(ic+1):
    m = max(sA[ia+1],sB[ib+1],sC[ic+1])
    if ia < (X-1) and sA[ia+1] == m:
        ia = min(ia+1,X-1)
    if ib < (Y-1) and sB[ib+1] == m:
        ib = min(ib+1,Y-1)
    if ic < (Z-1) and sC[ic+1] == m:
        ic = min(ic+1,Z-1)
ans = []
for a in A[:ia+1]:
    for b in B[:ib+1]:
        for c in C[:ic+1]:
            ans.append(a+b+c)
ans.sort(reverse=True)
for out in ans[:K]:
    print(out)

Fixed submission:
X,Y,Z,K = list(map(int,input().split()))
A = sorted(list(map(int,input().split())),reverse=True)
B = sorted(list(map(int,input().split())),reverse=True)
C = sorted(list(map(int,input().split())),reverse=True)

ma,mb,mc = A[0],B[0],C[0]
sA = [a-ma for a in A] + [-10**15]
sB = [b-mb for b in B] + [-10**15]
sC = [c-mc for c in C] + [-10**15]

ia,ib,ic = 0,0,0
while min(10**5,(X)*(Y)*(Z)) > (ia+1)*(ib+1)*(ic+1):
    m = max(sA[ia+1],sB[ib+1],sC[ic+1])
    if ia < (X-1) and sA[ia+1] == m:
        ia = min(ia+1,X-1)
    if ib < (Y-1) and sB[ib+1] == m:
        ib = min(ib+1,Y-1)
    if ic < (Z-1) and sC[ic+1] == m:
        ic = min(ic+1,Z-1)
ans = []
for a in A[:ia+1]:
    for b in B[:ib+1]:
        for c in C[:ic+1]:
            ans.append(a+b+c)
ans.sort(reverse=True)
for out in ans[:K]:
    print(out)
Buggy python submission (verdict: Runtime Error):
N,Q = list(map(int,input().split()))
S = (input())
lr = [list(map(int,input().split())) for _ in range(Q)]

cnt = [0]*N
tmp = 0
for i,c in enumerate(S):
    if tmp == 0 and c == "A":
        tmp =1
        cnt[i] = cnt[i-1]
    elif tmp == 1 and c == "C":
        tmp =0
        cnt[i] = cnt[i-1]+1
    else:
        tmp = int(c == "A")
        cnt[i] = cnt[i-1]

for l,r in lr:
    print(cnt[r-1]-cnt[l-1] , " : " ,S[l-1:r])

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

cnt = [0]*N
tmp = 0
for i,c in enumerate(S):
    if tmp == 0 and c == "A":
        tmp =1
        cnt[i] = cnt[i-1]
    elif tmp == 1 and c == "C":
        tmp =0
        cnt[i] = cnt[i-1]+1
    else:
        tmp = int(c == "A")
        cnt[i] = cnt[i-1]

for l,r in lr:
    print(cnt[r-1]-cnt[l-1])
Buggy python submission (verdict: Time Limit Exceeded):
S = list(map(int,input()))
N = len(S)
i = 0
while i < len(S)-1:
    if S[i] != S[i+1]:
        S[i:] = S[i+2:]
        i -=1
    else:
        i +=1
print(N-len(S))

Fixed submission:
S = list(map(int,input()))
N = len(S)

ones = sum(S)
zeros = N - ones
print(2*min(ones,zeros))
Buggy python submission (verdict: Time Limit Exceeded):
#D問題
A,B,Q = map(int,(input().split()))
si = [-(10**10)]+[int(input()) for _ in range(A)]+[2*(10**10)] # 範囲外に追加して、xの左右に常にデータがあるようにする
ti = [-(10**10)]+[int(input()) for _ in range(B)]+[2*(10**10)]
A +=2
B +=2

for _ in [0]*Q:
    x = int(input())
    l = 0
    r = A-1
    while l+1<r:
        i = (l+r)//2
        if si[i]<x:
            l = i
        else:
            r = i
    sl = si[l]
    sr = si[r]
    
    l = 0
    r = B-1
    while l+1<r:
        i = (l+r)//2
        if ti[i]<x:
            l = i
        else:
            r = i
    tl = ti[l]
    tr = ti[r]
    dsl = x-sl
    dsr = sr-x
    dtl = x-tl
    dtr = tr-x
    print(min(max(dsr,dtr),max(dsl,dtl),dsl+dtr+min(dsl,dtr),dsr+dtl+min(dsr,dtl)))

Fixed submission:
A,B,Q = map(int,(input().split()))
si = [-(10**10)]+[int(input()) for _ in range(A)]+[2*(10**10)]
ti = [-(10**10)]+[int(input()) for _ in range(B)]+[2*(10**10)]
xi = [(i,int(input())) for i in range(Q)]
A +=2
B +=2

#xを小さい順に考える
xi.sort(key = lambda x:x[1])
ans = [0]*Q
x = xi[0][1]
for i_sr,sr in enumerate(si):
    if sr>x:
        sl = si[i_sr-1]
        break
for i_tr,tr in enumerate(ti):
    if tr>x:
        tl = ti[i_tr-1]
        break
for i,x in xi:
    while sr < x:
        sl = sr
        i_sr += 1
        sr = si[i_sr]
    while tr < x:
        tl = tr
        i_tr += 1
        tr = ti[i_tr]
    dsl = x-sl
    dsr = sr-x
    dtl = x-tl
    dtr = tr-x
    ans[i] = min(max(dsr,dtr),max(dsl,dtl),dsl+dtr+min(dsl,dtr),dsr+dtl+min(dsr,dtl))
for out in ans:
    print(out)

Buggy python submission (verdict: Time Limit Exceeded):
#D問題
A,B,Q = map(int,(input().split()))
si = [-(10**10)]+[int(input()) for _ in range(A)]+[2*(10**10)] # 範囲外に追加して、xの左右に常にデータがあるようにする
ti = [-(10**10)]+[int(input()) for _ in range(B)]+[2*(10**10)]
A +=2
B +=2

for _ in [0]*Q:
    x = int(input())
    l = 0
    r = A-1
    while l+1<r:
        i = (l+r)//2
        if si[i]<x:
            l = i
        else:
            r = i
    sl = si[l]
    sr = si[r]
    
    l = 0
    r = B-1
    while l+1<r:
        i = (l+r)//2
        if ti[i]<x:
            l = i
        else:
            r = i
    tl = ti[l]
    tr = ti[r]
    dsl = x-sl
    dsr = sr-x
    dtl = x-tl
    dtr = tr-x
    print(min(max(dsr,dtr),max(dsl,dtl),dsl+dtr+min(dsl,dtr),dsr+dtl+min(dsr,dtl)))

Fixed submission:
A,B,Q = map(int,(input().split()))
si = [-(10**10)]+[int(input()) for _ in range(A)]+[2*(10**10)]
ti = [-(10**10)]+[int(input()) for _ in range(B)]+[2*(10**10)]
xi = [(i,int(input())) for i in range(Q)]
A +=2
B +=2

#xを小さい順に考える
xi.sort(key = lambda x:x[1])
ans = [0]*Q
x = xi[0][1]
for i_sr,sr in enumerate(si):
    if sr>x:
        sl = si[i_sr-1]
        break
for i_tr,tr in enumerate(ti):
    if tr>x:
        tl = ti[i_tr-1]
        break
for i,x in xi:
    while sr < x:
        sl = sr
        i_sr += 1
        sr = si[i_sr]
    while tr < x:
        tl = tr
        i_tr += 1
        tr = ti[i_tr]
    dsl = x-sl
    dsr = sr-x
    dtl = x-tl
    dtr = tr-x
    ans[i] = min(max(dsr,dtr),max(dsl,dtl),dsl+dtr+min(dsl,dtr),dsr+dtl+min(dsr,dtl))
for out in ans:
    print(out)
Buggy python submission (verdict: Runtime Error):
N,M = map(int,input().split())
X = list(map(int,(input().split())))

X.sort()

memo = dict()
def get_min(n,x):
    key = str((n,x))
    tmp = memo.get(key,None)
    if tmp != None:
        return tmp
    if x == []:
        tmp = 10**8
        memo[key] = tmp
        return tmp
    elif len(x) == 1:
        memo[key] = 0
        return 0
    x0 = x[0]
    if n == 1:
        tmp = x[-1]-x0
        memo[key] = tmp
        return tmp
    tmp = min([y - x0 + get_min(n-1,x[i+1:]) for i,y in enumerate(x)])
    memo[key] = tmp
    return tmp
if N >= M:
    print(0)
else:
    print(get_min(N,X))

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

X.sort()

dif_X = [X[i+1]-x for i,x in enumerate(X[:-1])]
dif_X.sort()
print(sum(dif_X[:max(0,M-N)]))

Buggy python submission (verdict: Runtime Error):
X.sort()

memo = dict()
def get_min(n,x):
    key = str((n,x))
    tmp = memo.get(key,None)
    if tmp != None:
        return tmp
    if x == []:
        tmp = 10**8
        memo[key] = tmp
        return tmp
    elif len(x) == 1:
        memo[key] = 0
        return 0
    x0 = x[0]
    if n == 1:
        tmp = x[-1]-x0
        memo[key] = tmp
        return tmp
    tmp = min([y - x0 + get_min(n-1,x[i+1:]) for i,y in enumerate(x)])
    memo[key] = tmp
    return tmp
if N >= M:
    print(0)
else:
    print(get_min(N,X))

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

X.sort()

dif_X = [X[i+1]-x for i,x in enumerate(X[:-1])]
dif_X.sort()
print(sum(dif_X[:max(0,M-N)]))

Buggy python submission (verdict: Runtime Error):
N,M = map(int,input().split())
X = list(map(int,(input().split())))

X.sort()

memo = dict()
def get_min(n,x):
    key = str((n,x))
    tmp = memo.get(key,None)
    if tmp != None:
        return tmp
    if x == []:
        tmp = 10**8
        memo[key] = tmp
        return tmp
    elif len(x) == 1:
        memo[key] = 0
        return 0
    x0 = x[0]
    if n == 1:
        tmp = x[-1]-x0
        memo[key] = tmp
        return tmp
    tmp = min([y - x0 + get_min(n-1,x[i+1:]) for i,y in enumerate(x)])
    memo[key] = tmp
    return tmp

print(get_min(N,X))

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

X.sort()

dif_X = [X[i+1]-x for i,x in enumerate(X[:-1])]
dif_X.sort()
print(sum(dif_X[:max(0,M-N)]))
Buggy python submission (verdict: Time Limit Exceeded):
N,M = map(int,input().split())
AB = [list(map(int,input().split())) for _ in [0]*(N+M-1)]

E = [[] for _ in [0]*N]
Eb = [[] for _ in [0]*N]
for a,b in AB:
    E[a-1].append(b-1)
    Eb[b-1].append(a-1)

r = 0
while Eb[r]: r=Eb[r][0]

d = [-1]*N
d[r] = 0
q = [r]
while q:
    qq = []
    for i in q:
        di = d[i]
        for j in E[i]:
            if d[j]>=di+1:continue
            d[j] = di+1
            q.append(j)
    q = qq

p=[0]*N
for i in range(N):
    di = d[i]
    for j in Eb[i]:
        if d[j]==di-1:
            p[i] = j+1

print(*p,sep="\n")

Fixed submission:
N,M = map(int,input().split())
AB = [list(map(int,input().split())) for _ in [0]*(N+M-1)]

E = [set() for _ in [0]*N]
E2 = [set() for _ in [0]*N]
Eb = [set() for _ in [0]*N]
for a,b in AB:
    E[a-1].add(b-1)
    E2[a-1].add(b-1)
    Eb[b-1].add(a-1)

p = [0]*N
q = []
for i in range(N):
    if not E[i]:
        q.append(i)
while q:
    qq = set()
    for i in q:
        for j in Eb[i]:
            E[j].remove(i)
    for i in q:
        while Eb[i]:
            j = Eb[i].pop()
            if not E[j]:
                for k in E2[j]:
                    if p[k] == 0 : p[k] = j+1
                qq.add(j)
    q = qq

print(*p,sep="\n")

Buggy python submission (verdict: Time Limit Exceeded):
N,M = map(int,input().split())
AB = [list(map(int,input().split())) for _ in [0]*(N+M-1)]

E = [[] for _ in [0]*N]
Eb = [[] for _ in [0]*N]
for a,b in AB:
    E[a-1].append(b-1)
    Eb[b-1].append(a-1)

r = 0
while Eb[r]: r=Eb[r][0]

d = [-1]*N
d[r] = 0
q = [r]
while q:
    qq = []
    for i in q:
        di = d[i]
        for j in E[i]:
            if d[j]>=di+1:continue
            d[j] = di+1
            q.append(j)
    q = qq

p=[0]*N
for i in range(N):
    di = d[i]
    for j in Eb[i]:
        if d[j]==di-1:
            p[i] = j+1

print(*p,sep="\n")

Fixed submission:
N,M = map(int,input().split())
AB = [list(map(int,input().split())) for _ in [0]*(N+M-1)]

E = [set() for _ in [0]*N]
E2 = [set() for _ in [0]*N]
Eb = [set() for _ in [0]*N]
for a,b in AB:
    E[a-1].add(b-1)
    E2[a-1].add(b-1)
    Eb[b-1].add(a-1)

p = [0]*N
q = []
for i in range(N):
    if not E[i]:
        q.append(i)
while q:
    qq = set()
    for i in q:
        for j in Eb[i]:
            E[j].remove(i)
    for i in q:
        while Eb[i]:
            j = Eb[i].pop()
            if not E[j]:
                for k in E2[j]:
                    if p[k] == 0 : p[k] = j+1
                qq.add(j)
    q = qq

print(*p,sep="\n")
Buggy python submission (verdict: Time Limit Exceeded):
N,K = map(int,input().split())
td = sorted([list(map(int,input().split())) for _ in range(N)],key = lambda x: (-x[1],x[0]))

head = []
no_head = []
is_used = [False]*(N+1)
for t,d in td[:K]:
    if is_used[t]:
        no_head.append(d)
    else:
        head.append(d)
        is_used[t] = True

unused_head = []
for t,d in td[K:]:
    if not is_used[t]:
        unused_head.append(d)
        is_used[t] = True
        
n = min(len(no_head),len(unused_head))
ans = 0
sum_head = sum(head)
l_head = len(head)
l_no_head = len(no_head)
for i in range(n+1):
    ans = max(ans,sum_head+sum(no_head[:l_no_head-i])+sum(unused_head[:i]) + (l_head+i)**2)
print(ans)

Fixed submission:
N,K = map(int,input().split())
td = sorted([list(map(int,input().split())) for _ in range(N)],key = lambda x: (-x[1],x[0]))

head = []
no_head = []
is_used = [False]*(N+1)
for t,d in td[:K]:
    if is_used[t]:
        no_head.append(d)
    else:
        head.append(d)
        is_used[t] = True

unused_head = []
for t,d in td[K:]:
    if not is_used[t]:
        unused_head.append(d)
        is_used[t] = True
        
n = min(len(no_head),len(unused_head))
sum_head = sum(head)
sum_no_head = sum(no_head)
sum_unused_head = 0
l_head = len(head)
l_no_head = len(no_head)
ans = sum_head + sum_no_head + l_head ** 2
for i in range(n):
    sum_no_head -= no_head[-1-i]
    sum_unused_head += unused_head[i]
    ans = max(ans,sum_head+sum_no_head+sum_unused_head + (l_head+i+1)**2)
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N,K = map(int,input().split())
t,d = list(zip(*sorted([list(map(int,input().split())) for _ in range(N) ],key=lambda x: (-x[1],x[0]))))

def get_value(sushi):
    ret = 0
    var = set()
    for i in sushi:
        ret += d[i]
        var.add(t[i])
    l = len(var)
    return ret + l*l

sushi = set()
sushi = set([(i,sushi.add(i))[0] for i in range(N) if t[i] not in [t[j] for j in sushi]][:K])
sushi |= set(list(set(range(N))-sushi)[:K-len(sushi)])

while 1:
    tmp = sushi - {max(sushi)}
    tmp.add(min(set(range(N)) - tmp))
    if get_value(tmp) <= get_value(sushi):
        break
    else:
        sushi = tmp
print(get_value(sushi))

Fixed submission:
N,K = map(int,input().split())
td = sorted([list(map(int,input().split())) for _ in range(N)],key = lambda x: (-x[1],x[0]))

head = []
no_head = []
is_used = [False]*(N+1)
for t,d in td[:K]:
    if is_used[t]:
        no_head.append(d)
    else:
        head.append(d)
        is_used[t] = True

unused_head = []
for t,d in td[K:]:
    if not is_used[t]:
        unused_head.append(d)
        is_used[t] = True
        
n = min(len(no_head),len(unused_head))
sum_head = sum(head)
sum_no_head = sum(no_head)
sum_unused_head = 0
l_head = len(head)
l_no_head = len(no_head)
ans = sum_head + sum_no_head + l_head ** 2
for i in range(n):
    sum_no_head -= no_head[-1-i]
    sum_unused_head += unused_head[i]
    ans = max(ans,sum_head+sum_no_head+sum_unused_head + (l_head+i+1)**2)
print(ans)
Buggy python submission (verdict: Runtime Error):
S = input()
N = len(S)

ans = false
for i in range(N):
  for j in range(i,N):
    if S[:i]+S[j:] == "keyence":
      print("YES")
      ans = True
      break
  if ans: break
else:
  print("NO")

Fixed submission:
S = input()
N = len(S)

ans = False
for i in range(N):
  for j in range(i,N):
    if S[:i]+S[j:] == "keyence":
      print("YES")
      ans = True
      break
  if ans: break
else:
  print("NO")
Buggy python submission (verdict: Runtime Error):
N = int(input())
A,B = map(int,input().split())
*P, = map(int,input().split())

a = len([p for p in P if p<=A])
a = min(a,
        len([p for p in P if A<p<=B])
a = min(a,
        len([p for p in P if B<p])
print(a)

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

a = len([p for p in P if p<=A])
a = min(a,
        len([p for p in P if A<p<=B]))
a = min(a,
        len([p for p in P if B<p]))
print(a)
Buggy python submission (verdict: Time Limit Exceeded):
N,K = map(int,input().split())
h = list(map(int,input().split()))

dp = [0]*N
for i in range(1,N):
    dp[i] = min([dp[i-j]+abs(h[i]-h[i-j]) for j in range(1,min(i,K)+1)])
print(dp[-1])

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

dp = [0]*N
for i in range(1,N):
    tmp = 10**10
    for j in range(1,min(i+1,K+1)):
        tmp = min(tmp,dp[i-j]+abs(h[i]-h[i-j]))
    dp[i] = tmp
print(dp[-1])

Buggy python submission (verdict: Time Limit Exceeded):
N,K = map(int,input().split())
h = list(map(int,input().split()))

dp = [0]*N
for i in range(1,N):
    tmp = 10**10
    for j in range(1,min(i+1,K+1)):
        tmp = min(tmp,dp[i-j]+abs(h[i]-h[i-j]))
    dp[i] = tmp
print(dp[-1])

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

dp = [0]*N
for i in range(1,N):
    tmp = 10**10
    for j in range(1,min(i+1,K+1)):
        tmp = min(tmp,dp[i-j]+abs(h[i]-h[i-j]))
    dp[i] = tmp
print(dp[-1])

Buggy python submission (verdict: Time Limit Exceeded):
N,K = map(int,input().split())
h = list(map(int,input().split()))

dp = [0]*N
for i in range(1,N):
    tmp = []
    for j in range(1,K+1):
        if i-j<0:
            continue
        tmp.append(dp[i-j]+abs(h[i]-h[i-j]))
    dp[i] = min(tmp)
print(dp[-1])

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

dp = [0]*N
for i in range(1,N):
    tmp = 10**10
    for j in range(1,min(i+1,K+1)):
        tmp = min(tmp,dp[i-j]+abs(h[i]-h[i-j]))
    dp[i] = tmp
print(dp[-1])