Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
h, w, d = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(h)]

pos = [0] * (h*w + 1)
for i in range(h):
    for j in range(w):
        pos[a[i][j]] = (j, i)

res = []
q = int(input())
for i in range(q):
    l, r = map(int, input().split())

    ans = 0
    px, py = pos[l]
    for j in range(l, r+1, d):
        x, y = pos[j]
        ans += abs(px - x) + abs(py - y)
        px, py = pos[j]

    res.append(ans)

print("\n".join(map(str,res)))


Fixed submission:
h, w, d = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(h)]

pos = [0] * (h*w + 1)
for i in range(h):
    for j in range(w):
        pos[a[i][j]] = (j, i)

dis = [0] * (h*w + 1)
for i in range(h*w+1):
    if i > d:
        x1, y1 = pos[i-d]
        x2, y2 = pos[i]
        dis[i] = abs(x1-x2) + abs(y1-y2) + dis[i-d]

res = []
q = int(input())
for i in range(q):
    l, r = map(int, input().split())

    res.append(dis[r]-dis[l])

print("\n".join(map(str,res)))

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

pos = [0] * (h*w + 1)
for i in range(h):
    for j in range(w):
        pos[a[i][j]] = (j, i)

res = []
q = int(input())
for i in range(q):
    l, r = map(int, input().split())

    ans = 0
    px, py = pos[l]
    for j in range(l, r+1, d):
        x, y = pos[j]
        ans += abs(px - x) + abs(py - y)
        px, py = pos[j]

    res.append(ans)

print("\n".join(map(str,res)))


Fixed submission:
h, w, d = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(h)]

pos = [0] * (h*w + 1)
for i in range(h):
    for j in range(w):
        pos[a[i][j]] = (j, i)

dis = [0] * (h*w + 1)
for i in range(h*w+1):
    if i > d:
        x1, y1 = pos[i-d]
        x2, y2 = pos[i]
        dis[i] = abs(x1-x2) + abs(y1-y2) + dis[i-d]

res = []
q = int(input())
for i in range(q):
    l, r = map(int, input().split())

    res.append(dis[r]-dis[l])

print("\n".join(map(str,res)))
Buggy python submission (verdict: Time Limit Exceeded):
import math

n = int(input())

c = {"Vacant":0, "Male":1, "Female":2}
d = [0] * n

print(0)
d[0] = c[input()]

lb = 1
ub = n
while ub - lb > 1:
    mid = (ub + lb) // 2
    print(mid)
    d[mid] = c[input()]
    len1 = mid - lb
    le2 = ub - mid -1
    if len1 % 2:
        if d[lb-1] == d[mid]:
            lb = mid + 1
        else:
            ub = mid
    else:
        if d[lb-1] == d[mid]:
            ub = mid
        else:
            lb = mid + 1


Fixed submission:
n = int(input())

lb, ub = 0, n
print(lb, flush=True)
s = str(input())
if s == 'Vacant':
    exit()
for i in range(19):
    mid = (lb + ub) // 2
    print(mid, flush=True)
    t = str(input())
    if t == 'Vacant':
        exit()
    if (mid - lb) % 2 == 0 and s == t:
        lb = mid
    elif (mid - lb) % 2 == 0 and s != t:
        ub = mid
    elif s == t:
        ub = mid
    else:
        lb, s = mid, t
Buggy python submission (verdict: Time Limit Exceeded):
n, y = map(int, input().split())

for i in range(n+1):
    for j in range(n+1):
        for k in range(n+1):
            if i + j + k == n and 10000*i + 5000*j + 1000*k == y:
                print(i, j, k)
                exit()

print(-1, -1, -1)


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

for i in range(n+1):
    for j in range(n+1):
        k = n - i - j
        if 0 <= k <= n and 10000*i + 5000*j + 1000*k == y:
            print(i, j, k)
            exit()

print(-1, -1, -1)
Buggy python submission (verdict: Runtime Error):
s = input()
t = input()

result = []
for i in range(len(s)-len(t)+1):
    temp = '?'*i + t + '?'*(len(s)-len(t)-i)
    
    ans = ''
    flag = True
    for j in range(len(s)):
        if s[j] == '?' or s[j] == temp[j]:
            ans += temp[j]
        elif s[j] != '?' and temp[j] == '?':
            ans += s[j]
        else:
            flag = False

    if flag:
        result.append(ans)

if ans:
    result.sort()
    print(result[0])
else:
    print("UNRESTORABLE")

