Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
H, W = map(int, input().split())
T = [[] for i in range(H)]
d = []
for i in range(H):
    T[i] = list(input())
    for j in range(W):
        if T[i][j] == '#':
            d.append((i, j))

num = 0
for p, q in d:
    que = [(p, q, 0)]
    R = {}
    R[(p, q, 0)] = 1
    while que:
        x, y, k = que.pop(0)
        if k == 0:
            for dx, dy in [(0, 1), (1, 0), (-1, 0), (0, -1)]:
                nx, ny = x + dx, y + dy
                if (nx, ny) in R:
                    continue
                if 0 <= nx < H and 0 <= ny < W and T[nx][ny] == '.':
                    R[(nx, ny)] = 1
                    que.append((nx, ny, 1))
                    num += 1

        else:
            for dx, dy in [(0, 1), (1, 0), (-1, 0), (0, -1)]:
                nx, ny = x + dx, y + dy
                if (nx, ny) in R:
                    continue
                if 0 <= nx < H and 0 <= ny < W and T[nx][ny] == '#':
                    R[(nx, ny)] = 1
                    que.append((nx, ny, 0))
                    i = 0

print(num)


Fixed submission:
H, W = map(int, input().split())
T = [[] for i in range(H)]
for i in range(H):
    a = list(input())
    T[i] = a

S = [[-1] * W for i in range(H)]

rec = 0
ans = [[0] * (H * W + 5) for i in range(2)]
for i in range(H):
    for j in range(W):
        if T[i][j] == "#" and S[i][j] == -1:
            rec += 1
            S[i][j] = rec
            ans[1][rec] += 1
            pre = "#"
            que = [(i, j, pre)]
            while que:
                x, y, pre = que.pop()
                for dx, dy in [(0, 1), (1, 0), (-1, 0), (0, -1)]:
                    nx, ny = x + dx, y + dy
                    if pre == "#":
                        if 0 <= nx < H and 0 <= ny < W and S[nx][ny] == -1 and T[nx][ny] == ".":
                            S[nx][ny] = rec
                            ans[0][rec] += 1
                            que.append((nx, ny, "."))
                    else:
                        if 0 <= nx < H and 0 <= ny < W and S[nx][ny] == -1 and T[nx][ny] == "#":
                            S[nx][ny] = rec
                            ans[1][rec] += 1
                            que.append((nx, ny, "#"))


num1 = 0
for i in range(H * W + 5):
    num1 += ans[0][i] * ans[1][i]

print(num1)
Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int, input().split())
h = list(map(int, input().split()))
INF = float('inf')
dp = [INF] * N
dp[0] = 0
for i in range(N):
    for j in range(i + 1, min(i + K + 1, N)):
        dp[j] = min(dp[j], dp[i] + abs(h[i] - h[j]))

print(dp[N - 1])

Fixed submission:
N, K = map(int, input().split())
h = list(map(int, input().split()))
INF = float('inf')
dp = [INF] * N
dp[0] = 0
for i in range(N):
    for j in range(i + 1, min(i + K + 1, N)):
        dp[j] = min(dp[j], dp[i] + abs(h[i] - h[j]))

print(dp[N - 1])
Buggy python submission (verdict: Time Limit Exceeded):
N, W = map(int, input().split())
d = []
for i in range(N):
    w, v = map(int, input().split())
    d.append((w, v))

dp = [[0] * (W + 1) for i in range(N + 1)]
for i in range(N):
    for w in range(W + 1):
        w1, v1 = d[i]
        dp[i + 1][w] = max(dp[i + 1][w], dp[i][w])
        if w + w1 <= W:
            dp[i + 1][w + w1] = max(dp[i + 1][w + w1], dp[i][w] + v1)

num = 0
for i in range(W + 1):
    num = max(num, dp[N][i])

print(num)

Fixed submission:
N, W = map(int, input().split())
d = []
for i in range(N):
    w, v = map(int, input().split())
    d.append((w, v))

