Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    footing, next_range = map(int, input().split())
    height = list(map(int, input().split()))
    result = abs(height[-1] - height[0])
    if next_range < footing:
        answer = [float("inf")] * footing
        answer[0] = 0
        answer[1] = abs(height[1] - height[0])
        for i in range(footing):
            for j in range(1, next_range + 1):
                answer[i] = min(answer[i], answer[i - j] + abs(height[i] - height[i - j]))
        result = answer[-1]
    print(result)


if __name__ == '__main__':
    main()



Fixed submission:
def main():
    footing, next_range = map(int, input().split())
    height = list(map(int, input().split()))
    result = abs(height[-1] - height[0])
    if next_range < footing:
        answer = [float("inf")] * footing
        answer[0] = 0
        answer[1] = abs(height[1] - height[0])
        for i in range(footing):
            for j in range(1, next_range + 1):
                answer[i] = min(answer[i], answer[i - j] + abs(height[i] - height[i - j]))
        result = answer[-1]
    print(result)


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
def main():
    n, m = map(int, input().split())
    graph = [[] for _ in range(n)]
    for _ in range(m):
        x, y = map(lambda x: int(x) - 1, input().split())
        graph[x].append(y)
    dp = [-1 for _ in range(n)]
    # dp[i] := iから距離が最も長い頂点への距離

    def solve(v):
        if dp[v] != -1:
            return dp[v]
        res = 0
        for next_v in graph[v]:
            res = max(res, solve(next_v) + 1)
        dp[v] = res
        return dp[v]

    ans = 0
    for i in range(n):
        ans = max(ans, solve(i))
    print(ans)


if __name__ == '__main__':
    main()


Fixed submission:
from sys import setrecursionlimit
setrecursionlimit(10 ** 7)


