Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
from itertools import accumulate


def solve(n, k, ppp, ccc):
    NINF = -(10 ** 18)
    ans = NINF

    checked = [False] * n
    for s in range(n):
        if checked[s] == True:
            continue
        checked[s] = True
        scores = [ccc[ppp[s]]]
        starts = [s]
        v = ppp[s]
        while v != s:
            scores.append(ccc[ppp[v]])
            starts.append(v)
            checked[v] = True
            v = ppp[v]

        l = len(scores)
        d, m = divmod(k, l)
        loop = sum(scores)

        if d > 0:
            d -= 1
            m += l

        base = max(0, loop * d)

        for s in starts:
            v = ppp[s]
            score = base + ccc[ppp[s]]
            best_score = score
            for _ in range(m - 1):
                score += ccc[ppp[v]]
                v = ppp[v]
                best_score = max(best_score, score)
            ans = max(ans, best_score)

    return ans


n, k = map(int, input().split())
ppp = list(map(int, input().split()))
ppp = [p - 1 for p in ppp]
ccc = list(map(int, input().split()))

print(solve(n, k, ppp, ccc))


Fixed submission:
from itertools import accumulate


def solve(n, k, ppp, ccc):
    NINF = -(10 ** 18)
    ans = NINF

    checked = [False] * n
    for s in range(n):
        if checked[s] == True:
            continue
        checked[s] = True
        scores = [ccc[ppp[s]]]
        starts = [s]
        v = ppp[s]
        while v != s:
            scores.append(ccc[ppp[v]])
            starts.append(v)
            checked[v] = True
            v = ppp[v]

        l = len(scores)
        d, m = divmod(k, l)
        loop = sum(scores)

        if d > 0:
            d -= 1
            m += l

        base = max(0, loop * d)

        for s in starts:
            v = ppp[s]
            score = base + ccc[ppp[s]]
            best_score = score
            for _ in range(m - 1):
                score += ccc[ppp[v]]
                v = ppp[v]
                best_score = max(best_score, score)
            ans = max(ans, best_score)

    return ans


n, k = map(int, input().split())
ppp = list(map(int, input().split()))
ppp = [p - 1 for p in ppp]
ccc = list(map(int, input().split()))

print(solve(n, k, ppp, ccc))
Buggy python submission (verdict: Time Limit Exceeded):
import sys

r, c, k = map(int, sys.stdin.buffer.readline().split())
items = [[0] * (c + 1) for _ in range(r + 1)]
rcv = map(int, sys.stdin.buffer.read().split())
for r_, c_, v in zip(rcv, rcv, rcv):
    items[r_][c_] = v

dp = [[[0, 0, 0, 0] for _ in range(c + 1)] for _ in range(r + 1)]

for i in range(1, r + 1):
    for j in range(1, c + 1):
        up = dp[i - 1][j][3]
        for w in range(4):
            dp[i][j][w] = max(dp[i][j - 1][w], up)
        v = items[i][j]
        if v == 0:
            continue
        for w in range(2, -1, -1):
            dp[i][j][w + 1] = max(dp[i][j][w + 1], dp[i][j][w] + v)

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


Fixed submission:
import os
import sys

import numpy as np


def solve(inp):
    r, c, k = inp[:3]
    items = np.zeros((r + 1, c + 1), dtype=np.int64)
    rrr = inp[3::3]
    ccc = inp[4::3]
    vvv = inp[5::3]
    for r_, c_, v in zip(rrr, ccc, vvv):
        items[r_][c_] = v

    dp = np.zeros((r + 1, c + 1, 4), dtype=np.int64)

    for i in range(1, r + 1):
        for j in range(1, c + 1):
            up = dp[i - 1][j][3]
            for w in range(4):
                dp[i][j][w] = max(dp[i][j - 1][w], up)
            v = items[i][j]
            if v == 0:
                continue
            for w in range(2, -1, -1):
                dp[i][j][w + 1] = max(dp[i][j][w + 1], dp[i][j][w] + v)

    return dp[-1][-1][3]