d = sorted(d)
dp = [[0] * (W + 1) for i in range(N + 1)]
for i in range(N):
    for w in range(W + 1):
        w1, v1 = d[i]
        dp[i + 1][w] = max(dp[i + 1][w], dp[i][w])
        if w + w1 <= W:
            dp[i + 1][w + w1] = max(dp[i + 1][w + w1], dp[i][w] + v1)


num = 0
for i in range(W + 1):
    num = max(num, dp[N][i])

print(num)
Buggy python submission (verdict: Time Limit Exceeded):
N, W = map(int, input().split())
d = []
S = 0
for i in range(N):
    w, v = map(int, input().split())
    d.append((w, v))
    S += v
INF = float('inf')
dp = [[INF] * (S + 1) for i in range(N + 1)]
dp[0][0] = 0
for i in range(1, N + 1):
    for j in range(S + 1):
        w, v = d[i - 1]
        dp[i][j] = min(dp[i][j], dp[i - 1][j])
        if j + v <= S:
            dp[i][j + v] = min(dp[i][j + v], dp[i - 1][j] + w)

for i in range(S, -1, -1):
    if dp[N][i] <= W:
        print(i)
        exit()


Fixed submission:
N, W = map(int, input().split())
d = []
S = 0
for i in range(N):
    w, v = map(int, input().split())
    d.append((w, v))
    S += v
INF = float('inf')
dp = [[INF] * (S + 1) for i in range(N + 1)]
dp[0][0] = 0
for i in range(1, N + 1):
    for j in range(S + 1):
        w, v = d[i - 1]
        dp[i][j] = min(dp[i][j], dp[i - 1][j])
        if j + v <= S:
            dp[i][j + v] = min(dp[i][j + v], dp[i - 1][j] + w)

for i in range(S, -1, -1):
    if dp[N][i] <= W:
        print(i)
        exit()
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
P = list(map(float, input().split()))

dp = [0] * (N + 1)
dp[0] = 1
for i in range(1, N + 1):
    tmp = dp
    dp = [0] * (N + 1)
    for j in range(N):
        if j < N:
            dp[j + 1] += tmp[j] * P[i - 1]
        dp[j] += tmp[j] * (1 - P[i - 1])

num = 0
for i in range(N // 2 + 1, N + 1):
    num += dp[i]

print(num)


Fixed submission:
N = int(input())
P = list(map(float, input().split()))
dp = [[0] * (N + 1) for i in range(N + 1)]
dp[0][0] = 1.0
for i in range(1, N + 1):
    for j in range(N):
        if j < N:
            dp[i][j + 1] += dp[i - 1][j] * P[i - 1]
        dp[i][j] += dp[i - 1][j] * (1 - P[i - 1])

num = 0
for i in range(N + 1):
    if i > N // 2:
        num += dp[N][i]

print(num)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
P = list(map(float, input().split()))
dp = [[0] * (N + 1) for i in range(N + 1)]
dp[0][0] = 1.0
for i in range(1, N + 1):
    for j in range(N):
        if j < N:
            dp[i][j + 1] += dp[i - 1][j] * P[i - 1]
        dp[i][j] += dp[i - 1][j] * (1 - P[i - 1])

num = 0
for i in range(N + 1):
    if i > N // 2:
        num += dp[N][i]

print(num)


Fixed submission:
N = int(input())
P = list(map(float, input().split()))
dp = [[0] * (N + 1) for i in range(N + 1)]
dp[0][0] = 1.0
for i in range(1, N + 1):
    for j in range(N):
        if j < N:
            dp[i][j + 1] += dp[i - 1][j] * P[i - 1]
        dp[i][j] += dp[i - 1][j] * (1 - P[i - 1])

num = 0
for i in range(N + 1):
    if i > N // 2:
        num += dp[N][i]

print(num)
Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int, input().split())
a = list(map(int, input().split()))
dp = [False] * (K + 1)
for i in range(1, K + 1):
    for j in range(N):
        if i - a[j] >= 0:
            dp[i] |= not dp[i - a[j]]

if dp[K]:
    print('First')
else:
    print('Second')