Fixed submission:
s = input()
t = input()

result = []
for i in range(len(s)-len(t)+1):
    temp = '?'*i + t + '?'*(len(s)-len(t)-i)
    
    ans = ''
    flag = True
    for j in range(len(s)):
        if s[j] == '?' or s[j] == temp[j]:
            ans += temp[j]
        elif s[j] != '?' and temp[j] == '?':
            ans += s[j]
        else:
            flag = False

    if flag:
        result.append(ans.replace('?', 'a'))

if result:
    result.sort()
    print(result[0])
else:
    print("UNRESTORABLE")
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
A = [list(map(int, input().split())) for _ in range(n)]
B = [[1] * n for _ in range(n)]

for k in range(n):
    for i in range(n):
        for j in range(n):
            if k != i and k != j:
                if A[i][j] > A[i][k] + A[k][j]:
                    print(-1)
                    exit()
                elif A[i][j] == A[i][k] + A[k][j]:
                    B[i][j] = 0

ans = 0
for i in range(n):
    for j in range(i):
        if B[i][j]:
            ans += A[i][j]

print(ans)


Fixed submission:
n = int(input())
A = [list(map(int, input().split())) for _ in range(n)]
B = [[1] * n for _ in range(n)]

for k in range(n):
    for i in range(n):
        for j in range(n):
            if k != i and k != j:
                if A[i][j] > A[i][k] + A[k][j]:
                    print(-1)
                    exit()
                elif A[i][j] == A[i][k] + A[k][j]:
                    B[i][j] = 0

ans = 0
for i in range(n):
    for j in range(i):
        if B[i][j]:
            ans += A[i][j]

print(ans)
Buggy python submission (verdict: Runtime Error):
n = int(input())
p = list(map(int, input().split()))

ans = 0
for i in range(n):
    if i+1 == p[i]:
        temp = p[i]
        p[i] = p[i+1]
        p[i+1] = temp
        ans += 1
    if i == n-1 and i+1 == p[i]:
        ans += 1        

print(ans)


Fixed submission:
n = int(input())
p = list(map(int, input().split()))

ans = 0
for i in range(n):
    if i == n-1 and i+1 == p[i]:
        ans += 1
    elif i+1 == p[i]:
        temp = p[i]
        p[i] = p[i+1]
        p[i+1] = temp
        ans += 1


print(ans)

Buggy python submission (verdict: Runtime Error):
n = int(input())
p = list(map(int, input().split()))

ans = 0
for i in range(n):
    if i+1 == p[i]:
        temp = p[i]
        p[i] = p[i+1]
        p[i+1] = temp
        ans += 1

print(ans)


Fixed submission:
n = int(input())
p = list(map(int, input().split()))

ans = 0
for i in range(n):
    if i == n-1 and i+1 == p[i]:
        ans += 1
    elif i+1 == p[i]:
        temp = p[i]
        p[i] = p[i+1]
        p[i+1] = temp
        ans += 1


print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import heapq

n = int(input())

g = [[] for _ in range(n)]
for i in range(n-1):
    a, b, c = map(int, input().split())

    g[a-1].append((b-1, c))
    g[b-1].append((a-1, c))

ans = []
q, k = map(int, input().split())
for i in range(q):
    x, y = map(int, input().split())
    
    res = 0
    # x -> k
    dis = [float("inf")] * n
    dis[x-1] = 0
    pq = [(0, x-1)]
    while pq:
        d, node = heapq.heappop(pq)
        if d > dis[node]: continue

        for nxt, cost in g[node]:
            if d + cost < dis[nxt]:
                dis[nxt] = d + cost
                heapq.heappush(pq, (dis[nxt], nxt))
    res += dis[k-1]
    # k -> y
    dis = [float("inf")] * n
    dis[k-1] = 0
    pq = [(0, k-1)]
    while pq:
        d, node = heapq.heappop(pq)
        if d > dis[node]: continue

        for nxt, cost in g[node]:
            if d + cost < dis[nxt]:
                dis[nxt] = d + cost
                heapq.heappush(pq, (dis[nxt], nxt))
    res += dis[y-1]
    ans.append(res)

print("\n".join(map(str, ans)))

Fixed submission:
import heapq

n = int(input())

g = [[] for _ in range(n)]
for i in range(n-1):
    a, b, c = map(int, input().split())

    g[a-1].append((b-1, c))
    g[b-1].append((a-1, c))

q, k = map(int, input().split())