if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC

    cc = CC('my_module')
    cc.export('solve', '(i8[:],)')(solve)
    cc.compile()
    exit()

if os.name == 'posix':
    # noinspection PyUnresolvedReferences
    from my_module import solve
else:
    from numba import njit

    solve = njit('(i8[:],)', cache=True)(solve)
    print('compiled', file=sys.stderr)

inp = np.fromstring(sys.stdin.read(), dtype=np.int64, sep=' ')
ans = solve(inp)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
from functools import lru_cache


@lru_cache(maxsize=None)
def f(x):
    if x == 0:
        return 0
    return f(x % bin(x).count('1')) + 1


n = int(input())
x = int(input(), base=2)
buf = []

for i in range(n):
    buf.append(f(x ^ (1 << i)))

buf.reverse()

print('\n'.join(map(str, buf)))


Fixed submission:
from functools import lru_cache


@lru_cache(maxsize=None)
def f(x):
    if x == 0:
        return 0
    return f(x % bin(x).count('1')) + 1


n = int(input())
x = input()
d = x.count('1')
y = int(x, base=2)
y0 = y % (d + 1)
y1 = y % (d - 1) if d > 1 else 0
buf = []

for i in range(n):
    if x[i] == '0':
        m = d + 1
        z = (y0 + pow(2, n - i - 1, m)) % m
        # print(0, y0, pow(2, n - i - 1, m))
    else:
        m = d - 1
        if m == 0:
            buf.append(0)
            continue
        z = (y1 - pow(2, n - i - 1, m)) % m
        # print(1, y1, pow(2, n - i - 1, m))
    # print(i, z)
    buf.append(f(z) + 1)

print('\n'.join(map(str, buf)))
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
ans = 0
for i in range(1, n + 1):
    for j in range(i, n + 1, i):
        ans += j
print(ans)


Fixed submission:
import os
import sys

import numpy as np


def solve(inp):
    n = inp[0]
    ans = n * (n + 1) // 2
    for i in range(2, n + 1):
        k = n // i
        ans += i * k * (k + 1) // 2
    return ans


if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC

    cc = CC('my_module')
    cc.export('solve', '(i8[:],)')(solve)
    cc.compile()
    exit()

if os.name == 'posix':
    # noinspection PyUnresolvedReferences
    from my_module import solve
else:
    from numba import njit

    solve = njit('(i8[:],)', cache=True)(solve)

inp = np.fromstring(sys.stdin.read(), dtype=np.int64, sep=' ')
ans = solve(inp)
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
arr = [1] * (n + 1)
for i in range(2, n + 1):
    for j in range(i, n + 1, i):
        arr[j] += 1
ans = 0
for i, c in enumerate(arr):
    ans += i * c
print(ans)


Fixed submission:
import os
import sys

import numpy as np


def solve(inp):
    n = inp[0]
    ans = n * (n + 1) // 2
    for i in range(2, n + 1):
        k = n // i
        ans += i * k * (k + 1) // 2
    return ans


if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC

    cc = CC('my_module')
    cc.export('solve', '(i8[:],)')(solve)
    cc.compile()
    exit()

if os.name == 'posix':
    # noinspection PyUnresolvedReferences
    from my_module import solve
else:
    from numba import njit

    solve = njit('(i8[:],)', cache=True)(solve)

inp = np.fromstring(sys.stdin.read(), dtype=np.int64, sep=' ')
ans = solve(inp)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
def prepare(n, MOD):
    f = 1
    factorials = [1]
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    inv = pow(f, MOD - 2, MOD)
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv
    return factorials, invs


k = int(input())
s = input()
l = len(s)
MOD = 10 ** 9 + 7

facts, finvs = prepare(k + l, MOD)

ans = 0
for i in range(k + 1):
    r = k - i
    pat = facts[l + r - 1] * finvs[l - 1] * finvs[r] % MOD
    ans = (ans + pat * pow(25, r, MOD) * pow(26, i, MOD)) % MOD
