Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
N = int(input())
As = [int(input()) for _ in range(N)]
from bisect import bisect_right

def LIS(L):
    dp = [L[0]]
    length = len(L)
    for i in range(1, length):
        print(dp)
        a = L[i]
        if a >= dp[-1]:
            dp.append(a)
        else:
            dp[bisect_right(dp, a)] = a
    return dp

print(len(LIS(As[::-1])))

Fixed submission:
N = int(input())
As = [int(input()) for _ in range(N)]
from bisect import bisect_right
from collections import deque

def LIS(L):
    dp = deque([L[0]])
    length = len(L)
    for i in range(1, length):
        a = L[i]
        if a >= dp[-1]:
            dp.append(a)
        else:
            dp[bisect_right(dp, a)] = a
    return dp

print(len(LIS(As[::-1])))

Buggy python submission (verdict: Runtime Error):
N = int(input())
As = [int(input()) for _ in range(N)]
from bisect import bisect_left

def LIS(L):
    dp = [L[0]]
    length = len(L)
    lis = [[0]]*(length+1)
    l = 1
    for i in range(1, length):
        a = L[i]
        if a > dp[-1]:
            dp.append(a)
            l += 1
            lis[l] = dp[:]
        else:
            dp[bisect_left(dp, a)] = a
    for j in lis[l]:
        L.remove(j)
    return L

cnt = 0
while 1:
    L = LIS(As)
    cnt += 1
    if len(L)==0:
        print(cnt)
        break

Fixed submission:
N = int(input())
As = [int(input()) for _ in range(N)]
from bisect import bisect_right
from collections import deque

def LIS(L):
    dp = deque([L[0]])
    length = len(L)
    for i in range(1, length):
        a = L[i]
        if a >= dp[-1]:
            dp.append(a)
        else:
            dp[bisect_right(dp, a)] = a
    return dp

print(len(LIS(As[::-1])))
Buggy python submission (verdict: Runtime Error):
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, X = mapint()
Ls = list(mapint())

now = 0
cnt = 0
for l in Ls:
    if now>X:
        break
    now += l
    cnt += 1
else:
    if now<=x:
        cnt += 1
print(cnt)

Fixed submission:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, X = mapint()
Ls = list(mapint())

now = 0
cnt = 0
for l in Ls:
    if now>X:
        break
    now += l
    cnt += 1
else:
    if now<=X:
        cnt += 1
print(cnt)

Buggy python submission (verdict: Runtime Error):
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, X = mapint()
Ls = list(mapint())

now = 0
cnt = 0
for l in Ls:
    if now>X:
        break
    now += l
    cnt += 1
else:
    if not now>x:
        cnt += 1
print(cnt)

Fixed submission:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, X = mapint()
Ls = list(mapint())

now = 0
cnt = 0
for l in Ls:
    if now>X:
        break
    now += l
    cnt += 1
else:
    if now<=X:
        cnt += 1
print(cnt)
Buggy python submission (verdict: Runtime Error):
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

W, H, x, y = mapint()
if x==W/2 and y==Y//2:
    print(W*H/2, 1)
else:
    print(W*H/2, 0)

Fixed submission:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

W, H, x, y = mapint()
if x==W/2 and y==H/2:
    print(W*H/2, 1)
else:
    print(W*H/2, 0)
Buggy python submission (verdict: Runtime Error):
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N = int(input())
XY = []
for _ in range(N):
    x, y = mapint()
    XY.append((x, y))

from collections import defaultdict, Counter
dic = []
for i in range(N):
    x1, y1 = XY[i]
    for j in range(N):
        if i==j:
            continue
        x2, y2 = XY[j]
        dx, dy = x2-x1, y2-y1
        if dx==0 and dy==0:
            continue
        dic.append((dx, dy))
c = Counter(dic)
(x, y), cnt = c.most_common()[0]
print(N-cnt)

Fixed submission:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N = int(input())
XY = []
for _ in range(N):
    x, y = mapint()
    XY.append((x, y))

