Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    n = int(input())
    a = list(map(int, input().split()))
    if 0 in a:
        print(0)
    else:
        answer = 1
        for aa in a:
            answer *= aa
        print(answer if answer <= pow(10, 18) else -1)


if __name__ == '__main__':
    main()



Fixed submission:
def main():
    n = int(input())
    a = list(map(int, input().split()))
    max_val = pow(10, 18)
    if 0 in a:
        print(0)
    else:
        answer = 1
        for aa in a:
            answer *= aa
            if max_val < answer:
                print(-1)
                break
        else:
            print(answer)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    n = int(input())
    a = list(map(int, input().split()))
    answer = 1
    for aa in a:
        answer *= aa
    if answer > 10 ** 18:
        print(-1)
    else:
        print(answer)


if __name__ == '__main__':
    main()



Fixed submission:
def main():
    n = int(input())
    a = list(map(int, input().split()))
    max_val = pow(10, 18)
    if 0 in a:
        print(0)
    else:
        answer = 1
        for aa in a:
            answer *= aa
            if max_val < answer:
                print(-1)
                break
        else:
            print(answer)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    n = int(input())
    a = list(map(int, input().split()))
    answer = 1
    for aa in a:
        answer *= aa
    if answer > 10 ** 18:
        print(-1)
    else:
        print(answer)


if __name__ == '__main__':
    main()



Fixed submission:
def main():
    n = int(input())
    a = list(map(int, input().split()))
    max_val = pow(10, 18)
    if 0 in a:
        print(0)
    else:
        answer = 1
        for aa in a:
            answer *= aa
            if max_val < answer:
                print(-1)
                break
        else:
            print(answer)


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
def comb(n, k, mod=10 ** 9 + 7):
    denominator = 1
    numerator = 1
    for i in range(1, k + 1):
        denominator = denominator * i % mod
    for i in range(n - k + 1, n + 1):
        numerator = numerator * i % mod
    return numerator * pow(denominator, mod - 2, mod) % mod


def main():
    n, m, k = map(int, input().split())
    mod = 998244353
    ans = 0
    for i in range(k + 1, -1, -1):
        ans += m * pow(m - 1, n - 1 - i, mod) * comb(n - 1, i, mod)
        ans %= mod
    print(ans)


if __name__ == '__main__':
    main()



Fixed submission:
def comb(n, k, nk, mod):
    return (n * pow(k * nk, mod - 2, mod)) % mod


def main():
    n, m, k = map(int, input().split())
    mod = 998244353
    ans = 0
    base = pow(m - 1, n - 1 - k, mod)
    fact = [1 for _ in range(n + 1)]
    for i in range(1, n + 1):
        fact[i] = fact[i - 1] * i
        fact[i] %= mod
    for i in range(k, -1, -1):
        ans += base * comb(fact[n - 1], fact[i], fact[n - i - 1], mod)
        ans %= mod
        base *= m - 1
        base %= mod
    ans *= m
    ans %= mod
    print(ans)


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    s = input()
    answer = 0
    for i in range(len(s)):
        for j in range(i + 1, len(s)):
            now = int(s[i:j + 1])
            if now < 2019:
                continue
            elif now % 2019 == 0:
                answer += 1
    print(answer)


if __name__ == '__main__':
    main()



Fixed submission:
def main():
    s = input()
    mod = 2019
    mod_count = {i: 0 for i in range(mod)}
    now_num = 0
    base = 1
    for i in range(len(s) - 1, -1, -1):
        mod_count[now_num] += 1
        now_num += base * int(s[i])
        now_num %= mod
        base *= 10
        base %= mod
    ans = 0
    mod_count[now_num % mod] += 1
    for i in range(mod):
        ans += mod_count[i] * (mod_count[i] - 1) // 2
    print(ans)


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
#include<bits/stdc++.h>
using namespace std;

int main() {
    int N;
    cin >> N;
    vector<int> A(N), count(N);
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }
    for (int i = 0; i < N; i++) {
        count[A[i]]++;
    }
    long long answer = 0;
    for (int i = 0; i < N; i++) {
        answer += count[i] * (count[i] - 1) / 2;
    }
    for (int i = 0; i < N; i++) {
        cout << answer - count[A[i]] + 1 << endl;
    }
    return 0;
}