Fixed submission:
N, K = map(int, input().split())
a = list(map(int, input().split()))
dp = [False] * (K + 1)
for i in range(1, K + 1):
    for j in range(N):
        if i - a[j] >= 0:
            dp[i] |= not dp[i - a[j]]

if dp[K]:
    print('First')
else:
    print('Second')
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
S = input()
Q = int(input())
K = list(map(int, input().split()))
for i in range(Q):
    k = K[i]
    D = 0
    M = 0
    DM = 0
    num = 0
    for j in range(N):
        if S[j] == 'D':
            D += 1
        elif S[j] == 'M':
            DM += D
            M += 1
        elif S[j] == 'C':
            num += DM
        if j >= k - 1:
            if S[j - k + 1] == 'D':
                D -= 1
                DM -= M
            elif S[j - k + 1] == 'M':
                M -= 1
    print(num)

Fixed submission:
import sys
N = int(sys.stdin.readline())
S = sys.stdin.readline()
Q = int(sys.stdin.readline())
K = list(map(int, sys.stdin.readline().split()))
for i in range(Q):
    k = K[i]
    D = 0
    M = 0
    DM = 0
    num = 0
    for j in range(N):
        if S[j] == 'D':
            D += 1
        elif S[j] == 'M':
            DM += D
            M += 1
        elif S[j] == 'C':
            num += DM
        if j >= k - 1:
            if S[j - k + 1] == 'D':
                D -= 1
                DM -= M
            elif S[j - k + 1] == 'M':
                M -= 1
    print(num)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
S = input()
Q = int(input())
K = list(map(int, input().split()))
for i in range(Q):
    k = K[i]
    D = 0
    M = 0
    DM = 0
    num = 0
    for j in range(N):
        if S[j] == 'D':
            D += 1
        elif S[j] == 'M':
            DM += D
            M += 1
        elif S[j] == 'C':
            num += DM
        if j >= k - 1:
            if S[j - k + 1] == 'D':
                D -= 1
                DM -= M
            elif S[j - k + 1] == 'M':
                M -= 1
    print(num)

Fixed submission:
import sys
N = int(sys.stdin.readline())
S = sys.stdin.readline()
Q = int(sys.stdin.readline())
K = list(map(int, sys.stdin.readline().split()))
for i in range(Q):
    k = K[i]
    D = 0
    M = 0
    DM = 0
    num = 0
    for j in range(N):
        if S[j] == 'D':
            D += 1
        elif S[j] == 'M':
            DM += D
            M += 1
        elif S[j] == 'C':
            num += DM
        if j >= k - 1:
            if S[j - k + 1] == 'D':
                D -= 1
                DM -= M
            elif S[j - k + 1] == 'M':
                M -= 1
    print(num)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = []
for i in range(N):
    A.append(int(input()))
A = sorted(A, reverse=True)
B = [A.pop(0)]
num = 0
for i in range(N - 1):
    if i % 2 == 0:
        k = A.pop(-1)
    else:
        k = A.pop(0)
    if abs(B[-1] - k) <= abs(B[0] - k):
        num += abs(B[0] - k)
        B = [k] + B
    else:
        num += abs(B[-1] - k)
        B += [k]


print(num)



Fixed submission:
from collections import deque
N = int(input())
A = []
for i in range(N):
    a = int(input())
    A.append(a)

A = sorted(A)
q = deque()
q.append(A[0])
i = 1
j = N - 1
mi = True
while i < N and j >= 0 and i <= j:
    if mi:
        p1, p2 = q[0], q[-1]
        q1, q2, q3, q4 = abs(A[j] - p1), abs(A[j] - p2), abs(A[i] - p1), abs(A[i] - p2)
        qm = max(q1, q2, q3, q4)
        if qm == q1:
            q.appendleft(A[j])
            j -= 1
        elif qm == q2:
            q.append(A[j])
            j -= 1
        elif qm == q3:
            q.appendleft(A[i])
            i += 1
        else:
            q.append(A[i])
            i += 1

num = 0
pre = q[0]
for i in range(1, N):
    num += abs(q[i] - pre)
    pre = q[i]