from collections import defaultdict, Counter
dic = []
for i in range(N):
    x1, y1 = XY[i]
    for j in range(N):
        if i==j:
            continue
        x2, y2 = XY[j]
        dx, dy = x2-x1, y2-y1
        if dx==0 and dy==0:
            continue
        dic.append((dx, dy))
c = Counter(dic)
if len(c)==0:
    print(N)
else:
    (x, y), cnt = c.most_common()[0]
    print(N-cnt)
Buggy python submission (verdict: Runtime Error):
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N = int(input())
As = list(mapint())
As.sort()
mini = As.pop(0)
maxi = As.pop()

ans = []
for a in As:
    if a>=0:
        ans.append((mini, a))
        mini -= a
    else:
        ans.append(print(maxi, a))
        maxi -= a

print(maxi-mini)
for a in ans:
    print(*a)
    print(maxi, mini)

Fixed submission:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N = int(input())
As = list(mapint())
As.sort()
mini = As.pop(0)
maxi = As.pop()

ans = []
for a in As:
    if a>=0:
        ans.append((mini, a))
        mini -= a
    else:
        ans.append((maxi, a))
        maxi -= a

print(maxi-mini)
for a in ans:
    print(*a)
print(maxi, mini)
Buggy python submission (verdict: Runtime Error):
M, K = map(int, input().split())

if K>=(2**M):
    print(-1)
elif M==0:
    if K==0:
        print(0, 0)
    else:
        print(-1)
elif M==1:
    if K==0:
        print(0, 0, 1, 1)
    else:
        print(0)
else:
    b = [i for i in range(2**M)]
    c = reversed([i for i in range(2**M)])
    print(' '.join(b+[K]+c+[K]))

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

if K>=(2**M):
    print(-1)
elif M==0:
    if K==0:
        print(0, 0)
    else:
        print(-1)
elif M==1:
    if K==0:
        print(0, 0, 1, 1)
    else:
        print(-1)
else:
    b = [str(i) for i in range(2**M) if not i==K]
    c = [str(i) for i in range(2**M-1, -1, -1) if not i==K]
    ans = b+[str(K)]+c+[str(K)]
    print(' '.join(ans))
Buggy python submission (verdict: Runtime Error):
N = int(input())
S = [input() for _ in range(N)]

cnt = 0
end_a = 0
sta_b = 0
a_b = 0
for s in S:
    cnt += s.count('AB')
    if s[-1]=='A' and s[0]=='B':
        a_b += 1
    elif s[-1]=='A':
        end_a += 1
    elif s[0]=='B':
        sta_b += 1

a_b = [a_b, a_b]
if a_b[0]>=end_a:
    cnt += end_a
    a_b[0] -= end_a
    end_a = 0
else:
    cnt += a_b
    a_b[0] = 0
    end_a -= a_b

if a_b[1]>=sta_b:
    cnt += sta_b
    a_b[1] -= sta_b
    sta_b = 0
else:
    cnt += a_b
    a_b[1] = 0
    sta_b -= a_b
cnt += min(end_a, sta_b)
cnt += min(a_b)
print(cnt)

Fixed submission:
N = int(input())
S = [input() for _ in range(N)]

cnt = 0
end_a = 0
sta_b = 0
a_b = 0
for s in S:
    cnt += s.count('AB')
    if s[-1]=='A' and s[0]=='B':
        a_b += 1
    elif s[-1]=='A':
        end_a += 1
    elif s[0]=='B':
        sta_b += 1
if a_b>=1:
    cnt += a_b-1
    if end_a>=1:
        end_a -= 1
        cnt += 1
    if sta_b>=1:
        sta_b -=1
        cnt+=1
cnt += min(end_a, sta_b)

print(cnt)
Buggy python submission (verdict: Runtime Error):
from math import gcd
N = int(input())
As = list(map(int, input().split()))

lis = [0]*N
ans = 0
for k in range(N):
    g = 10**20
    for i in range(N-1):
        if i==k: continue
        for j in range(i+1, N):
            if j==k: continue
            g = min(gcd(As[i], As[j]), g)
    ans = max(ans, g)
if N==2:
    print(max(As))
else:
    print(ans)

