Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
import sys
from collections import deque
from heapq import heappop, heappush

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n, k = map(int, input().split())
    LD = [[] for _ in range(n)]
    for _ in range(n):
        t, d = map(int, input().split())
        LD[t - 1].append([d, 0] if len(LD[t - 1]) else [d, 1])

    ALL = []
    for ld in LD:
        ALL.extend(ld)
    ALL.sort(reverse=True)
    que = deque(ALL)

    x = y = 0
    zero, one = [], []
    for _ in range(k):
        d, ex = que.popleft()
        x += d
        y += ex
        heappush(zero, d) if ex == 0 else heappush(one, d)

    res = x + y ** 2
    while que:
        d, ex = que.popleft()
        if ex:
            if zero:
                x += d - heappop(zero)
                y += 1
                res = max(res, x + y ** 2)
            else:
                x += d - heappop(one)
                res = max(res, x + y ** 2)
    print(res)


if __name__ == '__main__':
    resolve()


Fixed submission:
import sys
from collections import deque
from heapq import heappop, heappush

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n, k = map(int, input().split())
    TD = [list(map(int, input().split())) for _ in range(n)]
    TD.sort(key=lambda z: -z[1])
    TD_new = [[] for _ in range(n)]
    for t, d in TD:
        TD_new[t - 1].append([d, 0] if len(TD_new[t - 1]) else [d, 1])

    ALL = []
    for td in TD_new:
        ALL.extend(td)
    ALL.sort(reverse=True)
    que = deque(ALL)

    x = y = 0
    zero = []
    for _ in range(k):
        d, ex = que.popleft()
        x += d
        y += ex
        if ex == 0:
            heappush(zero, d)

    res = x + y ** 2
    while que:
        d, ex = que.popleft()
        if ex:
            if zero:
                x += d - heappop(zero)
                y += 1
                res = max(res, x + y ** 2)
            else:
                break

    print(res)


if __name__ == '__main__':
    resolve()
Buggy python submission (verdict: Runtime Error):
s = list(input())
n = len(s)

if "".join(s) == "keyence":
	print("YES")
	eixt()

for i in range(n):
	ss = s[::]
	for j in range(i, n):
		ss.pop(i)
		print("".join(ss))
		if "".join(ss) == "keyence":
			print("YES")
			break
	else:
		continue
	break
else:
	print("NO")

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

if "".join(s) == "keyence":
	print("YES")
	exit()

for i in range(n):
	ss = s[::]
	for j in range(i, n):
		ss.pop(i)
		if "".join(ss) == "keyence":
			print("YES")
			break
	else:
		continue
	break
else:
	print("NO")
Buggy python submission (verdict: Time Limit Exceeded):
import sys
from bisect import bisect_left

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n, m = map(int, input().split())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    if len(A) != len(set(A)) or len(B) != len(set(B)):
        print(0)
        exit()
    A.sort()
    B.sort()
    As = set(A)
    Bs = set(B)
    res = 1
    for x in reversed(range(1, n * m + 1)):
        if x in As and x in Bs:
            continue
        elif x in A:
            res *= m - bisect_left(B, x)
        elif x in B:
            res *= n - bisect_left(A, x)
        else:
            s = m - bisect_left(B, x)
            t = n - bisect_left(A, x)
            res *= s * t - (n * m - x)
        res %= mod
    print(res)


if __name__ == '__main__':
    resolve()


Fixed submission:
import sys
from bisect import bisect_left

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n, m = map(int, input().split())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    if len(A) != len(set(A)) or len(B) != len(set(B)):
        print(0)
        exit()
    A.sort()
    B.sort()
    As = set(A)
    Bs = set(B)
    res = 1
    for x in reversed(range(1, n * m + 1)):
        if x in As and x in Bs:
            continue
        elif x in A:
            res *= m - bisect_left(B, x)
        elif x in B:
            res *= n - bisect_left(A, x)
        else:
            s = m - bisect_left(B, x)
            t = n - bisect_left(A, x)
            res *= s * t - (n * m - x)
        res %= mod
    print(res)