print(num)
Buggy python submission (verdict: Runtime Error):
h, w = map(int, input().split())
T = [[] for i in range(h)]
S = [[0] * w for i in range(h)]
for i in range(h):
    a = list(map(int, input().split()))
    T[i] = a

for i in range(h):
    for j in range(w):
        T[i][j] = T[i][j] % 2

rec = []
for i in range(h):
    for j in range(w):
        if T[i][j] == 1:
            rec.append((i, j))

rec = sorted(rec)
rec = sorted(rec, key=lambda s: s[1])
move = []
for i in range(0, len(rec), 2):
    if i + 1 == len(rec):
        break
    a, b = rec[i], rec[i + 1]
    sx = a[0]
    sy = a[1]
    tx = b[0]
    ty = b[1]
    while sx != tx and S[sx][sy] != 1:
        move.append((sx, sy, sx + 1, sy))
        S[sx][sy] = 1
        sx += 1
    if sy <= ty:
        while sy != ty and S[sx][sy] != 1:
            move.append((sx, sy, tx, sy + 1))
            S[sx][sy] = 1
            sy += 1
    else:
        while sy != ty and S[sx][sy] != 1:
            move.append((sx, sy, tx, sy - 1))
            S[sx][sy] = 1
            sy -= 1

print(len(move))
for i in range(len(move)):
    x, y, w, z = move[i][0] + 1, move[i][1] + 1, move[i][2] + 1, move[i][3] + 1
    print(x, y, w, z)


Fixed submission:
h, w = map(int, input().split())
T = [[] for i in range(h)]
S = [[0] * w for i in range(h)]
for i in range(h):
    a = list(map(int, input().split()))
    T[i] = a

for i in range(h):
    for j in range(w):
        T[i][j] = T[i][j] % 2

move = []
i = 0
j = 0
k = 0
flag = False
while True:
    px, py = i, j
    if T[i][j] == 1:
        flag = True
    if i % 2 == 0:
        j += 1
        if j == w:
            j -= 1
            i += 1
        if i == h:
            break
        if flag:
            move.append((px, py, i, j))
        if flag and T[i][j] == 1:
            T[i][j] = 0
            flag = False
        k += 1
    else:
        j -= 1
        if j == -1:
            j += 1
            i += 1
        if i == h:
            break
        if flag:
            move.append((px, py, i, j))
        if flag and T[i][j] == 1:
            T[i][j] = 0
            flag = False

print(len(move))
for i in range(len(move)):
    x, y, w, z = move[i][0] + 1, move[i][1] + 1, move[i][2] + 1, move[i][3] + 1
    print(x, y, w, z)
Buggy python submission (verdict: Runtime Error):
N, K = map(int, input().split())
X = list(map(int, input().split()))
zero = 0
for i in range(N):
    if X[i] >= 0:
        break
    zero += 1
p = len(X[zero:])
m = len(X[:zero])
pl = X[zero:]
mi = X[:zero]
mi = mi[::-1]
num = float("inf")
if m == 0:
    num = min(num, pl[K - 1])
elif p == 0:
    num = min(num, mi[K - 1])
else:
    for i in range(K + 1):
        j = K - i
        if 0 < j <= m and 0 < i:
            rec1 = pl[i - 1] * 2 + abs(mi[j - 1])
            rec2 = pl[i - 1] + 2 * abs(mi[j - 1])
            num = min(num, rec1)
            num = min(num, rec2)
        elif j == 0 and K - 1 < p:
            num = min(num, pl[K - 1])
        elif i == 0 and K - 1 < m:
            num = min(num, mi[K - 1])


print(num)





Fixed submission:
n, k = map(int, input().split())
x = list(map(int, input().split()))
pl, mi = 0, 0
recp, recm = [], []
for i in range(n):
    if x[i] >= 0:
        pl += 1
        recp.append(x[i])
    else:
        mi += 1
        recm.append(x[i])