print(ans)


Fixed submission:
def prepare(n, MOD):
    f = 1
    factorials = [1]
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    inv = pow(f, MOD - 2, MOD)
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv
    return factorials, invs


k = int(input())
s = input()
l = len(s)
MOD = 10 ** 9 + 7

facts, finvs = prepare(k + l, MOD)

ans = 0
for i in range(k + 1):
    r = k - i
    pat = facts[l + r - 1] * finvs[l - 1] * finvs[r] % MOD
    ans = (ans + pat * pow(25, r, MOD) * pow(26, i, MOD)) % MOD
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
a, b, c, d = map(int, input().split())
MOD = 998244353

dp = [[0] * (d + 1) for _ in range(c + 1)]
dp[a][b] = 1

for i in range(a + 1, c + 1):
    dp[i][b] = dp[i - 1][b] * b % MOD

for j in range(b + 1, d + 1):
    dp[a][j] = dp[a][j - 1] * a % MOD

for i in range(a + 1, c + 1):
    for j in range(b + 1, d + 1):
        dp[i][j] = (dp[i][j - 1] * i + dp[i - 1][j] * j - dp[i - 1][j - 1] * (i - 1) * (j - 1)) % MOD

print(dp[c][d])


Fixed submission:
a, b, c, d = map(int, input().split())
MOD = 998244353

dp = [[0] * (d + 1) for _ in range(c + 1)]
dp[a][b] = 1

for i in range(a + 1, c + 1):
    dp[i][b] = dp[i - 1][b] * b % MOD

for j in range(b + 1, d + 1):
    dp[a][j] = dp[a][j - 1] * a % MOD

for i in range(a + 1, c + 1):
    for j in range(b + 1, d + 1):
        dp[i][j] = (dp[i][j - 1] * i + dp[i - 1][j] * j - dp[i - 1][j - 1] * (i - 1) * (j - 1)) % MOD

print(dp[c][d])
Buggy python submission (verdict: Time Limit Exceeded):
import sys
from itertools import accumulate

n, k, *aaa = map(int, sys.stdin.buffer.read().split())

for _ in range(k):
    bbb = [0] * (n + 1)
    for i in range(n):
        a = aaa[i]
        bbb[max(0, i - a)] += 1
        bbb[min(n, i + a + 1)] -= 1

    aaa = list(accumulate(bbb))
    aaa.pop()

    if all(a == n for a in aaa):
        break

print(*aaa)


Fixed submission:
import sys
from itertools import accumulate

n, k, *aaa = map(int, sys.stdin.buffer.read().split())

for _ in range(k):
    bbb = [0] * (n + 1)
    for i in range(n):
        a = aaa[i]
        bbb[max(0, i - a)] += 1
        bbb[min(n, i + a + 1)] -= 1

    aaa = list(accumulate(bbb))
    aaa.pop()

    if all(a == n for a in aaa):
        break

print(*aaa)
Buggy python submission (verdict: Time Limit Exceeded):
def check(s, m, parity):
    lo = parity
    hi = m - (m - parity) % 2

    for c in s:
        if c == '0':
            lo += 1
            hi += 1
        elif c == '1':
            lo -= 1
            hi -= 1
        else:
            lo -= 1
            hi += 1

        if lo < 0:
            lo += 2
        if hi > m:
            hi -= 2

        if lo > hi:
            return False

    return True


s = input()
l, r = 0, len(s)
while l + 1 < r:
    m = (l + r) // 2
    if check(s, m, 0) or check(s, m, 1):
        r = m
    else:
        l = m
print(r)


Fixed submission:
def check(s, m, parity):
    lo = parity
    hi = m - (m - parity) % 2

    for c in s:
        if c == '0':
            lo += 1
            hi += 1
        elif c == '1':
            lo -= 1
            hi -= 1
        else:
            lo -= 1
            hi += 1

        if lo < 0:
            lo += 2
        if hi > m:
            hi -= 2

        if lo > hi:
            return False

    return True