if __name__ == '__main__':
    resolve()
Buggy python submission (verdict: Time Limit Exceeded):
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n, w = map(int, input().split())
    goods = [list(map(int, input().split())) for _ in range(n)]

    dp = [[0 for _ in range(w + 1)] for _ in range(n + 1)]
    for j in range(1, w + 1):
        for i in range(1, n + 1):
            w, v = goods[i - 1]
            if j - w >= 0:
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w] + v)
            else:
                dp[i][j] = dp[i - 1][j]

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


if __name__ == '__main__':
    resolve()


Fixed submission:
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n, w = map(int, input().split())
    goods = [list(map(int, input().split())) for _ in range(n)]

    dp = [[0 for _ in range(w + 1)] for _ in range(n + 1)]
    for j in range(1, w + 1):
        for i in range(1, n + 1):
            w, v = goods[i - 1]
            if j - w >= 0:
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w] + v)
            else:
                dp[i][j] = dp[i - 1][j]

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


if __name__ == '__main__':
    resolve()
Buggy python submission (verdict: Time Limit Exceeded):
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    S = list(input())
    T = list(input())

    LCS = [[0 for _ in range(len(T) + 1)] for _ in range(len(S) + 1)]
    for i in range(1, len(S) + 1):
        for j in range(1, len(T) + 1):
            x = 1 if S[i - 1] == T[j - 1] else 0
            LCS[i][j] = max(LCS[i - 1][j - 1] + x, LCS[i - 1][j], LCS[i][j - 1])

    res = ""
    i, j = len(S), len(T)
    while i > 0 and j > 0:
        if LCS[i][j] == LCS[i - 1][j]:
            i -= 1
        elif LCS[i][j] == LCS[i][j - 1]:
            j -= 1
        else:
            res += S[i - 1]
            i -= 1
            j -= 1

    print(res[::-1])


if __name__ == '__main__':
    resolve()


Fixed submission:
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    S = list(input())
    T = list(input())

    LCS = [[0 for _ in range(len(T) + 1)] for _ in range(len(S) + 1)]
    for i in range(1, len(S) + 1):
        for j in range(1, len(T) + 1):
            x = 1 if S[i - 1] == T[j - 1] else 0
            LCS[i][j] = max(LCS[i - 1][j - 1] + x, LCS[i - 1][j], LCS[i][j - 1])

    res = []
    i, j = len(S), len(T)
    while i > 0 and j > 0:
        if LCS[i][j] == LCS[i - 1][j]:
            i -= 1
        elif LCS[i][j] == LCS[i][j - 1]:
            j -= 1
        else:
            res.append(S[i - 1])
            i -= 1
            j -= 1

    print("".join(res[::-1]))


if __name__ == '__main__':
    resolve()
Buggy python submission (verdict: Time Limit Exceeded):
import sys
from collections import deque

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n, m = map(int, input().split())
    tree = [[] for _ in range(n)]
    for _ in range(m):
        a, b = map(int, input().split())
        tree[a - 1].append([b - 1, 1])
        tree[b - 1].append([a - 1, -1])

    def bfs(v):
        q = deque()
        q.append(v)
        while q:
            u = q.popleft()
            for nv, d in tree[u]:
                if d == 1:
                    dist[nv] = max(dist[nv], dist[u] + d)
                    q.append(nv)

    dist = [0 for _ in range(n)]
    for i in range(n):
        if dist[i] == 0:
            bfs(i)

    print(max(dist))


if __name__ == '__main__':
    resolve()


Fixed submission:
import sys
from collections import deque
sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n, m = map(int, input().split())

    # 各頂点の次数
    deg = [0 for _ in range(n)]
    # グラフ
    edge = [[] for _ in range(n)]
    for _ in range(m):
        a, b = map(int, input().split())
        edge[a - 1].append(b - 1)
        deg[b - 1] += 1

    que = deque([])
    for i in range(n):
        if deg[i] == 0:
            que.append(i)

    dp = [0 for _ in range(n)]
    while que:
        v = que.popleft()
        for nv in edge[v]:
            deg[nv] -= 1
            if deg[nv] == 0:
                que.append(nv)
                dp[nv] = max(dp[nv], dp[v] + 1)

    res = 0
    for j in range(n):
        res = max(res, dp[j])
    print(res)