num = float("inf")
recm = recm[:: -1]
for i in range(pl + 1):
    if i == 0:
        if k <= mi:
            num = min(num, abs(recm[k - 1]))
        else:
            continue
    else:
        if k - i == 0:
            num = min(num, recp[k - 1])
        elif 0 < k - i <= mi:
            num = min(num, recp[i - 1] + 2 * abs(recm[k - i - 1]))
            num = min(num, 2 * recp[i - 1] + abs(recm[k - i - 1]))

print(num)
Buggy python submission (verdict: Runtime Error):
S = input()
K = int(input())
i = 0
while i < len(S) and S[i] == "1":
    i += 1

if i != len(S) - 1:
    ans = S[i]

if K - 1 <= i:
    print(1)
else:
    print(S[i])

Fixed submission:
s = input()
k = int(input())
n = len(s)
index = float("inf")
num = 0
for i in range(n):
    if s[i] != "1":
        index = i + 1
        num = s[i]
        break

if k < index:
    print(1)
else:
    print(num)
Buggy python submission (verdict: Time Limit Exceeded):
n, m, q = map(int, input().split())
tr = []
for i in range(m):
    l, r = map(int, input().split())
    tr.append((l, r))

qu = []
for i in range(q):
    p, q = map(int, input().split())
    qu.append((p, q))
    print(len(list(filter(lambda s: p <= s[0] and s[1] <= q, tr))))

Fixed submission:
n, m, q = map(int, input().split())
T = [[0] * n for i in range(n)]
for i in range(m):
    l, r = map(int, input().split())
    T[l - 1][r - 1] += 1

for i in range(n):
    for j in range(1, n):
        T[i][j] += T[i][j - 1]

for j in range(n):
    for i in range(n - 2, -1, -1):
        T[i][j] += T[i + 1][j]

for i in range(q):
    p, q = map(int, input().split())
    print(T[p - 1][q - 1])
Buggy python submission (verdict: Time Limit Exceeded):
s = input()
n = len(s)
mod = 10 ** 9 + 7
dp = [[0] * 4 for i in range(n + 1)]
dp[0][0] = 1

for i in range(n):
    if s[i] == "A":
        dp[i + 1][1] = dp[i + 1][1] + dp[i][0]
        dp[i + 1][0] += dp[i][0]
        dp[i + 1][1] += dp[i][1]
        dp[i + 1][2] += dp[i][2]
        dp[i + 1][3] += dp[i][3]
    elif s[i] == "B":
        dp[i + 1][2] = dp[i + 1][2] + dp[i][1]
        dp[i + 1][0] += dp[i][0]
        dp[i + 1][1] += dp[i][1]
        dp[i + 1][2] += dp[i][2]
        dp[i + 1][3] += dp[i][3]
    elif s[i] == "C":
        dp[i + 1][3] = dp[i + 1][3] + dp[i][2]
        dp[i + 1][0] += dp[i][0]
        dp[i + 1][1] += dp[i][1]
        dp[i + 1][2] += dp[i][2]
        dp[i + 1][3] += dp[i][3]
    else:
        for j in range(4):
            dp[i + 1][j] += 3 * dp[i][j]
        dp[i + 1][1] += dp[i][0]
        dp[i + 1][2] += dp[i][1]
        dp[i + 1][3] += dp[i][2]

print(dp[n][3] % mod)


Fixed submission:
s = input()
n = len(s)
mod = 10 ** 9 + 7
dp = [[0] * 4 for i in range(n + 1)]
dp[0][0] = 1

for i in range(n):
    if s[i] == "A":
        dp[i + 1][1] = dp[i + 1][1] + dp[i][0]
        dp[i + 1][0] += dp[i][0]
        dp[i + 1][1] += dp[i][1]
        dp[i + 1][2] += dp[i][2]
        dp[i + 1][3] += dp[i][3]
    elif s[i] == "B":
        dp[i + 1][2] = dp[i + 1][2] + dp[i][1]
        dp[i + 1][0] += dp[i][0]
        dp[i + 1][1] += dp[i][1]
        dp[i + 1][2] += dp[i][2]
        dp[i + 1][3] += dp[i][3]
    elif s[i] == "C":
        dp[i + 1][3] = dp[i + 1][3] + dp[i][2]
        dp[i + 1][0] += dp[i][0]
        dp[i + 1][1] += dp[i][1]
        dp[i + 1][2] += dp[i][2]
        dp[i + 1][3] += dp[i][3]
    else:
        for j in range(4):
            dp[i + 1][j] += 3 * dp[i][j]
        dp[i + 1][1] += dp[i][0]
        dp[i + 1][2] += dp[i][1]
        dp[i + 1][3] += dp[i][2]
    for j in range(4):
        dp[i + 1][0] %= mod
        dp[i + 1][1] %= mod
        dp[i + 1][2] %= mod
        dp[i + 1][3] %= mod