s = input()
l, r = 0, len(s)
while l + 1 < r:
    m = (l + r) // 2
    if check(s, m, 0) or check(s, m, 1):
        r = m
    else:
        l = m
print(r)
Buggy python submission (verdict: Time Limit Exceeded):
# salsa=0, rumba=1
# [0 1 0 1] 1より上の位に帯する操作

# 繰り上がりを考慮しつつ、3（より上）の位に対する操作を考える
# [1]       1の位が0である数字の、3の位に対する操作
# [0 1 0]   1の位が1である数字の、3の位に対する操作
# []        1の位が2である数字の、3の位に対する操作
# ある数字が"2"の時にルンバが来れば繰り上がる（上の位にルンバが波及）
# それ以外の状態では、上の位にとってルンバは無いのと同じことになる
# サルサは常に影響するが、連続した2つのサルサは打ち消し合い、無いのと同じことになる

# 再帰的に上の位を決める
# []        3,1の位が00,10である数字の、9の位に対する操作
# [1]       3,1の位が20である数字の、9の位に対する操作
# []        3,1の位が01,21である数字の、9の位に対する操作
# [0 1 0]   3,1の位が11である数字の、9の位に対する操作
# []        3,1の位が02,12,22である数字の、9の位に対する操作

# 一度繰り上がったら、例えば100.. と0がd個続くとして、
# 更にその上の位に波及させるには 2^d オーダーの操作が必要となるので、各操作列は徐々に減っていく

n = int(input())
t = input()
op = [[int(c == 'R') for c in t]]
ans = [0]

for d in range(n):
    k = 3 ** d
    nop = []
    nans = [0] * (k * 3)
    for g in range(3):  # d桁目の数
        for i in range(k):  # d桁目未満の数
            opg = op[i]
            opn = []
            h = g
            for o in opg:
                if o == 0:
                    if len(opn) > 0 and opn[-1] == 0:
                        opn.pop()
                    else:
                        opn.append(0)
                    if h == 1:
                        h = 2
                    elif h == 2:
                        h = 1
                else:
                    if h == 2:
                        h = 0
                        opn.append(1)
                    else:
                        h += 1
            nop.append(opn)
            nans[g * k + i] = h * k + ans[i]

    op = nop
    ans = nans

print(*ans)


Fixed submission:
# salsa=0, rumba=1
# [0 1 0 1] 1より上の位に帯する操作

# 繰り上がりを考慮しつつ、3（より上）の位に対する操作を考える
# [1]       1の位が0である数字の、3の位に対する操作
# [0 1 0]   1の位が1である数字の、3の位に対する操作
# []        1の位が2である数字の、3の位に対する操作
# ある数字が"2"の時にルンバが来れば繰り上がる（上の位にルンバが波及）
# それ以外の状態では、上の位にとってルンバは無いのと同じことになる
# サルサは常に影響するが、連続した2つのサルサは打ち消し合い、無いのと同じことになる

# 再帰的に上の位を決める
# []        3,1の位が00,10である数字の、9の位に対する操作
# [1]       3,1の位が20である数字の、9の位に対する操作
# []        3,1の位が01,21である数字の、9の位に対する操作
# [0 1 0]   3,1の位が11である数字の、9の位に対する操作
# []        3,1の位が02,12,22である数字の、9の位に対する操作

# 一度繰り上がったら、例えば100.. と0がd個続くとして、
# 更にその上の位に波及させるには 2^d オーダーの操作が必要となるので、各操作列は徐々に減っていく

n = int(input())
t = input()
op = [[int(c == 'R') for c in t]]
ans = [0]

for d in range(n):
    k = 3 ** d
    nop = []
    nans = [0] * (k * 3)
    for g in range(3):  # d桁目の数
        for i in range(k):  # d桁目未満の数
            opg = op[i]
            opn = []
            h = g
            for o in opg:
                if o == 0:
                    if len(opn) > 0 and opn[-1] == 0:
                        opn.pop()
                    else:
                        opn.append(0)
                    if h == 1:
                        h = 2
                    elif h == 2:
                        h = 1
                else:
                    if h == 2:
                        h = 0
                        opn.append(1)
                    else:
                        h += 1
            nop.append(opn)
            nans[g * k + i] = h * k + ans[i]

    op = nop
    ans = nans