dis = [float("inf")] * n
dis[k-1] = 0
pq = [(0, k-1)]
while pq:
    d, node = heapq.heappop(pq)
    if d > dis[node]: continue

    for nxt, cost in g[node]:
        if d + cost < dis[nxt]:
            dis[nxt] = d + cost
            heapq.heappush(pq, (dis[nxt], nxt))

ans = []
for i in range(q):
    x, y = map(int, input().split())

    ans.append(dis[x-1]+dis[y-1])

print("\n".join(map(str, ans)))
Buggy python submission (verdict: Runtime Error):
import functools
import math

n, k = map(int, input().split())
a = list(map(int, input().split()))
m = max(a)

if k > m:
    print("IMPOSSIBLE")
else:
    gcd = functools.reduce(math.gcd, a)
    if k % gcd == 0:
        print("POSSIBLE")
    else:
        print("IMPOSSIBLE")


Fixed submission:
import functools
import fractions

n, k = map(int, input().split())
a = list(map(int, input().split()))
m = max(a)

if k > m:
    print("IMPOSSIBLE")
else:
    gcd = functools.reduce(fractions.gcd, a)
    if k % gcd == 0:
        print("POSSIBLE")
    else:
        print("IMPOSSIBLE")
Buggy python submission (verdict: Runtime Error):
n = int(input())

s = 0
i = 0
while s < n:
    s += i
    i += 1

if i == 1:
    print(1)
    exit()
ans = list(range(1,i))
ans.remove(s-n)
print('\n'.join(map(str,ans)))


Fixed submission:
n = int(input())

s = 0
i = 0
while s < n:
    s += i
    i += 1

if i == 1:
    print(1)
else:
    ans = list(range(1,i))
    if s - n != 0: ans.remove(s-n)
    print('\n'.join(map(str,ans)))
Buggy python submission (verdict: Runtime Error):
s = input()
n = len(s)
k = int(input())

d = [0] * n
for i in range(n):
    if s[i] != 'a':
        d[i] = ord('z') - ord(s[i]) + 1

ans = list(s)
for i in range(n):
    if d[i] != 0 and d[i] <= k:
        k -= d[i]
        ans[i] = 'a'
    if k == 0: break
    if i == n-1:
        ans[i] = chr(ord(s[i]) + k)

print(''.join(ans))


Fixed submission:
s = list(input())
n = len(s)
k = int(input())

for i in range(n):
    x = ord(s[i]) - ord('a')
    if x == 0 or 26 -x > k: continue
    k -= 26 - x
    s[i] = 'a'

if k:
    s[-1] = chr((ord(s[-1]) - ord('a') + k) % 26 + ord('a'))

print(''.join(s))

Buggy python submission (verdict: Runtime Error):
s = input()
n = len(s)
k = int(input())

d = [0] * n
for i in range(n):
    if s[i] != 'a':
        d[i] = ord('z') - ord(s[i]) + 1

ans = list(s)
for i in range(n):
    if d[i] != 0 and d[i] <= k:
        k -= d[i]
        c = ord(s[i]) + d[i]
        ans[i] = chr(c - ord('z') + ord('a') - 1) if c > ord('z') else chr(c)
    if k == 0: break
    if i == n-1:
        ans[i] = chr(ord(s[i]) + k)

print(''.join(ans))


Fixed submission:
s = list(input())
n = len(s)
k = int(input())

for i in range(n):
    x = ord(s[i]) - ord('a')
    if x == 0 or 26 -x > k: continue
    k -= 26 - x
    s[i] = 'a'

if k:
    s[-1] = chr((ord(s[-1]) - ord('a') + k) % 26 + ord('a'))

print(''.join(s))
Buggy python submission (verdict: Runtime Error):
n = int(input())
a = [int(input()) for _ in range(n)]