Fixed submission:
from fractions import gcd

N = int(input())
As = list(map(int, input().split()))
re_As = As[::-1]
gcds = [0]*(N)
rgcds = [0]*(N)
gcds[0] = 0
rgcds[0] = 0

for i in range(N-1):
    gcds[i+1] = gcd(As[i], gcds[i])
    rgcds[i+1] = gcd(re_As[i], rgcds[i])

rgcds = rgcds[::-1]

ans = [0]*(N+1)

for i, (s, r) in enumerate(zip(gcds, rgcds)):
    ans[i] = gcd(s, r)
    
print(max(ans))

Buggy python submission (verdict: Runtime Error):
from math import gcd
N = int(input())
As = list(map(int, input().split()))

lis = [0]*N
ans = 0
for k in range(N):
    g = 10**20
    for i in range(N-1):
        if i==k: continue
        for j in range(i+1, N):
            if j==k: continue
            g = min(gcd(As[i], As[j]), g)
    ans = max(ans, g)
if N==2:
    print(max(As))
else:
    print(ans)
        

Fixed submission:
from fractions import gcd

N = int(input())
As = list(map(int, input().split()))
re_As = As[::-1]
gcds = [0]*(N)
rgcds = [0]*(N)
gcds[0] = 0
rgcds[0] = 0

for i in range(N-1):
    gcds[i+1] = gcd(As[i], gcds[i])
    rgcds[i+1] = gcd(re_As[i], rgcds[i])

rgcds = rgcds[::-1]

ans = [0]*(N+1)

for i, (s, r) in enumerate(zip(gcds, rgcds)):
    ans[i] = gcd(s, r)
    
print(max(ans))

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = list(map(int, input().split()))
M = []
for i in range(N):
    X = A[:i] + A[i+1:]
    for v in range(max(X), 0, -1):
        if all([x % v == 0 for x in X]):
            M.append(v)
print(max(M))

Fixed submission:
from fractions import gcd

N = int(input())
As = list(map(int, input().split()))
re_As = As[::-1]
gcds = [0]*(N)
rgcds = [0]*(N)
gcds[0] = 0
rgcds[0] = 0

for i in range(N-1):
    gcds[i+1] = gcd(As[i], gcds[i])
    rgcds[i+1] = gcd(re_As[i], rgcds[i])

rgcds = rgcds[::-1]

ans = [0]*(N+1)

for i, (s, r) in enumerate(zip(gcds, rgcds)):
    ans[i] = gcd(s, r)
    
print(max(ans))

Buggy python submission (verdict: Runtime Error):
N = int(input())
A = list(map(int, input().split()))
wh = int(input())
A[wh] = int(input())
ans = 1
for i in range(max(A), 0, -1):
    if all([x % i == 0 for x in A]):
        ans = i
        break
print(ans)

Fixed submission:
from fractions import gcd

N = int(input())
As = list(map(int, input().split()))
re_As = As[::-1]
gcds = [0]*(N)
rgcds = [0]*(N)
gcds[0] = 0
rgcds[0] = 0

for i in range(N-1):
    gcds[i+1] = gcd(As[i], gcds[i])
    rgcds[i+1] = gcd(re_As[i], rgcds[i])

rgcds = rgcds[::-1]

ans = [0]*(N+1)

for i, (s, r) in enumerate(zip(gcds, rgcds)):
    ans[i] = gcd(s, r)
    
print(max(ans))
Buggy python submission (verdict: Runtime Error):
import math
n = int(input())
M = list(map(int, input().split()))
X = [math.abs(x) for x in M]
print(sum(X) - min(X)*2)

Fixed submission:
import math
n = int(input())
M = list(map(int, input().split()))
p = [q < 0 for q in M].count(True)
X = [abs(x) for x in M]
if p % 2 == 0:
    print(sum(X))
else:
    print(sum(X) - min(X)*2)
Buggy python submission (verdict: Time Limit Exceeded):
S = input()
L = len(S)
while 1:
    old = S
    S = S.replace('01', '').replace('10', '')
    if old==S:
        break
print(L-len(S))