print(*ans)
Buggy python submission (verdict: Runtime Error):
n, m = map(int, input().split())
if n % 2 == 1:
    for i in range(1, m + 1):
        print(i, n + 1 - i)
else:
    used = [False] * (n + 1)
    i = 1
    count = 0
    while count < m:
        while used[i]:
            i += 1
        print(i, i + count + 1)
        used[i] = True
        used[i + count + 1] = True
        count += 1


Fixed submission:
n, m = map(int, input().split())
if n % 2 == 1:
    for i in range(1, m + 1):
        print(i, n + 1 - i)
else:
    turning_point = (m + 1) // 2
    for i in range(1, turning_point + 1):
        print(i, n + 1 - i)
    for i in range(turning_point + 1, m + 1):
        print(i, n - i)
Buggy python submission (verdict: Runtime Error):
import sys
from bisect import bisect_left


def dfs(v, p, links, state, ans):
    # print(v, p, state, ans)
    ans[v] = len(state)
    for u in links[v]:
        if u == p:
            continue
        a = aaa[u]
        b = -1
        i = bisect_left(state, aaa[u])
        if i == len(state):
            state.append(a)
        else:
            b = state[i]
            state[i] = a
        dfs(u, v, links, state, ans)
        if b == -1:
            state.pop()
        else:
            state[i] = b


n = int(input())
aaa = list(map(int, input().split()))
links = [set() for _ in range(n)]
for line in sys.stdin:
    u, v = map(int, line.split())
    u -= 1
    v -= 1
    links[u].add(v)
    links[v].add(u)
ans = [0] * n
dfs(0, -1, links, [aaa[0]], ans)
print('\n'.join(map(str, ans)))


Fixed submission:
import sys
from bisect import bisect_left

sys.setrecursionlimit(10 ** 6)


def dfs(v, p, links, state, ans):
    ans[v] = len(state)
    for u in links[v]:
        if u == p:
            continue
        a = aaa[u]
        b, i = -1, -1
        if state[-1] < a:
            state.append(a)
        else:
            i = bisect_left(state, a)
            b = state[i]
            state[i] = a
        dfs(u, v, links, state, ans)
        if b == -1:
            state.pop()
        else:
            state[i] = b


n = int(input())
aaa = list(map(int, input().split()))
links = [set() for _ in range(n)]
for line in sys.stdin:
    u, v = map(int, line.split())
    u -= 1
    v -= 1
    links[u].add(v)
    links[v].add(u)
ans = [0] * n
dfs(0, -1, links, [aaa[0]], ans)
print('\n'.join(map(str, ans)))
Buggy python submission (verdict: Time Limit Exceeded):
def column_check(grp, grp_count, choco, h, j, k):
    """ 0:成功（更新も反映）  1:失敗（区切った結果を返す） 2:不可能 """
    # この行のグループ毎のカウント
    curr_count = [0] * len(grp_count)
    # 数える
    for i in range(h):
        if choco[i][j] == '0':
            continue
        curr_count[grp[i]] += 1
    # この行だけでk越えてたら現在の横の切り方では不可能
    for cc in curr_count:
        if cc > k:
            return 2
    # 左と合わせてkを越えないかチェック
    over = False
    for gc, cc in zip(grp_count, curr_count):
        if gc + cc > k:
            over = True
            break
    # 越えてたら、現在の行でgrp_countを更新
    if over:
        for i, cc in enumerate(curr_count):
            grp_count[i] = cc
        return 1
    # 越えてなかったら、加算
    for i, cc in enumerate(curr_count):
        grp_count[i] += cc
    return 0