dp = [0] * n
for i in range(n):
    dp[i] = max(dp[i-1] + a[i]//2,dp[i-2] + min(a[i-1], a[i]))

print(dp[-1])


Fixed submission:
n = int(input())
a = [int(input()) for _ in range(n)]

ans = 0
i = 0
while i < n:
    res = 0
    for j in range(i, n):
        if a[j] == 0: break
        res += a[j]
    ans += res // 2
    i = j + 1

print(ans)
Buggy python submission (verdict: Runtime Error):
s = list(input())
n = len(s)

ans = []
for i in range(n):
    if s[i] == '0':
        ans.append('0')
    if s[i] == '1':
        ans.append('1')
    if s[i] == 'B':
        ans[-1] = ''

print("".join(ans))


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

ans = []
for i in range(n):
    if s[i] == '0':
        ans.append('0')
    if s[i] == '1':
        ans.append('1')
    if s[i] == 'B':
        if ans:
            ans.pop()

print("".join(ans))
Buggy python submission (verdict: Runtime Error):
src/contest/abc/abc153/c.py

Fixed submission:

n, k = list(map(int, input().split()))

h = list(map(int, input().split()))

h.sort(reverse=True)

print(sum(h[min(n,k):]))
Buggy python submission (verdict: Time Limit Exceeded):
h, n = list(map(int, input().split()))
ab = [list(map(int, input().split())) for _ in range(n)]

dp = [0] * (h+max(a for a,b in ab))
for i in range(1, len(dp)):
    dp[i] = min([float('inf')] + [(dp[i-a]+b) for a, b in ab if i-a >= 0])
print(min(dp[h:]))


Fixed submission:
h, n = list(map(int, input().split()))
ab = [list(map(int, input().split())) for _ in range(n)]

dp = [0] * (h+max(a for a,b in ab))
for i in range(1, len(dp)):
    dp[i] = min(dp[i-a]+b for a, b in ab)
print(min(dp[h:]))
Buggy python submission (verdict: Runtime Error):
n = int(input())
a = []
for i in range(n):
  a.append(int(input()))
  
sorted_a = sorted(a)

for v in a:
  if v == sorted[0]:
    print(sorted[1])
  else:
    print(sorted[0])

Fixed submission:
n = int(input())
a = []
for i in range(n):
  a.append(int(input()))
  
sorted_a = sorted(a, reverse=True)

for v in a:
  if v == sorted_a[0]:
    print(sorted_a[1])
  else:
    print(sorted_a[0])
Buggy python submission (verdict: Time Limit Exceeded):
# coding: utf-8

N,M = list(map(int,input().split()))

A = list(map(int,input().split()))
A.sort(reverse=True)

for i in range(M):
    B, C = list(map(int,input().split()))
    A = A + [C] * B
    A.sort(reverse=True)
    A = A[0:N]

print(sum(A))

Fixed submission:
# coding: utf-8

N,M = list(map(int,input().split()))

A = list(map(int,input().split()))

tmp = {}
for i in A:
    if i in tmp.keys():
        tmp[i] += 1
    else:
        tmp[i] = 1 

for i in range(M):
    B, C = list(map(int,input().split()))
    if C in tmp.keys():
        tmp[C] += B
    else:
        tmp[C] = B

ans = 0
for i in sorted(tmp.keys(), reverse = True):
    if N >= tmp[i]:
        N -= tmp[i]
        ans += i * tmp[i]
    else:
        ans += i * N
        break
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
def gcd(a,b):
    if ( b==0 ):
        return a
    else:
        return (gcd(b, a%b))

def reduce_gcd(lst):
    ans = lst.pop(0)
    for i in lst:
        ans = gcd(ans,i)
    return ans

def other_lst(lst,index):
    return [x for i,x in enumerate(lst) if not i == index]

input()
A = list(map(int, input().split()))

print(max([reduce_gcd(other_lst(A,i)) for i in range(len(A)) ]))

Fixed submission:
def gcd(a,b):
    if ( b==0 ):
        return a
    else:
        return (gcd(b, a%b))

input()
A = list(map(int, input().split()))

left_gcd = [A[0]]
for i in A[1:]:
    left_gcd.append(gcd(left_gcd[-1],i))

right_gcd = [A[-1]]
for i in reversed(A[0:-1]):
    right_gcd.append(gcd(right_gcd[-1],i))
right_gcd.reverse()

gcd_lst = [right_gcd[1]] + [gcd(right_gcd[i+1], left_gcd[i-1]) for i in range(1,len(A)-1)] + [left_gcd[-2]]
print(max(gcd_lst))
Buggy python submission (verdict: Runtime Error):
def cal_min_cost(cnt):
    return min([
      abs(hight_list[i] - hight_list[i-diff]) + cost_list[i-diff])
      for diff in range(1,3)
      ])

hight_list = []
cost_list = [0,0]
N = int(input())
hight_list = list(map(int, input().split()))
hight_list.insert(0,self.hight_list[0])
for i in range(2, N+1):
    cost_list.append(cal_min_cost(i))
print(cost_list[-1])
    


Fixed submission:
def cal_min_cost(cnt):
    return min([
      abs(hight_list[i] - hight_list[i-diff]) + cost_list[i-diff]
      for diff in range(1,3)
      ])