Fixed submission:
S = list(input())
L = len(S)
from collections import Counter
c = Counter(S)
one = c['1']
zero = c['0']

print(L-abs(one-zero))

Buggy python submission (verdict: Runtime Error):
S = list(input())
from collections import deque
S = deque(S)
f = S.popleft()
stocked = f
ans = 0
while S:
    n = S.popleft()
    if f!=n:
        ans += 1
        if not S:
            break
        f = S.popleft()
    else:
        stocked = f
        f = n
if stocked!=n:
    ans += 1
print(ans*2)

Fixed submission:
S = list(input())
L = len(S)
from collections import Counter
c = Counter(S)
one = c['1']
zero = c['0']

print(L-abs(one-zero))

Buggy python submission (verdict: Time Limit Exceeded):
S = input()
L = len(S)
while 1:
    l = len(S)
    S = S.replace('01', '').replace('10', '')
    l2 = len(S)
    if l==l2:
        break
print(L-l2)

Fixed submission:
S = list(input())
L = len(S)
from collections import Counter
c = Counter(S)
one = c['1']
zero = c['0']

print(L-abs(one-zero))
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**5)

N, M = map(int, input().split())
AB = [list(map(lambda x: int(x)-1, input().split())) for _ in range(M)][::-1]
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [-x for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

uf = UnionFind(N)
ans = []
for a, b in AB:
    roots = uf.roots()
    ans.append(sum([i*(N-i) for i in roots]))
    uf.union(a, b)
for a in ans[::-1]:
    print(a//2)

Fixed submission:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**5)

N, M = map(int, input().split())
AB = [list(map(lambda x: int(x)-1, input().split())) for _ in range(M)][::-1]
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [-x for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

uf = UnionFind(N)
ans = []
cnt = N*(N-1)//2
for a, b in AB:
    ans.append(cnt)
    if uf.same(a, b):
        continue
    cnt -= uf.size(a)*uf.size(b)
    uf.union(a, b)
for a in ans[::-1]:
    print(a)
Buggy python submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10**9)
Input = open('input.txt')
def input(): return Input.readline()
def mapint(): return map(int, input().split())

N, A, B, C = mapint()
Ls = [int(input()) for _ in range(N)]
ans = 10**18
def dfs(a, b, c, idx, magic):
    global ans
    if idx==N:
        if a==0 or b==0 or c==0:
            return
        magic -= 30
        magic += abs(A-a)
        magic += abs(B-b)
        magic += abs(C-c)
        ans = min(ans, magic)
        return
    nx = Ls[idx]
    dfs(a+nx, b, c, idx+1, magic+10)
    dfs(a, b+nx, c, idx+1, magic+10)
    dfs(a, b, c+nx, idx+1, magic+10)
    dfs(a, b, c, idx+1, magic)

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

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

L = [int(input()) for _ in range(N)]

ans = []
def dfs(idx, a, b, c, mp10):
    if idx==N:
        if a and b and c:
            ans.append(abs(A-a)+abs(B-b)+abs(C-c)+mp10*10)
    else:
        dfs(idx+1, a, b, c, mp10)
        dfs(idx+1, a+L[idx], b, c, mp10+1)
        dfs(idx+1, a, b+L[idx], c, mp10+1)
        dfs(idx+1, a, b, c+L[idx], mp10+1)

dfs(0, 0, 0, 0, -3)

print(min(ans))
Buggy python submission (verdict: Time Limit Exceeded):
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, M = mapint()
As = list(mapint())
num_lis = [2, 5, 5, 4, 5, 6, 3, 7, 6]
need_m = [num_lis[a-1] for a in As]
dp = [-1]*(N+1)
dp[0] = 0

for i in range(1, N+1):
    for a, need in zip(As, need_m):
        if need>i:
            continue
        elif dp[i-need]==-1:
            continue
        elif dp[i-need]==0:
            dp[i] = max(dp[i], a)
        else:
            dp[i] = max(dp[i], int(str(a)+str(dp[i-need])))

print(dp[-1])

Fixed submission:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, M = mapint()
As = list(mapint())
num_lis = [2, 5, 5, 4, 5, 6, 3, 7, 6]
need_m = [num_lis[a-1] for a in As]
dp = [-1]*(N+1)
dp[0] = 0

for i in range(1, N+1):
    for a, need in zip(As, need_m):
        if need>i:
            continue
        elif dp[i-need]==-1:
            continue
        elif dp[i-need]==0:
            dp[i] = max(dp[i], a)
        else:
            dp[i] = max(dp[i], dp[i-need]*10+a)

print(dp[-1])

Buggy python submission (verdict: Time Limit Exceeded):
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, M = mapint()
As = list(mapint())
num_lis = [2, 5, 5, 4, 5, 6, 3, 7, 6]
dp = [-1]*(N+1)
dp[0] = 0

for i in range(1, N+1):
    for a in As:
        need = num_lis[a-1]
        if need>i:
            continue
        elif dp[i-need]==-1:
            continue
        elif dp[i-need]==0:
            dp[i] = max(dp[i], a)
        else:
            dp[i] = max(dp[i], int(str(a)+str(dp[i-need])))

print(dp[-1])

Fixed submission:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, M = mapint()
As = list(mapint())
num_lis = [2, 5, 5, 4, 5, 6, 3, 7, 6]
need_m = [num_lis[a-1] for a in As]
dp = [-1]*(N+1)
dp[0] = 0

for i in range(1, N+1):
    for a, need in zip(As, need_m):
        if need>i:
            continue
        elif dp[i-need]==-1:
            continue
        elif dp[i-need]==0:
            dp[i] = max(dp[i], a)
        else:
            dp[i] = max(dp[i], dp[i-need]*10+a)

print(dp[-1])
Buggy python submission (verdict: Runtime Error):
N, K = map(int, input().split())
As = list(map(int, input().split()))
bitK = K.bit_length()
ans = [0]*bitK
for a in As:
    for i in range(bitK):
        if not (a>>i)&1:
            ans[i] += 1

ans = ans[::-1]
string = ['0']*bitK
for i, a in enumerate(ans):
    if a>=N/2:
        string[i] = '1'
        if int(''.join(string), 2)>K:
            string[i] = '0'
num = int(''.join(string), 2)
print(sum([x^num for x in As]))

Fixed submission:
N, K = map(int, input().split())
As = list(map(int, input().split()))
bitK = K.bit_length()
ans = [0]*bitK
for a in As:
    for i in range(bitK):
        if not (a>>i)&1:
            ans[i] += 1

ans = ans[::-1]
string = ['0']*bitK
if bitK==0:
    print(sum(As))
else:
    for i, a in enumerate(ans):
        if a>=N/2:
            string[i] = '1'
            if int(''.join(string), 2)>K:
                string[i] = '0'
    num = int(''.join(string), 2)
    print(sum([x^num for x in As]))

Buggy python submission (verdict: Runtime Error):
N, K = map(int, input().split())
As = list(map(int, input().split()))
bitK = K.bit_length()
ans = [0]*bitK
for a in As:
    for i in range(bitK):
        if (a>>i)&1:
            ans[i] += 1

string = ['0']*bitK
for i, a in enumerate(ans):
    if a>=N//2:
        string[i] = '1'
        if int(''.join(string), 2)>K:
            string[i] = '0'
num = int(''.join(string), 2)
print(sum([x^num for x in As]))

Fixed submission:
N, K = map(int, input().split())
As = list(map(int, input().split()))
bitK = K.bit_length()
ans = [0]*bitK
for a in As:
    for i in range(bitK):
        if not (a>>i)&1:
            ans[i] += 1

ans = ans[::-1]
string = ['0']*bitK
if bitK==0:
    print(sum(As))
else:
    for i, a in enumerate(ans):
        if a>=N/2:
            string[i] = '1'
            if int(''.join(string), 2)>K:
                string[i] = '0'
    num = int(''.join(string), 2)
    print(sum([x^num for x in As]))
Buggy python submission (verdict: Time Limit Exceeded):
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, M = mapint()
parents = [-1]*N
query = [[] for _ in range(N)]
for _ in range(N+M-1):
    a, b = mapint()
    parents[b-1] = a-1
    query[a-1].append(b-1)

for i, c in enumerate(parents):
    if c==-1:
        root = i
        break

from collections import deque
Q = deque([root])
while Q:
    v = Q.popleft()
    for nx in query[v]:
        parents[nx] = v
        Q.append(nx)

for p in parents:
    print(p+1)

Fixed submission:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, M = mapint()
parents = [-1]*N
query = [[] for _ in range(N)]
get_into = [0]*N
for _ in range(N+M-1):
    a, b = mapint()
    parents[b-1] = a-1
    get_into[b-1] += 1
    query[a-1].append(b-1)

for i, c in enumerate(parents):
    if c==-1:
        root = i
        break

from collections import deque
Q = deque([root])
while Q:
    v = Q.popleft()
    for nx in query[v]:
        get_into[nx] -= 1
        if get_into[nx]==0:
            parents[nx] = v
            Q.append(nx)

for p in parents:
    print(p+1)
Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int, input().split())
steps = list(map(int, input().split()))
costs = [0]*(N+1)
for i in range(1, N):
  if i<=K:
    k = i
  choices = [costs[i-j] + abs(steps[i]-steps[i-j]) for j in range(1, k+1)]
  costs[i] = min(choices)