Fixed submission:
def main():
    n = int(input())
    a = list(map(int, input().split()))
    count = {}
    for aa in a:
        if aa in count:
            count[aa] += 1
        else:
            count[aa] = 1
    balls = list(count.items())
    all = 0
    for b in balls:
        all += b[1] * (b[1] - 1) // 2
    for aa in a:
        print(all - count[aa] + 1)


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    s = input()
    q = int(input())
    reverse_count = 0
    for _ in range(q):
        query = list(input().split())
        if query[0] == "1":
            reverse_count += 1
        else:
            if reverse_count % 2:
                if query[1] == "1":
                    s += query[2]
                else:
                    s = query[2] + s
            else:
                if query[1] == "1":
                    s = query[2] + s
                else:
                    s += query[2]
    print(s[::-1] if reverse_count % 2 else s)


if __name__ == '__main__':
    main()



Fixed submission:
def main():
    s = input()
    q = int(input())
    reverse_count = 0
    left = []
    right = []
    for _ in range(q):
        query = list(input().split())
        if query[0] == "1":
            reverse_count += 1
        else:
            if reverse_count % 2:
                if query[1] == "1":
                    right.append(query[2])
                else:
                    left.append(query[2])
            else:
                if query[1] == "1":
                    left.append(query[2])
                else:
                    right.append(query[2])
    print("".join(right[::-1]) + s[::-1] + "".join(left) if reverse_count % 2
          else "".join(left[::-1]) + s + "".join(right))


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    s = input()
    q = int(input())
    reverse_count = 0
    for _ in range(q):
        query = list(input().split())
        if query[0] == "1":
            reverse_count += 1
        else:
            if reverse_count % 2:
                if query[1] == "1":
                    s += query[2]
                else:
                    s = query[2] + s
            else:
                if query[1] == "1":
                    s = query[2] + s
                else:
                    s += query[2]
    print(s[::-1] if reverse_count % 2 else s)


if __name__ == '__main__':
    main()



Fixed submission:
def main():
    s = input()
    q = int(input())
    reverse_count = 0
    left = []
    right = []
    for _ in range(q):
        query = list(input().split())
        if query[0] == "1":
            reverse_count += 1
        else:
            if reverse_count % 2:
                if query[1] == "1":
                    right.append(query[2])
                else:
                    left.append(query[2])
            else:
                if query[1] == "1":
                    left.append(query[2])
                else:
                    right.append(query[2])
    print("".join(right[::-1]) + s[::-1] + "".join(left) if reverse_count % 2
          else "".join(left[::-1]) + s + "".join(right))


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
def make_list(length, repeat):
    result = [[] for _ in range(length)]
    for _ in range(repeat):
        a, b = map(lambda x: int(x) - 1, input().split())
        result[a].append(b)
        result[b].append(a)
    return result


def main():
    n, m, k = map(int, input().split())
    friend = make_list(n, m)
    block = make_list(n, k)
    group_id = 1
    group = [0 for _ in range(n)]

    def dfs(start, group_id):
        q = [start]
        if group[start] == 0:
            while q:
                now = q.pop()
                group[now] = group_id
                for nn in friend[now]:
                    if group[nn] == 0:
                        group[nn] = group_id
                        q.append(nn)
            group_id += 1
        return group_id

    for i in range(n):
        group_id = dfs(i, group_id)

    members = [[] for _ in range(group_id)]
    for i in range(n):
        members[group[i]].append(i)

    answer = [0 for _ in range(n)]
    for i in range(n):
        answer[i] = len(members[group[i]]) - len(friend[i]) - len(set(members[group[i]]) & set(block[i])) - 1
    print(" ".join(map(str, answer)))


if __name__ == '__main__':
    main()



Fixed submission:
def make_list(length, loop):
    result = [[] for _ in range(length)]
    for _ in range(loop):
        a, b = map(lambda x: int(x) - 1, input().split())
        result[a].append(b)
        result[b].append(a)
    return result