hight_list = []
cost_list = [0,0]
N = int(input())
hight_list = list(map(int, input().split()))
hight_list.insert(0,hight_list[0])
for i in range(2, N+1):
    cost_list.append(cal_min_cost(i))
print(cost_list[-1])
Buggy python submission (verdict: Time Limit Exceeded):
def cal_min_cost(num):
    return min([
      abs(hight_list[num] - hight_list[num-diff]) + cost_list[num-diff]
      for diff in range(1,K+1)
      ])

N,K = list(map(int, input().split()))
hight_list = []
cost_list = [0]*K
hight_list = list(map(int, input().split()))
for i in range(K-1):
    hight_list.insert(0,hight_list[0])
for i in range(K, N+K-1):
    cost_list.append(cal_min_cost(i))
print(cost_list[-1])

Fixed submission:
import numpy as np

N,WIDTH = list(map(int, input().split()))

hight_arr = np.array(list(map(int, input().split())))
cost_arr = np.zeros(N,dtype=int)

for i in range(1,N):
    start = max(i-WIDTH,0)
    cost_arr[i] = np.min(np.abs(hight_arr[i] - hight_arr[start:i]) + cost_arr[start:i])
print(cost_arr[-1])
Buggy python submission (verdict: Runtime Error):
n = input()
flag = [0 for i in xrange(n)]
a = []
b = []
for i in xrange(n):
	x,y = map(int, raw_input().split())
	a.append((x,y,i))
	b.append((y,x,i))
a.sort(reverse = True)
b.sort(reverse = True)
ptr1 = 0
ptr2 = 0
turn = 0
ans1 = 0
ans2 = 0
while ptr1 < n and ptr2 < n:
	if turn == 0:
		while flag[a[ptr1][2]] == 1:
			ptr1 += 1
		if ptr1 < n:
			ans1 += a[ptr1][0]
			flag[a[ptr1][2]] = 1
			ptr1 += 1
		turn = 1
	else:
		while flag[b[ptr2][2]] == 1:
			ptr2 += 1
		if ptr2 < n:
			ans2 += b[ptr2][0]
			flag[b[ptr2][2]] = 1
			ptr2 += 1
		turn = 0
print ans1-ans2


Fixed submission:
n = input()
ans = 0
l = []
for i in xrange(n):
	a,b = map(int, raw_input().split())
	ans -= b
	l.append(a+b)
l.sort(reverse = True)
for i in xrange(0,n,2):
	ans += l[i]
print ans
Buggy python submission (verdict: Runtime Error):
s = raw_input()
k = input()
index = -1
for i in xrange(len(s)):
	if s[i] > '1':
		index = i
		break
index += 1
if k >= index:
	print s[index]
else:
	print 1

Fixed submission:
s = raw_input()
k = input()
index = -1
for i in xrange(len(s)):
	if s[i] > '1':
		index = i
		break
index += 1
if k >= index:
	print s[index-1]
else:
	print 1
Buggy python submission (verdict: Time Limit Exceeded):
from fractions import gcd

MOD = 1000000000 + 7

N = int(input())
A = list(map(int, input().split()))

def lcm(x, y):
    return (x * y) // gcd(x, y)

l = 1
for i in A:
    l = lcm(l, i)