print(dp[n][3] % mod)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = list(map(int, input().split()))
S = [0] * N
S[0] = A[0]
for i in range(1, N):
    S[i] = S[i - 1] + A[i]

num = float("inf")
a = 0
b = 0
for i in range(1, N - 2):
    while S[a] < S[i] - S[a + 1]:
        a += 1
    b = i
    while S[b] - S[i] < S[N - 1] - S[b + 1]:
        b += 1

    P = [S[a], S[i] - S[a], S[b] - S[i], S[N - 1] - S[b]]
    num = min(num, abs(max(P) - min(P)))

print(num)


Fixed submission:
N = int(input())
A = list(map(int, input().split()))
S = [0] * N
S[0] = A[0]
for i in range(1, N):
    S[i] = S[i - 1] + A[i]

num = float("inf")
a = 0
b = 2
for i in range(1, N - 2):
    while S[a] < S[i] - S[a + 1]:
        a += 1
    b = max(b, i + 1)
    while S[b] - S[i] < S[N - 1] - S[b + 1]:
        b += 1

    P = [S[a], S[i] - S[a], S[b] - S[i], S[N - 1] - S[b]]
    num = min(num, abs(max(P) - min(P)))

print(num)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = list(map(int, input().split()))
INF = float("inf")
B = [[A[i], -INF] for i in range(1 << N)]
for i in range(N):
    for j in range(1 << N):
        if j & (1 << i):
            tmp = B[j] + B[j ^ (1 << i)]
            tmp = sorted(tmp, reverse=True)
            B[j] = tmp[:2]

ans = -INF
for i in range(1, 1 << N):
    ans = max(ans, sum(B[i]))
    print(ans)


Fixed submission:
N = int(input())
A = list(map(int, input().split()))
INF = float("inf")
B = [[A[i], -INF] for i in range(1 << N)]
for i in range(N):
    for j in range(1 << N):
        if j & (1 << i):
            tmp = B[j] + B[j ^ (1 << i)]
            tmp = sorted(tmp, reverse=True)
            B[j] = tmp[:2]

ans = -INF
for i in range(1, 1 << N):
    ans = max(ans, sum(B[i]))
    print(ans)
Buggy python submission (verdict: Runtime Error):
a = int(input())
b = int(input())
if a <= 8 and b <= 8:
    print("Yay!")
else:
    print(":(")

Fixed submission:
a, b = map(int, input().split())
if a <= 8 and b <= 8:
    print("Yay!")
else:
    print(":(")
Buggy python submission (verdict: Time Limit Exceeded):
N, A, B, K = map(int, input().split())

C = [0] * (3 * 10 ** 5 + 5)
rC = [0] * (3 * 10 ** 5 + 5)
MOD = 998244353

C[1] = 1
rC[1] = 1
for i in range(2, N + 1):
    C[i] = C[i - 1] * i % MOD

rC[N] = pow(C[N], MOD - 2, MOD)

for i in range(N, 1, -1):
    rC[i - 1] = rC[i] * i


def calc(n, m):
    return C[n] * rC[n - m] * rC[m]

num = 0
for i in range(N + 1):
    if (K - A * i) % B == 0:
        j = (K - i * A) // B
        if 0 <= j <= N:
            num += calc(N, i) * calc(N, j) % MOD

if K == 0:
    print(1)
else:
    print(num)

Fixed submission:
N, A, B, K = map(int, input().split())