def main():
    # 敢えてDFSで解いてみる．
    n, m, k = map(int, input().split())
    friend = make_list(n, m)
    brock = make_list(n, k)
    answer = [0] * n
    group_index = [0] * n
    group_id = 1

    def dfs(index):
        q = [index]
        group_index[index] = group_id
        connection = 1
        while not q == []:
            now = q.pop()
            for f in friend[now]:
                if group_index[f] == 0:
                    connection += 1
                    group_index[f] = group_id
                    q.append(f)
        return connection

    id_and_elements = {}
    for i in range(n):
        if group_index[i] == 0:
            id_and_elements[group_id] = dfs(i)
            group_id += 1

    for i in range(n):
        answer[i] += id_and_elements[group_index[i]] - 1
        answer[i] -= len(friend[i])
        for b in brock[i]:
            if group_index[b] == group_index[i]:
                answer[i] -= 1
    print(" ".join(map(str, answer)))


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    N, K = map(int, input().split())
    answer = 1
    while True:
        if K ** answer <= N < K ** (answer + 1):
            break
        else:
            answer += 1
    print(answer + 1)


if __name__ == '__main__':
    main()



Fixed submission:
from math import log, ceil


def main():
    N, K = map(int, input().split())
    answer = log(N, K)
    if answer.is_integer():
        print(int(answer) + 1)
    else:
        print(ceil(answer))


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    N, K = map(int, input().split())
    answer = 1
    while True:
        if K ** answer <= N < K ** (answer + 1):
            break
        else:
            answer += 1
    print(answer + 1)


if __name__ == '__main__':
    main()



Fixed submission:
from math import log, ceil


def main():
    N, K = map(int, input().split())
    answer = log(N, K)
    if answer.is_integer():
        print(int(answer) + 1)
    else:
        print(ceil(answer))


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
def expectation(n):
    return (n + 1) / 2


def main():
    n, k = map(int, input().split())
    p = list(map(int, input().split()))
    answer = 0
    for i in range(n - k + 1):
        tmp = 0
        for j in range(k):
            tmp += expectation(p[i + j])
        answer = max(answer, tmp)
    print(answer)


if __name__ == '__main__':
    main()



Fixed submission:
def main():
    # 差分だけ微調整する解法
    N, K = map(int, input().split(" "))
    p = list(map(int, input().split(" ")))
    answer = sum(p[:K])
    tmp = sum(p[:K])
    for i in range(N - K):
        tmp = tmp + p[i+K] - p[i]
        answer = max(answer, tmp)
    print((answer + K) / 2)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    N, K = map(int, input().split(" "))
    p = list(map(int, input().split(" ")))
    exceptation = [0] * N
    answer = 0
    for i in range(N):
        exceptation[i] = (p[i] + 1) / 2
    for i in range(N - K + 1):
        answer = max(answer, sum(exceptation[i:i+K]))
    print(answer)


if __name__ == '__main__':
    main()

Fixed submission:
def main():
    # 差分だけ微調整する解法
    N, K = map(int, input().split(" "))
    p = list(map(int, input().split(" ")))
    answer = sum(p[:K])
    tmp = sum(p[:K])
    for i in range(N - K):
        tmp = tmp + p[i+K] - p[i]
        answer = max(answer, tmp)
    print((answer + K) / 2)


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    monster_health, spells = map(int, input().split())
    attack = []
    damage = []
    for _ in range(spells):
        a, b = map(int, input().split())
        attack.append(a)
        damage.append(b)
    dp = [[float("inf") for _ in range(monster_health + 1)] for _ in range(spells + 1)]
    dp[0][0] = 0
    for i in range(1, spells + 1):
        for j in range(monster_health + 1):
            ind = min(j + attack[i - 1], monster_health)
            dp[i][j] = min(dp[i][j], dp[i - 1][j])
            dp[i][ind] = min(dp[i][ind], dp[i][j] + damage[i - 1])
    print(dp[-1][-1])


if __name__ == '__main__':
    main()



Fixed submission:
def main():
    monster_health, spells = map(int, input().split())
    attack = []
    damage = []
    for _ in range(spells):
        a, b = map(int, input().split())
        attack.append(a)
        damage.append(b)
    dp = [[float("inf") for _ in range(monster_health + 1)] for _ in range(spells + 1)]
    dp[0][0] = 0
    for i in range(1, spells + 1):
        for j in range(monster_health + 1):
            ind = min(j + attack[i - 1], monster_health)
            dp[i][j] = min(dp[i][j], dp[i - 1][j])
            dp[i][ind] = min(dp[i][ind], dp[i][j] + damage[i - 1])
    print(dp[-1][-1])


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    a, b = input().split(" ")
    i = int(a * int(b))
    j = int(b * int(a))
    numbers = [k for k in range(1, (max(i, j) + 1))]
    i_index = numbers.index(i)
    j_index = numbers.index(j)
    if i_index > j_index:
        print(i)
    else:
        print(j)