ans = 0
for i in A:
    ans += (l // i) % MOD
print(int(ans % MOD))


Fixed submission:
from fractions import gcd

MOD = 1000000000 + 7

N = int(input())
A = list(map(int, input().split()))

l = 1
ans = 0
for a in A:
    g = gcd(a, l)
    l = (l // g) * a
    ans = (ans * (a // g)) % MOD
    ans = (ans + (l // a)) % MOD
print(int(ans))

Buggy python submission (verdict: Runtime Error):
from fractions import gcd

MOD = 1000000000 + 7

N = int(input())
A = list(map(int, input().split()))

l = 1
ans = 0
for a in A:
    g = gcd(a, l)
    ans = (ans * (a // g)) % MOD
    l = l * a // g
    ans = (ans + (l / a) % MOD) % MOD
print(int(ans))


Fixed submission:
from fractions import gcd

MOD = 1000000000 + 7

N = int(input())
A = list(map(int, input().split()))

l = 1
ans = 0
for a in A:
    g = gcd(a, l)
    l = (l // g) * a
    ans = (ans * (a // g)) % MOD
    ans = (ans + (l // a)) % MOD
print(int(ans))

Buggy python submission (verdict: Runtime Error):
from fractions import gcd

MOD = 1000000000 + 7

N = int(input())
A = list(map(int, input().split()))

def lcm(x, y):
    return (x * y) // gcd(x, y)

l = 1
ans = 0
for a in A:
    g = gcd(a, l)
    ans = ((ans * a) // g) % MOD
    l = lcm(l, a)
    ans = (ans + (l / a) % MOD) % MOD
print(int(ans))

Fixed submission:
from fractions import gcd

MOD = 1000000000 + 7

N = int(input())
A = list(map(int, input().split()))

l = 1
ans = 0
for a in A:
    g = gcd(a, l)
    l = (l // g) * a
    ans = (ans * (a // g)) % MOD
    ans = (ans + (l // a)) % MOD
print(int(ans))

Buggy python submission (verdict: Time Limit Exceeded):
from fractions import gcd

MOD = 1000000000 + 7

N = int(input())
A = list(map(int, input().split()))

def lcm(x, y):
    return (x * y) // gcd(x, y)

l = 1
for i in A:
    l = lcm(l, i)

ans = 0
for i in A:
    ans += (l // i) % MOD
print(int(ans % MOD))

Fixed submission:
from fractions import gcd

MOD = 1000000000 + 7

N = int(input())
A = list(map(int, input().split()))

l = 1
ans = 0
for a in A:
    g = gcd(a, l)
    l = (l // g) * a
    ans = (ans * (a // g)) % MOD
    ans = (ans + (l // a)) % MOD
print(int(ans))

Buggy python submission (verdict: Runtime Error):
import math

MOD = 1000000000 + 7

N = int(input())
A = list(map(int, input().split()))

def lcm(x, y):
    return (x * y) // math.gcd(x, y)

l = 1
for i in A:
    l = lcm(l, i)

ans = 0
for i in A:
    ans += (l // i) % MOD
print(int(ans % MOD))

Fixed submission:
from fractions import gcd

MOD = 1000000000 + 7

N = int(input())
A = list(map(int, input().split()))

l = 1
ans = 0
for a in A:
    g = gcd(a, l)
    l = (l // g) * a
    ans = (ans * (a // g)) % MOD
    ans = (ans + (l // a)) % MOD
print(int(ans))
Buggy python submission (verdict: Time Limit Exceeded):
X, Y, Z, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

AB = list()
for i in A:
    for j in B:
        AB.append(i+j)

AB.sort(reverse=True)
ABC = list()

for i in AB[:K]:
    for j in C:
        ABC.append(i+j)

ABC.sort(reverse=True)
for i in range(K):
    print(ABC[i])


Fixed submission:
X, Y, Z, K = 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)

ans = list()
for i in range(X):
    for j in range(Y):
        if (i+1)*(j+1) > K:
            break
        else:
            for k in range(Z):
                if (i+1)*(j+1)*(k+1) > K:
                    break
                else:
                    ans.append(A[i]+B[j]+C[k])

ans.sort(reverse=True)
for i in range(K):
    print(ans[i])
Buggy python submission (verdict: Time Limit Exceeded):
N, M = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]
AB.sort(key=lambda x:x[0])

a = 0
while True:
    s = AB.pop(0)
    if M > s[1]:
        M -= s[1]
        a += s[0] * s[1]
    else:
        a += s[0] * M
        break

print(a)

Fixed submission:
N, M = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]
AB.sort(key=lambda x:x[0])

a = 0
while True:
    s = AB.pop(0)
    if M > s[1]:
        M -= s[1]
        a += s[0] * s[1]
    else:
        a += s[0] * M
        break

print(a)
Buggy python submission (verdict: Runtime Error):
import math

N, M = map(int, input().split())
S = input()
T = input()
gcd = math.gcd(N, M)

if gcd == 1:
    print(N*M)
else:
    sl = [i for i in range(0, N, N//gcd)]
    tl = [i for i in range(0, M, M//gcd)]
    for i in range(len(sl)):
        if S[sl[i]] != T[tl[i]]:
            print(-1)
            break
    else:
        print(N*M//gcd)


Fixed submission:
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a


N, M = map(int, input().split())
S = input()
T = input()
gcd = gcd(N, M)

sl = [i for i in range(0, N, N//gcd)]
tl = [i for i in range(0, M, M//gcd)]
for i in range(len(sl)):
    if S[sl[i]] != T[tl[i]]:
        print(-1)
        break
else:
    print(N*M//gcd)