if __name__ == '__main__':
    resolve()
Buggy python submission (verdict: Time Limit Exceeded):
def prime_factorization(n):
    res = []
    for i in range(2, int(pow(n, 0.5)) + 1):
        if n % i == 0:
            ex = 0
            while n % i == 0:
                ex += 1
                n //= i
            res.append([i, ex])
    if n != 1:
        res.append([n, 1])
    return res


n, p = map(int, input().split())
res = prime_factorization(p)
ans = [1 for _ in range(n)]
for p in res:
    k = p[1]
    while k:
        for i in range(n):
            if k == 0:
                break
            ans[i] *= p[0]
            k -= 1

print(min(ans))


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

res = []
for i in range(2, int(pow(p, 0.5)) + 1):
    if p % i == 0:
        ex = 0
        while p % i == 0:
            ex += 1
            p //= i
        res.append([i, ex])
if p != 1:
    res.append([p, 1])

ans = 1
for p in res:
    k = p[1]
    while k:
        if k < n:
            k = 0
        else:
            ans *= p[0]
            k -= n
print(ans)
Buggy python submission (verdict: Runtime Error):
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a


def lcm(a, b):
    return a * b // gcd(a, b)


def resolve():
    n, m = map(int, input().split())
    s = input()
    t = input()

    L = lcm(n, m)

    X = [""] * L
    for i in range(n):
        idx = (L // n) * i
        X[idx] = s[i]

    for i in range(m):
        idx = (L // m) * i
        if X[idx] != "" and X[idx] != t[i]:
            print("-1")
            break
    else:
        print(L)


if __name__ == '__main__':
    resolve()


Fixed submission:
import sys
from collections import defaultdict

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a


def lcm(a, b):
    return a * b // gcd(a, b)


def resolve():
    n, m = map(int, input().split())
    s = input()
    t = input()

    L = lcm(n, m)

    X = dict()
    for i in range(n):
        idx = (L // n) * i
        X[idx] = s[i]

    for i in range(m):
        idx = (L // m) * i
        if X.get(idx) != None and X[idx] != t[i]:
            print("-1")
            break
    else:
        print(L)


if __name__ == '__main__':
    resolve()

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

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a


def lcm(a, b):
    return a * b // gcd(a, b)


def resolve():
    n, m = map(int, input().split())
    s = input()
    t = input()

    L = lcm(n, m)
    X = [""] * L
    for i in range(n):
        idx = i * L // n
        X[idx] = s[i]

    for i in range(m):
        idx = i * L // m
        if X[idx] != "" and X[idx] != t[i]:
            print("-1")
            break
    else:
        print(L)


if __name__ == '__main__':
    resolve()


Fixed submission:
import sys
from collections import defaultdict

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a


def lcm(a, b):
    return a * b // gcd(a, b)


def resolve():
    n, m = map(int, input().split())
    s = input()
    t = input()

    L = lcm(n, m)

    X = dict()
    for i in range(n):
        idx = (L // n) * i
        X[idx] = s[i]

    for i in range(m):
        idx = (L // m) * i
        if X.get(idx) != None and X[idx] != t[i]:
            print("-1")
            break
    else:
        print(L)


if __name__ == '__main__':
    resolve()
Buggy python submission (verdict: Time Limit Exceeded):
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n, m = map(int, input().split())

    if m % n == 0:
        print(m // n)
    else:
        ma = m // n
        res = 0
        for g in range(1, ma + 1):
            t = m - g * (n - 1)
            if t % g == 0:
                GCD = g
                res = max(res, GCD)
        print(res)


if __name__ == '__main__':
    resolve()


Fixed submission:
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def make_divisors(n):
    divisors = []
    for i in range(1, int(pow(n, 0.5)) + 1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n // i)
    divisors.sort()
    return divisors


def resolve():
    n, m = map(int, input().split())

    ma = m // n
    div = make_divisors(m)
    res = 1
    for d in div:
        if d <= ma:
            res = d
        else:
            break

    print(res)


if __name__ == '__main__':
    resolve()
Buggy python submission (verdict: Time Limit Exceeded):
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n = int(input())
    X = list(map(int, input().split()))
    X_s = sorted(X)
    for i in range(n):
        idx = X_s.index(X[i])
        if idx <= n // 2 - 1:
            print(X_s[n // 2])
        else:
            print(X_s[n // 2 - 1])


if __name__ == '__main__':
    resolve()


Fixed submission:
n = int(input())
x = list(map(int, input().split()))
xs = sorted(x)
for i in range(n):
    if x[i] <= xs[n // 2 - 1]:
        res = xs[n // 2]
    else:
        res = xs[n // 2 - 1]
    print(res)

Buggy python submission (verdict: Time Limit Exceeded):
import copy

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

for i in range(n):
    memo = copy.deepcopy(x)
    memo.pop(i)
    memo.sort()
    print(memo[(n - 1) // 2])

Fixed submission:
n = int(input())
x = list(map(int, input().split()))
xs = sorted(x)
for i in range(n):
    if x[i] <= xs[n // 2 - 1]:
        res = xs[n // 2]
    else:
        res = xs[n // 2 - 1]
    print(res)
Buggy python submission (verdict: Time Limit Exceeded):
a, b, k = map(int, input().split())

for i in range(a, b + 1):
    if a <= i <= a + k - 1 or b - k + 1 <= i <= b:
        print(i)

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

res = []
for i in range(a, min(b + 1, a + k)):
    res.append(i)


for i in range(max(a, b - k + 1), b + 1):
    if i not in res:
        res.append(i)

res = sorted(res)
for i in res:
    print(i)
Buggy python submission (verdict: Runtime Error):
s = input()
L = ["a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z"]
res = ""
if len(s) < 26:
    for i in range(26):
        if L[i] in s:
            continue
        else:
            res += s + L[i]
            break
else:
    for i in range(1, 26):
        if s[i - 1] > s[i]:
            if L[L.index(s[i]) + 1] != s[i - 1]:
                continue
            else:
                res = s[: i - 1]
                res += L[res.index(res[-1]) + 1]
                break
    else:
        res ="-1"

print(res)

Fixed submission:
def main():
    s = input()
    alphabet = "".join([chr(i) for i in range(97, 97 + 26)])
    if len(s) < 26:
        for i in alphabet:
            if i not in s:
                print(s + i)
                exit()
    else:
        if s == "zyxwvutsrqponmlkjihgfedcba":
            print(-1)
        else:
            for i in reversed(range(26)):
                for j in reversed(range(i + 1, 26)):
                    if s[i] < s[j]:
                        print(s[:i] + s[j])
                        exit()


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    x, y = map(int, input().split())

    if x == y:
        print(-1)
        exit()

    for res in range(x, 10 ** 18, x):
        if res % y:
            print(res)
            break


if __name__ == '__main__':
    resolve()


Fixed submission:
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    x, y = map(int, input().split())

    if x % y == 0:
        print(-1)
        exit()

    for res in range(x, 10 ** 18, x):
        if res % y:
            print(res)
            break


if __name__ == '__main__':
    resolve()
Buggy python submission (verdict: Runtime Error):
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    k = int(input())
    A = list(map(int, input().split()))[::-1]

    if A[0] != 2:
        print(-1)
    else:
        prev_min, prev_max = 2, 3
        for i in range(1, k):
            a = A[i]
            if a > prev_max:
                print(-1)
                break
            else:
                if prev_min % a == 0:
                    now_min = prev_min
                else:
                    now_min = (prev_min // a) * a + a
                now_max = now_min + a - 1
                prev_min, prev_max = now_min, now_max
        else:
            print(now_min, now_max)


if __name__ == '__main__':
    resolve()


Fixed submission:
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    k = int(input())
    A = list(map(int, input().split()))[::-1]

    if A[0] != 2:
        print(-1)
    else:
        prev_min, prev_max = 2, 3
        for i in range(1, k):
            a = A[i]
            if a > prev_max:
                print(-1)
                break
            else:
                if prev_min % a == 0:
                    now_min = prev_min
                else:
                    now_min = (prev_min // a + 1) * a
                if now_min > prev_max:
                    print(-1)
                    break
                diff = prev_max - now_min
                now_max = now_min + (diff // a + 1) * a - 1
                prev_min, prev_max = now_min, now_max
        else:
            print(prev_min, prev_max)


if __name__ == '__main__':
    resolve()
Buggy python submission (verdict: Runtime Error):
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7
MAX = 8010


def resolve():
    S = input()
    X, Y = map(int, input().split())

    x = 0
    y = 0
    flg = 1
    for s in S:
        if s == "F":
            if flg:
                x += 1
            else:
                y += 1
        else:
            flg ^= 1

    dp_x = [0] * MAX
    dp_x[MAX // 2] = 1
    for i in range(x):
        j = 0
        while j < MAX:
            if dp_x[j] == 1:
                dp_x[j] = 0
                dp_x[j - 1] = 1
                dp_x[j + 1] = 1
                j += 2
            else:
                j += 1

    dp_y = [0] * MAX
    dp_y[MAX // 2] = 1
    for i in range(y):
        j = 0
        while j < MAX:
            if dp_y[j] == 1:
                dp_y[j] = 0
                dp_y[j - 1] = 1
                dp_y[j + 1] = 1
                j += 2
            else:
                j += 1

    print("Yes" if dp_x[MAX // 2 + X] and dp_y[MAX // 2 + Y] else "No")


if __name__ == '__main__':
    resolve()


Fixed submission:
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    s = input()
    gx, gy = map(int, input().split())

    spl = list(map(len, s.split("T")))
    init_x = spl[0]
    is_x = 0
    to_x, to_y = [], []
    for i in range(1, len(spl)):
        to_x.append(spl[i]) if is_x else to_y.append(spl[i])
        is_x ^= 1

    now_x = [init_x]
    for move in to_x:
        nx = set()
        for x in now_x:
            nx.add(x + move)
            nx.add(x - move)
        now_x = nx

    now_y = [0]
    for move in to_y:
        ny = set()
        for y in now_y:
            ny.add(y + move)
            ny.add(y - move)
        now_y = ny

    print("Yes" if gx in now_x and gy in now_y else "No")


if __name__ == '__main__':
    resolve()
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
numbers = [int(x) for x in input().split()]
count = 0
while True:
  for i in range(n):
    if numbers[i] % 2 == 0:
      numbers[i] /= 2
    else:
      print(count)
      break
  count += 1

Fixed submission:
n = int(input())
a = list(map(int, input().split()))
ans = 0
while True:
    for i in range(n):
        if a[i] % 2 == 0:
            a[i] = a[i] // 2
        else:
            print(ans)
            exit()
    ans += 1

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
numbers = [int(i) for i in input().split()]
count = 0
while True:
  for i in range(n):
    if numbers[i] % 2 != 0:
      print(count)
      break
    else:
      numbers[i] = int(numbers[i]) / 2
  count += 1

Fixed submission:
n = int(input())
a = list(map(int, input().split()))
ans = 0
while True:
    for i in range(n):
        if a[i] % 2 == 0:
            a[i] = a[i] // 2
        else:
            print(ans)
            exit()
    ans += 1

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
numbers = [int(i) for i in input().split()]
for i in range(0,n):
    count = 0
    while True:
        for i in range(n):
            if numbers[i] % 2 != 0:
                break
            else:
                numbers[i] = int(numbers[i]) / 2
        count += 1
print(count)


Fixed submission:
n = int(input())
a = list(map(int, input().split()))
ans = 0
while True:
    for i in range(n):
        if a[i] % 2 == 0:
            a[i] = a[i] // 2
        else:
            print(ans)
            exit()
    ans += 1