print(costs[N-1])

Fixed submission:
N, K = map(int, input().split())
steps = list(map(int, input().split()))
costs = [0]*(N+1)
for i in range(1, N):
  if i<=K:
    k = i
  choices = [costs[i-j] + abs(steps[i]-steps[i-j]) for j in range(1, k+1)]
  costs[i] = min(choices)
print(costs[N-1])
Buggy python submission (verdict: Time Limit Exceeded):
N, W = map(int, input().split())
dp = [[0]*(W+1) for _ in range(N+1)]
for i in range(N):
  w, v = map(int, input().split())
  for j in range(W+1):
    if j<w:
      dp[i][j] = dp[i-1][j]
      continue
    dp[i][j] = max(dp[i-1][j-w]+v, dp[i-1][j])
print(max(dp[N-1]))

Fixed submission:
N, W = map(int, input().split())
dp = [[0]*(W+1) for _ in range(N+1)]
for i in range(N):
  w, v = map(int, input().split())
  for j in range(W+1):
    if j<w:
      dp[i][j] = dp[i-1][j]
      continue
    dp[i][j] = max(dp[i-1][j-w]+v, dp[i-1][j])
print(max(dp[N-1]))

Buggy python submission (verdict: Time Limit Exceeded):
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][j] = dp[i-1][j]
      continue
    dp[i][j] = max(dp[i-1][j-w]+v, dp[i-1][j])