C = [0] * (3 * 10 ** 5 + 5)
rC = [0] * (3 * 10 ** 5 + 5)
MOD = 998244353

C[0] = 1
rC[0] = 1
C[1] = 1
rC[1] = 1
for i in range(2, N + 1):
    C[i] = C[i - 1] * i % MOD

rC[N] = pow(C[N], MOD - 2, MOD)

for i in range(N, 1, -1):
    rC[i - 1] = rC[i] * i % MOD


def calc(n, m):
    return C[n] * rC[n - m] * rC[m] % MOD

num = 0
for i in range(N + 1):
    if (K - A * i) % B == 0:
        j = (K - i * A) // B
        if 0 <= j <= N:
            num += calc(N, i) * calc(N, j)
            num = num % MOD

if K == 0:
    print(1)
else:
    print(num % MOD)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = list(map(int, input().split()))
s = 0
num = 0
for i in range(N):
    l = i
    s = 0
    while l < N and s + A[l] == s ^ A[l]:
        s += A[l]
        l += 1
    num += l - i
    s -= A[i]

print(num)

Fixed submission:
N = int(input())
A = list(map(int, input().split()))
s = 0
num = 0
l = 0
for i in range(N):
    while l < N and s + A[l] == s ^ A[l]:
        s += A[l]
        l += 1
    num += l - i
    s -= A[i]

print(num)

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = list(map(int, input().split()))
xor = [0] * n
s = [0] * n
xor[0] = a[0]
s[0] = a[0]
for i in range(1, n):
    s[i] = s[i - 1] + a[i]
    xor[i] = xor[i - 1] ^ a[i]

num = 0
for i in range(n):
    for j in range(i, n):
        if i == 0:
            if xor[j] == s[j]:
                num += 1
        elif (xor[j] ^ xor[i - 1]) == (s[j] - s[i - 1]):
            num += 1
        if (xor[j] ^ xor[i - 1]) < (s[j] - s[i - 1]):
            break

print(num)

Fixed submission:
N = int(input())
A = list(map(int, input().split()))
s = 0
num = 0
l = 0
for i in range(N):
    while l < N and s + A[l] == s ^ A[l]:
        s += A[l]
        l += 1
    num += l - i
    s -= A[i]

print(num)
Buggy python submission (verdict: Time Limit Exceeded):
s = input()
k = int(input())
t = sorted(list(s))
num = []
while len(num) < k:
    a = t.pop(0)
    indexes = [i for i, x in enumerate(s) if x == a]
    z = 0
    while z < len(indexes):
        i = indexes[z]
        q = 1
        while i + q <= len(s):
            if s[i:i + q] not in num:
                num.append(s[i:i + q])
            q += 1
        z += 1

num = sorted(num)
print(num[k - 1])

Fixed submission:
s = input()
k = int(input())
t = sorted(list(s))
num = []
while len(num) < k:
    a = t.pop(0)
    indexes = [i for i, x in enumerate(s) if x == a]
    z = 0
    while z < len(indexes):
        i = indexes[z]
        q = 1
        while q <= 5:
            if s[i:i + q] not in num:
                num.append(s[i:i + q])
            q += 1
        z += 1

num = sorted(num)
print(num[k - 1])

Buggy python submission (verdict: Time Limit Exceeded):
s = input()
k = int(input())
t = sorted(list(s))
num = []
while len(num) < k:
    a = t.pop(0)
    for i in range(len(s)):
        if s[i] == a:
            q = 1
            while i + q <= len(s):
                if s[i:i + q] not in num:
                    num.append(s[i:i + q])
                q += 1

num = sorted(num)
print(num[k - 1])

Fixed submission:
s = input()
k = int(input())
t = sorted(list(s))
num = []
while len(num) < k:
    a = t.pop(0)
    indexes = [i for i, x in enumerate(s) if x == a]
    z = 0
    while z < len(indexes):
        i = indexes[z]
        q = 1
        while q <= 5:
            if s[i:i + q] not in num:
                num.append(s[i:i + q])
            q += 1
        z += 1

num = sorted(num)
print(num[k - 1])