def solve(h, w, k, choco):
    ans = 10 ** 9
    grp = [0] * h
    for bit in range(1 << (h - 1)):
        g = 0
        for i in range(h):
            grp[i] = g
            if (bit >> i) & 1:
                g += 1

        grp_count = [0] * (g + 1)
        tmp = 0
        possible = True
        for j in range(w):
            result = column_check(grp, grp_count, choco, h, j, k)
            if result == 2:
                possible = False
                break
            if result == 1:
                tmp += 1

        if not possible:
            continue

        ans = min(ans, tmp + bin(bit).count('1'))

    return ans


h, w, k = map(int, input().split())
choco = [input() for _ in range(h)]
print(solve(h, w, k, choco))


Fixed submission:
from itertools import accumulate


def solve(h, w, lim, choco):
    acc = [[0] + list(accumulate(int(c == '1') for c in s)) for s in choco]
    acc = list(zip(*acc))
    acc = [[0] + list(accumulate(s)) for s in acc]
    acc = list(zip(*acc))
    # print(*acc, sep='\n')

    ans = 10 ** 9
    # i:j  h方向の分割
    # k:l  w方向の分割
    for bit in range(1 << (h - 1)):
        k = 1
        tmp = 0
        while k < w:
            # print(bin(bit), k)
            i = 0
            l = w + 1
            sp = bit | 1 << (h - 1)
            while sp:
                b = sp & -sp
                sp ^= b
                j = b.bit_length()
                lt = k
                while lt <= w and acc[j][lt] - acc[j][k - 1] - acc[i][lt] + acc[i][k - 1] <= lim:
                    lt += 1
                if lt == k:
                    break
                l = min(l, lt)
                # print('i,j,k,l', i, j, k, l, lt)
                i = j
            else:
                k = l
                if k <= w:
                    tmp += 1
                continue
            break
        else:
            # print(tmp, bin(bit).count('1'))
            ans = min(ans, tmp + bin(bit).count('1'))
    return ans


h, w, k = map(int, input().split())
choco = [input() for _ in range(h)]
print(solve(h, w, k, choco))
Buggy python submission (verdict: Runtime Error):
import numpy as np

n, s = map(int, input().split())
aaa = list(map(int, input().split()))

fwd_acc = np.zeros((n + 1, s + 1), dtype=np.int64)
fwd_acc[0][0] = 1

ans = 0
MOD = 998244353
for i, a in enumerate(aaa, start=1):
    fwd_acc[i] = fwd_acc[i - 1]
    fwd_acc[i][0] = i
    if a <= s:
        fwd_acc[i][a:] += fwd_acc[i][:-a]
    ans = (ans + fwd_acc[i - 1][s - a] * (n - i + 1)) % MOD
print(ans)


Fixed submission:
import numpy as np

n, s = map(int, input().split())
aaa = list(map(int, input().split()))

fwd_acc = np.zeros((n + 1, s + 1), dtype=np.int64)
fwd_acc[0][0] = 1

ans = 0
MOD = 998244353
for i, a in enumerate(aaa, start=1):
    fwd_acc[i] = fwd_acc[i - 1]
    fwd_acc[i][0] = i
    if a <= s:
        fwd_acc[i][a:] = fwd_acc[i][a:] + fwd_acc[i][:-a]
    fwd_acc[i] %= MOD
    ans = (ans + fwd_acc[i][s]) % MOD
    # print(fwd_acc)
    # print(ans)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n, MOD = map(int, input().split())

n3 = n * 3
dp = [[0] * int(i * 1.5 + 5) for i in range(n3 + 1)]
dp[0][0] = dp[1][1] = dp[2][2] = dp[2][-1] = 1