def main():
    n, m = map(int, input().split())
    graph = [[] for _ in range(n)]
    for _ in range(m):
        x, y = map(lambda x: int(x) - 1, input().split())
        graph[x].append(y)
    dp = [-1 for _ in range(n)]
    # dp[i] := iから距離が最も長い頂点への距離

    def solve(v):
        if dp[v] != -1:
            return dp[v]
        res = 0
        for next_v in graph[v]:
            res = max(res, solve(next_v) + 1)
        dp[v] = res
        return dp[v]

    ans = 0
    for i in range(n):
        ans = max(ans, solve(i))
    print(ans)


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    n, p = map(int, input().split())
    f = {}
    tmp = 0
    while p % 2 == 0:
        tmp += 1
        p //= 2
    f[2] = tmp
    tmp = 3
    while p > 1:
        if p % tmp == 0:
            p //= tmp
            if tmp in f:
                f[tmp] += 1
            else:
                f[tmp] = 1
        else:
            tmp += 2
    f = sorted(f.items(), key=lambda x: x[1], reverse=True)
    answer = 1
    for ff, cnt in f:
        if cnt < n:
            break
        answer *= ff ** (cnt // n)
    print(answer)


if __name__ == '__main__':
    main()



Fixed submission:
from collections import Counter


def main():
    number, product = map(int, input().split())
    prime_factors = []
    while product % 2 == 0:
        prime_factors.append(2)
        product //= 2
    i = 3
    while i * i <= product:
        if product % i == 0:
            product //= i
            prime_factors.append(i)
        else:
            i += 2
    if product != 1:
        prime_factors.append(product)
    prime_factors = Counter(prime_factors)
    answer = 1
    for p, n in prime_factors.items():
        if number <= n:
            answer *= pow(p, n // number)
    print(answer)


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
def solve(n):
    k = 1
    while k * (k + 1) < 2 * n:
        k += 1
    if k * (k + 1) != 2 * n:
        return False, []
    ans = [[] for _ in range(1000)]
    add_num = 1
    ans[1].append(add_num)
    ans[0].append(add_num)
    for i in range(2, k + 1):
        for j in range(i):
            add_num += 1
            ans[i].append(add_num)
            ans[i - j - 1].append(add_num)
    return True, ans, k


def main():
    n = int(input())
    res, ans, k = solve(n)
    if res:
        print("Yes")
        print(k + 1)
        for a in ans:
            if a:
                print(len(a), " ".join(map(str, a)))
            else:
                break
    else:
        print("No")


if __name__ == '__main__':
    main()


Fixed submission:
def solve(n):
    k = 1
    while k * (k + 1) < 2 * n:
        k += 1
    if k * (k + 1) != 2 * n:
        return False, [], -1
    ans = [[] for _ in range(1000)]
    add_num = 1
    ans[1].append(add_num)
    ans[0].append(add_num)
    for i in range(2, k + 1):
        for j in range(i):
            add_num += 1
            ans[i].append(add_num)
            ans[i - j - 1].append(add_num)
    return True, ans, k


def main():
    n = int(input())
    res, ans, k = solve(n)
    if res:
        print("Yes")
        print(k + 1)
        for a in ans:
            if a:
                print(len(a), " ".join(map(str, a)))
            else:
                break
    else:
        print("No")


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


def main():
    s_length, t_length = map(int, input().split())
    s = input()
    t = input()
    lcm = s_length * t_length // gcd(s_length, t_length)
    check = ["" for _ in range(lcm)]
    base = lcm // s_length
    for i in range(s_length):
        check[base * i] = s[i]
    base = lcm // t_length
    for i in range(t_length):
        if (0 < i and (check[base * i] != "" and check[base * i] != t[i])) or (i == 0 and t[0] != check[0]):
            print(-1)
            break
    else:
        print(lcm)


if __name__ == '__main__':
    main()




Fixed submission:
from fractions import gcd


def main():
    s_length, t_length = map(int, input().split())
    s = input()
    t = input()
    lcm = s_length * t_length // gcd(s_length, t_length)
    answer = True
    for i in range(s_length):
        if (i * t_length) % s_length == 0 and s[i] != t[(i * t_length) // s_length]:
            answer = False
            break
    print(lcm if answer else -1)


if __name__ == '__main__':
    main()

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


def main():
    s_length, t_length = map(int, input().split())
    s = input()
    t = input()
    lcm = s_length * t_length // gcd(s_length, t_length)
    check = ["" for _ in range(lcm)]
    base = lcm // s_length
    for i in range(s_length):
        check[base * i] = s[i]
    base = lcm // t_length
    for i in range(t_length):
        if (0 < i and (check[base * i] != "" and check[base * i] != t[i])) or (i == 0 and t[0] != check[0]):
            print(-1)
            break
    else:
        print(lcm)


if __name__ == '__main__':
    main()




Fixed submission:
from fractions import gcd


def main():
    s_length, t_length = map(int, input().split())
    s = input()
    t = input()
    lcm = s_length * t_length // gcd(s_length, t_length)
    answer = True
    for i in range(s_length):
        if (i * t_length) % s_length == 0 and s[i] != t[(i * t_length) // s_length]:
            answer = False
            break
    print(lcm if answer else -1)


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
# 解説AC．


def main():
    N, M = map(int, input().split(" "))
    result = 1
    for i in range(2, M // N + 1):
        if M % i == 0:
            result = i
    print(result)


if __name__ == '__main__':
    main()

Fixed submission:
def main():
    N, M = map(int, input().split(" "))
    for i in range(M // N, 0, -1):
        if M % i == 0 and i <= M / N:
            print(i)
            break


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    n, m, q = map(int, input().split())
    trains = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
    for _ in range(m):
        l, r = map(int, input().split())
        trains[l][r] += 1
    for i in range(n + 1):
        for j in range(1, n + 1):
            trains[i][j] += trains[i][j - 1]
    for _ in range(q):
        p, q = map(int, input().split())
        ans = 0
        for i in range(p, q + 1):
            ans += trains[i][q] - trains[i][p - 1]
        print(ans)


if __name__ == '__main__':
    main()


Fixed submission:
def main():
    n, m, q = map(int, input().split())
    trains = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
    for _ in range(m):
        l, r = map(int, input().split())
        trains[l][r] += 1
    for i in range(n + 1):
        for j in range(1, n + 1):
            trains[i][j] += trains[i][j - 1]
    for _ in range(q):
        p, q = map(int, input().split())
        ans = 0
        for i in range(p, q + 1):
            ans += trains[i][q] - trains[i][p - 1]
        print(ans)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    n, m, q = map(int, input().split())
    trains = [list(map(int, input().split())) for _ in range(m)]
    for _ in range(q):
        p, q = map(int, input().split())
        print(len(list(filter(lambda x: p <= x[0] and x[1] <= q, trains))))


if __name__ == '__main__':
    main()


Fixed submission:
def main():
    n, m, q = map(int, input().split())
    trains = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
    for _ in range(m):
        l, r = map(int, input().split())
        trains[l][r] += 1
    for i in range(n + 1):
        for j in range(1, n + 1):
            trains[i][j] += trains[i][j - 1]
    for _ in range(q):
        p, q = map(int, input().split())
        ans = 0
        for i in range(p, q + 1):
            ans += trains[i][q] - trains[i][p - 1]
        print(ans)


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
from string import ascii_lowercase


def main():
    all_s = input()
    k = int(input())
    ind = {a: [] for a in ascii_lowercase}
    if len(all_s) == 1:
        print(all_s)
    else:
        for i in range(len(all_s)):
            ind[all_s[i]].append(i)
        for s, index in ind.items():
            if not index:
                continue
            else:
                substr = {s}
                i = 1
                all_substr = len(all_s) * len(index) - sum(index) - 1
                if all_substr < k:
                    k -= all_substr
                    continue
                before_len = 0
                while len(substr) != before_len:
                    before_len = len(substr)
                    for j in index:
                        substr.add(all_s[j:i + j + 1])
                    i += 1
                substr = list(substr)
                substr.sort()
                print(substr[k - 1])
                break


if __name__ == '__main__':
    main()



Fixed submission:
def main():
    all_s = input()
    k = int(input())
    substr = set()
    for i in range(len(all_s)):
        for j in range(1, k + 1):
            substr.add(all_s[i:i + j])
    substr = list(substr)
    substr.sort()
    print(substr[k - 1])


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    s = input()
    k = int(input())
    n = len(s)
    substr = set()
    for i in range(n):
        for j in range(n - i):
            substr.add(s[j: j + i + 1])
    substr = list(substr)
    substr.sort()
    print(substr[k - 1])


if __name__ == '__main__':
    main()



Fixed submission:
def main():
    all_s = input()
    k = int(input())
    substr = set()
    for i in range(len(all_s)):
        for j in range(1, k + 1):
            substr.add(all_s[i:i + j])
    substr = list(substr)
    substr.sort()
    print(substr[k - 1])


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
from math import gcd
from functools import reduce


def main():
    n = int(input())
    numbers_gcd = reduce(gcd, list(map(int, input().split())))
    answer = 0
    while numbers_gcd > 0:
        if numbers_gcd % 2:
            break
        else:
            numbers_gcd //= 2
            answer += 1
    print(answer)


if __name__ == '__main__':
    main()

Fixed submission:
from fractions import gcd
from functools import reduce


def main():
    n = int(input())
    numbers_gcd = reduce(gcd, list(map(int, input().split())))
    answer = 0
    while numbers_gcd > 0:
        if numbers_gcd % 2:
            break
        else:
            numbers_gcd //= 2
            answer += 1
    print(answer)


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


def main():
    towns, roads, visit = map(int, input().split())
    visit_order = [int(x) - 1 for x in input().split()]
    dist = [[float("inf") for _ in range(towns)] for _ in range(towns)]
    for _ in range(roads):
        a, b, d = map(int, input().split())
        a -= 1
        b -= 1
        dist[a][b] = d
        dist[b][a] = d
    for k in range(towns):
        for i in range(towns):
            for j in range(towns):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    answer = float("inf")
    for p in permutations(visit_order):
        now = 0
        for i in range(visit - 1):
            now += dist[p[i]][p[i + 1]]
        answer = min(answer, now)
    print(answer)


if __name__ == '__main__':
    main()



Fixed submission:
from itertools import permutations


def main():
    towns, roads, visit = map(int, input().split())
    visit_order = [int(x) - 1 for x in input().split()]
    dist = [[float("inf") for _ in range(towns)] for _ in range(towns)]
    for _ in range(roads):
        a, b, d = map(int, input().split())
        a -= 1
        b -= 1
        dist[a][b] = d
        dist[b][a] = d
    for k in range(towns):
        for i in range(towns):
            for j in range(towns):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    answer = float("inf")
    for p in permutations(visit_order):
        now = 0
        for i in range(visit - 1):
            now += dist[p[i]][p[i + 1]]
        answer = min(answer, now)
    print(answer)


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
def main():
    N = int(input())
    permutation = list(map(int, input().split()))
    answer = 0
    for i in range(N):
        if permutation[i] == i + 1:
            permutation[i], permutation[i + 1] = permutation[i + 1], permutation[i]
            answer += 1
    print(answer)


if __name__ == '__main__':
    main()

Fixed submission:
def main():
    N = int(input())
    permutation = list(map(int, input().split()))
    answer = 0
    for i in range(N):
        if permutation[i] == i + 1:
            if permutation[i] == N:
                permutation[i], permutation[i - 1] = permutation[i - 1], permutation[i]
            else:
                permutation[i], permutation[i + 1] = permutation[i + 1], permutation[i]
            answer += 1
    print(answer)


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
def n_pow(a, n):
    if n <= 0:
        return 0
    return pow(a, n)


def main():
    bags, remainder = map(int, input().split())
    biscuits = list(map(int, input().split()))
    count = [0, 0]
    for b in biscuits:
        count[b % 2] += 1
    if remainder == 0:
        print(n_pow(2, count[0]) + n_pow(2, count[1] - 1))
    else:
        print(n_pow(2, count[0] + count[1] - 1, 0))


if __name__ == '__main__':
    main()



Fixed submission:
def n_pow(a, n):
    if n <= 0:
        return 0
    return pow(a, n)


def main():
    bags, remainder = map(int, input().split())
    biscuits = list(map(int, input().split()))
    count = [0, 0]
    for b in biscuits:
        count[b % 2] += 1
    if remainder == 1 and count[1] == 0:
        print(0)
    elif count[1] == 0:
        print(pow(2, bags))
    else:
        print(n_pow(2, bags - 1))


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    length = int(input())
    numbers = list(map(int, input().split()))
    answer = []
    for num in numbers:
        answer.append(num)
        answer = list(reversed(answer))
    print(" ".join(map(str, answer)))


if __name__ == '__main__':
    main()



Fixed submission:
def main():
    length = int(input())
    numbers = list(map(int, input().split()))
    answer = [0] * length
    if length % 2:
        answer[:length // 2 + 1] = numbers[::-2]
        answer[length // 2 + 1:] = numbers[1::2]
    else:
        answer[:length // 2] = numbers[::-2]
        answer[length // 2:] = numbers[::2]
    print(" ".join(list(map(str, answer))))


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    buttons = int(input())
    next_lighten_up = [int(input()) for _ in range(buttons)]
    searched = [1]
    answer = 1
    while True:
        if next_lighten_up[searched[-1] - 1] == 2:
            break
        elif next_lighten_up[searched[-1] - 1] in searched:
            answer = -1
            break
        else:
            answer += 1
            searched.append(next_lighten_up[searched[-1] - 1])
    print(answer)


if __name__ == '__main__':
    main()



Fixed submission:
def main():
    buttons = int(input())
    next_lighten_up = [int(input()) for _ in range(buttons)]
    searched = [False] * (buttons + 1)
    answer = 1
    index = 1
    while True:
        if next_lighten_up[index - 1] == 2:
            break
        elif searched[next_lighten_up[index - 1]]:
            answer = -1
            break
        else:
            searched[next_lighten_up[index - 1]] = True
            answer += 1
            index = next_lighten_up[index - 1]
    print(answer)


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
def main():
    word = input()
    count = {}
    for w in word:
        if w in count:
            count[w] += 1
        else:
            count[w] = 1
    count = sorted(count.items(), key=lambda x: x[1])
    target_list = []
    if count[-1][1] == 1:
        target_list.append(word[len(word) // 2])
    else:
        for i in range(-1, -len(word) - 1, -1):
            if count[i][1] == count[-1][1]:
                target_list.append(count[i][0])
            else:
                break
    answer = float("inf")
    for target in target_list:
        now_ans = 0
        now_word = word
        while len(set(now_word)) > 1:
            tmp = ""
            for i in range(len(now_word) - 1):
                if now_word[i] == target or now_word[i + 1] == target:
                    tmp += target
                else:
                    tmp += now_word[i]
            now_word = tmp
            now_ans += 1
        answer = min(answer, now_ans)
    print(answer)


if __name__ == '__main__':
    main()



Fixed submission:
from string import ascii_lowercase


def main():
    word = input()
    target_list = list(ascii_lowercase)
    answer = float("inf")
    for target in target_list:
        now_ans = 0
        now_word = word
        while len(set(now_word)) > 1:
            tmp = ""
            for i in range(len(now_word) - 1):
                if now_word[i] == target or now_word[i + 1] == target:
                    tmp += target
                else:
                    tmp += now_word[i]
            now_word = tmp
            now_ans += 1
        answer = min(answer, now_ans)
    print(answer)


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
from functools import reduce
from math import gcd


def main():
    cookies = list(map(int, input().split()))
    answer = -1
    if cookies[0] % 2 or cookies[1] % 2 or cookies[2] % 2:
        answer = 0
    elif len(set(cookies)) > 1:
        answer = reduce(gcd, cookies) - 1
    print(answer)


if __name__ == '__main__':
    main()



Fixed submission:
def main():
    cookies = list(map(int, input().split()))
    answer = 0
    if cookies[0] == cookies[1] == cookies[2] and cookies[0] % 2 == 0:
        answer = -1
    elif all(cookies[i] % 2 == 0 for i in range(3)):
        half = [0, 0, 0]
        sum_cookies = sum(cookies)
        while all(cookies[i] % 2 == 0 for i in range(3)):
            for i in range(3):
                half[i] = (sum_cookies - cookies[i]) // 2
            cookies[0] = half[1] + half[2]
            cookies[1] = half[0] + half[2]
            cookies[2] = half[1] + half[0]
            answer += 1
    print(answer)


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
def main():
    people_num = int(input())
    information = sorted(list(map(int, input().split())))
    unique = len(set(information))
    answer = 0
    if information[1] > 0 and unique * 2 == people_num + people_num % 2:
        answer = (unique - people_num % 2) ** 2
    print(answer)


if __name__ == '__main__':
    main()



Fixed submission:
def main():
    people_num = int(input())
    information = sorted(list(map(int, input().split())))
    unique = len(set(information))
    answer = 0
    if unique * 2 == people_num + people_num % 2:
        if people_num > 1 and information[1] > 0:
            answer = 2 ** (unique - people_num % 2)
        elif people_num == 1 and information[0] == 0:
            answer = 1
    print(answer % (10 ** 9 + 7))


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
def main():
    target = input()
    string = ["eraser", "dreamer", "erase", "dream"]
    for i in range(len(target)):
        for s in string:
            if target[i - len(s):] == s:
                target = target[:i - len(s)]
                break
        print(target)
    print("YES" if target == "" else "NO")


if __name__ == '__main__':
    main()



Fixed submission:
def main():
    target = input()
    string = ["eraser", "dreamer", "erase", "dream"]
    for i in range(len(target)):
        for s in string:
            if target[-len(s):] == s:
                target = target[:-len(s)]
        if target == "":
            break
    print("YES" if target == "" else "NO")


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
def main():
    word = list(input())
    operation = int(input())
    cost = {}
    for i in range(26):
        cost[chr(ord("a") + i)] = ord("z") - ord("a") - i + 1
    for i in range(len(word)):
        if cost[word[i]] <= operation:
            operation -= cost[word[i]]
            word[i] = "a"
        else:
            continue
    if 0 < operation:
        for i in range(-1, -len(word)-1, -1):
            word[i] = chr(ord(word[i]) + operation)
            operation = 0
            break
    print("".join(word))


if __name__ == '__main__':
    main()



Fixed submission:
def main():
    word = list(input())
    operation = int(input())
    cost = {}
    for i in range(26):
        cost[chr(ord("a") + i)] = ord("z") - ord("a") - i + 1
    for i in range(len(word)):
        if cost[word[i]] <= operation and word[i] != "a":
            operation -= cost[word[i]]
            word[i] = "a"
        else:
            continue
    if 0 < operation:
        word[-1] = chr((ord(word[-1]) - ord("a") + operation % 26) % 26 + ord("a"))
    print("".join(word))


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
s=input()
if s[1]=='B':
  s[1]='R'
else:
  s[1]='B'
print(s)

Fixed submission:
s=input()

if s[1]=='B':
  print('ARC')
else:
  print('ABC')

Buggy python submission (verdict: Runtime Error):
s=input()
if s[1]=='B':
  s[1]='R'
else:
  s[1]='B';
print(s)

Fixed submission:
s=input()

if s[1]=='B':
  print('ARC')
else:
  print('ABC')
Buggy python submission (verdict: Runtime Error):
S=input()
if S[2]==S[3] && S[4]==S[5]:
  print('Yes')
else:
  print('No')

Fixed submission:
S=str(input())
if S[2]==S[3] and S[4]==S[5]:
  print('Yes')
else:
  print('No')