if __name__ == '__main__':
    main()

Fixed submission:
def main():
    a, b = map(int, input().split(" "))
    if a < b:
        print(str(a) * b)
    else:
        print(str(b) * a)


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


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


def main():
    _ = int(input())
    a = list(map(int, input().split()))
    mod = 10 ** 9 + 7
    a_lcm = reduce(lcm, a)
    print(sum([(a_lcm // aa) % mod for aa in a]) % mod)


if __name__ == '__main__':
    main()


Fixed submission:
from math import gcd
from functools import reduce


def main():
    _ = int(input())
    a = list(map(int, input().split()))
    mod = 10 ** 9 + 7

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

    a_lcm = reduce(lcm, a)
    print(sum([a_lcm * pow(aa, mod - 2, mod) % mod for aa in a]) % mod)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
from math import gcd
from functools import reduce


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


def main():
    _ = int(input())
    a = list(map(int, input().split()))
    mod = 10 ** 9 + 7
    a_lcm = reduce(lcm, a)
    print(sum([(a_lcm // aa) % mod for aa in a]) % mod)


if __name__ == '__main__':
    main()


Fixed submission:
from math import gcd
from functools import reduce


def main():
    _ = int(input())
    a = list(map(int, input().split()))
    mod = 10 ** 9 + 7

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

    a_lcm = reduce(lcm, a)
    print(sum([a_lcm * pow(aa, mod - 2, mod) % mod for aa in a]) % mod)


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


def main():
    length, sum_num, subarray_sum = map(int, input().split())
    base_length = ceil(length / sum_num)
    base_array = [subarray_sum]
    base_array += [10 ** 9 if subarray_sum < 10 ** 9 else 1] * (base_length - 1)
    print(" ".join(map(str, (base_array * (length // base_length + 1))[:length])))


if __name__ == '__main__':
    main()



Fixed submission:
def main():
    length, sum_num, subarray_sum = map(int, input().split())
    answer = [subarray_sum] * sum_num
    if subarray_sum == 10 ** 9:
        answer += [1] * (length - sum_num)
    else:
        answer += [subarray_sum + 1] * (length - sum_num)
    print(" ".join(map(str, answer)))


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
def comb(n, k, mod=10 ** 9 + 7):
    denominator = 1
    numerator = 1
    for i in range(1, k + 1):
        denominator = denominator * i % mod
    for i in range(n - k + 1, n + 1):
        numerator = numerator * i % mod
    return numerator * pow(denominator, mod - 2, mod) % mod


def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort(reverse=True)
    mod = 10 ** 9 + 7
    if k == 1:
        print(0)
    else:
        ans = 0
        for _ in range(2):
            for i in range(n - k + 1):
                ans += comb(n - i - 1, k - 1) * a[i]
            a = a[::-1]
            a = list(map(lambda x: -x, a))
        ans %= mod
        print(ans)


if __name__ == '__main__':
    main()


Fixed submission:
def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort()
    mod = 10 ** 9 + 7
    fac = [1 for _ in range(n + 1)]
    inv = [1 for _ in range(n + 1)]
    for i in range(1, n + 1):
        fac[i] = fac[i - 1] * i
        fac[i] %= mod
        inv[i] = inv[i - 1] * pow(i, -1, mod)
        inv[i] %= mod

    def comb(a, b, mod):
        return (fac[a] * inv[b] * inv[a - b]) % mod

    ans = 0
    for i in range(k - 1, n):
        nck = comb(i, k - 1, mod)
        ans += nck * a[i]
        ans -= nck * a[n - i - 1]
        ans %= mod

    print(ans)


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


def main():
    number = int(input())
    isPrime = False
    while not isPrime:
        isPrime = (number in sieve) == True
        if not isPrime:
            number += 1
    print(number)


if __name__ == '__main__':
    main()


Fixed submission:
def main():
    X = int(input())
    i = 2
    while i ** 2 <= X:
        if X % i == 0:
            X += 1
            i = 2
        else:
            i += 1
    print(X)

if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
def main():
    n, k = map(int, input().split())
    r, s, p = map(int, input().split())
    t = list(input())
    score = {"r": p, "s": r, "p": s}
    answer = 0
    for i in range(n):
        if i < k:
            answer += score[t[i]]
            if t[i] == t[i + k]:
                t[i + k] = t[i + k] + "*"
        elif i + k < n:
            if "*" not in t[i]:
                answer += score[t[i][0]]
                if t[i] == t[i + k]:
                    t[i + k] = t[i + k] + "*"
        else:
            if "*" not in t[i]:
                answer += score[t[i][0]]
    print(answer)


if __name__ == '__main__':
    main()



Fixed submission:
def main():
    N, K = map(int, input().split(" "))
    R, S, P = map(int, input().split(" "))
    strings = input()
    T = []
    for s in strings:
        T.append(s)
    score = {'r': P, 's': R, 'p': S}
    total = 0

    for i in range(K):
        total += score[T[i]]

    for j in range(K, N):
        if T[j] != T[j - K]:
            total += score[T[j]]
        else:
            T[j] = ' '
            continue

    print(total)

   
if __name__ == '__main__':
    main()

Buggy python submission (verdict: Runtime Error):
def main():
    n, k = map(int, input().split())
    r, s, p = map(int, input().split())
    t = list(input())
    score = {"r": p, "s": r, "p": s}
    answer = 0
    for i in range(n):
        if i < k:
            answer += score[t[i]]
            if t[i] == t[i + k]:
                t[i + k] = t[i + k] + "*"
        elif i + k < n:
            if "*" not in t[i]:
                answer += score[t[i]]
                if t[i] == t[i + k]:
                    t[i + k] = t[i + k] + "*"
        else:
            if "*" not in t[i]:
                answer += score[t[i]]
    print(answer)


if __name__ == '__main__':
    main()



Fixed submission:
def main():
    N, K = map(int, input().split(" "))
    R, S, P = map(int, input().split(" "))
    strings = input()
    T = []
    for s in strings:
        T.append(s)
    score = {'r': P, 's': R, 'p': S}
    total = 0

    for i in range(K):
        total += score[T[i]]

    for j in range(K, N):
        if T[j] != T[j - K]:
            total += score[T[j]]
        else:
            T[j] = ' '
            continue

    print(total)

   
if __name__ == '__main__':
    main()

Buggy python submission (verdict: Runtime Error):
def main():
    n = int(input())
    if n % 2:
        print(0)
    else:
        n //= 2
        i = 5
        answer = 0
        while i <= n:
            answer += n // i
            i *= 5
        print(answer)


if __name__ == '__main__':
    main()



Fixed submission:
def main():
    N, K = map(int, input().split(" "))
    R, S, P = map(int, input().split(" "))
    strings = input()
    T = []
    for s in strings:
        T.append(s)
    score = {'r': P, 's': R, 'p': S}
    total = 0

    for i in range(K):
        total += score[T[i]]

    for j in range(K, N):
        if T[j] != T[j - K]:
            total += score[T[j]]
        else:
            T[j] = ' '
            continue

    print(total)

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


def main():
    result = 0
    N = int(input())
    if N % 2 == 0:
        N //= 2
        while N > 0:
            result += floor(N / 5)
            N //= N / 5
        print(result)
    else:
        print(0)


if __name__ == '__main__':
    main()



Fixed submission:
def main():
    result = 0
    N = int(input())
    if N % 2 == 0:
        N //= 2
        while N > 0:
            N //= 5
            result += N
        print(result)
    else:
        print(0)


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    length = int(input())
    numbers = list(map(int, input().split()))
    numbers.sort()
    max_digit = len(bin(numbers[-1])[2:])
    count = [[0, 0] for _ in range(60)]
    for n in numbers:
        bin_n = bin(n)[2:].zfill(max_digit)
        for i in range(max_digit):
            count[max_digit - i - 1][int(bin_n[i])] += 1
    answer = 0
    mod = 10 ** 9 + 7
    for i, c in enumerate(count):
        answer = (answer + c[0] * c[1] * pow(2, i)) % mod
    print(answer)


if __name__ == '__main__':
    main()



Fixed submission:
import numpy as np


def main():
    length = int(input())
    numbers = np.array(list(map(int, input().split())))
    mod = 10 ** 9 + 7
    answer = 0
    for d in range(60):
        count_one = np.count_nonzero((numbers >> d) & 1)
        answer = (answer + pow(2, d) * count_one * (length - count_one)) % mod
    print(answer)


if __name__ == '__main__':
    main()