for i in range(3, n3 + 1):
    i12 = (i - 1) * (i - 2)
    dpi3, dpi2, dpi1, dpi = dp[i - 3:i + 1]
    for j in range(-(i // 2), i + 1):
        tmp = dpi3[j] * i12
        tmp += dpi2[j + 1] * (i - 1)
        tmp += dpi1[j - 1]
        dpi[j] = tmp % MOD

print(sum(dp[-1][:n3 + 1]) % MOD)


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

n3 = n * 3
dp = [[0] * int(i * 1.5 + 5) for i in range(n3 + 1)]
dp[0][0] = dp[1][1] = dp[2][2] = dp[2][-1] = 1

for i in range(3, n3 + 1):
    i12 = (i - 1) * (i - 2)
    dpi3, dpi2, dpi1, dpi = dp[i - 3:i + 1]
    for j in range(-(i // 2), i + 1):
        tmp = dpi3[j] * i12
        tmp += dpi2[j + 1] * (i - 1)
        tmp += dpi1[j - 1]
        dpi[j] = tmp % MOD

print(sum(dp[-1][:n3 + 1]) % MOD)

Buggy python submission (verdict: Time Limit Exceeded):
n, MOD = map(int, input().split())

n3 = n * 3
dp = [[0] * int(i * 1.5 + 5) for i in range(n3 + 1)]
dp[0][0] = 1
dp[1][1] = 1
dp[2][2] = 1
dp[2][-1] = 1

for i in range(3, n3 + 1):
    i12 = (i - 1) * (i - 2)
    i1 = i - 1
    for j in range(-(i // 2), i + 1):
        tmp = dp[i - 3][j] * i12
        tmp += dp[i - 2][j + 1] * i1
        tmp += dp[i - 1][j - 1]
        dp[i][j] = tmp % MOD

print(sum(dp[-1][:n3 + 1]) % MOD)


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

n3 = n * 3
dp = [[0] * int(i * 1.5 + 5) for i in range(n3 + 1)]
dp[0][0] = dp[1][1] = dp[2][2] = dp[2][-1] = 1

for i in range(3, n3 + 1):
    i12 = (i - 1) * (i - 2)
    dpi3, dpi2, dpi1, dpi = dp[i - 3:i + 1]
    for j in range(-(i // 2), i + 1):
        tmp = dpi3[j] * i12
        tmp += dpi2[j + 1] * (i - 1)
        tmp += dpi1[j - 1]
        dpi[j] = tmp % MOD

print(sum(dp[-1][:n3 + 1]) % MOD)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
from itertools import accumulate


def solve(n, x, m):
    eee = [d % m for d in ddd]
    acc = list(accumulate(eee))
    zero = [int(e == 0) for e in eee]
    zero_acc = list(accumulate(zero))
    loop, rem = divmod(n - 1, k)
    tot = x % m + acc[-1] * loop
    tot_zero = zero_acc[-1] * loop
    if rem > 0:
        tot += acc[rem - 1]
        tot_zero += zero_acc[rem - 1]
    dame = tot // m
    # print(n, x, m)
    # print(eee)
    # print(acc)
    # print(loop, rem)
    # print(tot, dame)
    return n - 1 - dame - tot_zero


k, q = map(int, input().split())
ddd = list(map(int, input().split()))
buf = []
for line in sys.stdin:
    n, x, m = map(int, line.split())
    buf.append(solve(n, x, m))
print('\n'.join(map(str, buf)))


Fixed submission:
import sys
from itertools import accumulate


def solve(n, x, m):
    eee = [d % m for d in ddd]
    acc = list(accumulate(eee))
    zero = [int(e == 0) for e in eee]
    zero_acc = list(accumulate(zero))
    loop, rem = divmod(n - 1, k)
    tot = x % m + acc[-1] * loop
    tot_zero = zero_acc[-1] * loop
    if rem > 0:
        tot += acc[rem - 1]
        tot_zero += zero_acc[rem - 1]
    dame = tot // m
    # print(n, x, m)
    # print(eee)
    # print(acc)
    # print(loop, rem)
    # print(tot, dame)
    return n - 1 - dame - tot_zero


k, q = map(int, input().split())
ddd = list(map(int, input().split()))
buf = []
for line in sys.stdin:
    n, x, m = map(int, line.split())
    buf.append(solve(n, x, m))
print('\n'.join(map(str, buf)))