print(max(dp[N-1]))

Fixed submission:
N, W = map(int, input().split())
dp = [[0]*(W+1) for _ in range(N+1)]
for i in range(N):
  w, v = map(int, input().split())
  for j in range(W+1):
    if j<w:
      dp[i][j] = dp[i-1][j]
      continue
    dp[i][j] = max(dp[i-1][j-w]+v, dp[i-1][j])
print(max(dp[N-1]))
Buggy python submission (verdict: Time Limit Exceeded):
N, M = map(int, input().split())
from bisect import bisect_right
dic = [[] for i in range(N)]

shi = {}
for i in range(M):
    p, y = map(int, input().split())
    dic[p-1].insert(bisect_right(dic[p-1], y), y)
    shi[i] = (p, y)

for j in range(M):
    p, y = shi[j]
    print('{:06}{:06}'.format(p, bisect_right(dic[p-1], y)))



Fixed submission:
N, M = map(int, input().split())
from bisect import bisect_right
dic = [[] for i in range(N)]

shi = {}
for i in range(M):
    p, y = map(int, input().split())
    dic[p-1].append(y)
    shi[i] = (p, y)

for i in range(N):
    dic[i].sort()

for j in range(M):
    p, y = shi[j]
    print('{:06}{:06}'.format(p, bisect_right(dic[p-1], y)))