Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
import math
N = int(input())
A = list(map(int, input().split()))

DP_first = [0] * N
DP_last = [0] * N

DP_first[0] = A[0]
DP_last[0] = A[-1]

for i in range(1, N):
    DP_first[i] = math.gcd(DP_first[i-1], A[i])
    DP_last[i] = math.gcd(DP_last[i-1], A[-1-i])

ans = max(DP_first[N-2], DP_last[N-2])
for i in range(1, N-1):
    ans = max(ans, math.gcd(DP_first[i-1], DP_last[N-2-i]))
print(ans)


Fixed submission:
import fractions
N = int(input())
A = list(map(int, input().split()))

DP_first = [0] * N
DP_last = [0] * N

DP_first[0] = A[0]
DP_last[0] = A[-1]

for i in range(1, N):
    DP_first[i] = fractions.gcd(DP_first[i-1], A[i])
    DP_last[i] = fractions.gcd(DP_last[i-1], A[-1-i])

ans = max(DP_first[N-2], DP_last[N-2])
for i in range(1, N-1):
    ans = max(ans, fractions.gcd(DP_first[i-1], DP_last[N-2-i]))
print(ans)

Buggy python submission (verdict: Runtime Error):
import math
N = int(input())
A = list(map(int, input().split()))

DP_first = [0] * N
DP_last = [0] * N

DP_first[0] = A[0]
DP_last[0] = A[-1]

for i in range(1, N):
    DP_first[i] = math.gcd(DP_first[i-1], A[i])
    DP_last[i] = math.gcd(DP_last[i-1], A[-1-i])

ans = max(DP_first[N-2], DP_last[N-2])
for i in range(1, N-1):
    ans = max(ans, math.gcd(DP_first[i-1], DP_last[N-2-i]))
print(ans)


Fixed submission:
import fractions
N = int(input())
A = list(map(int, input().split()))

DP_first = [0] * N
DP_last = [0] * N

DP_first[0] = A[0]
DP_last[0] = A[-1]

for i in range(1, N):
    DP_first[i] = fractions.gcd(DP_first[i-1], A[i])
    DP_last[i] = fractions.gcd(DP_last[i-1], A[-1-i])

ans = max(DP_first[N-2], DP_last[N-2])
for i in range(1, N-1):
    ans = max(ans, fractions.gcd(DP_first[i-1], DP_last[N-2-i]))
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np

N = int(input())
A = np.array(list(map(int, input().split())))
ans = 0

for i in range(N):
    A_ = np.concatenate([A[:i], A[i+1:]])
    a = np.gcd.reduce(A_)
    ans = max(ans, a)

print(ans)


Fixed submission:
import fractions
N = int(input())
A = list(map(int, input().split()))

DP_first = [0] * N
DP_last = [0] * N

DP_first[0] = A[0]
DP_last[0] = A[-1]

for i in range(1, N):
    DP_first[i] = fractions.gcd(DP_first[i-1], A[i])
    DP_last[i] = fractions.gcd(DP_last[i-1], A[-1-i])

ans = max(DP_first[N-2], DP_last[N-2])
for i in range(1, N-1):
    ans = max(ans, fractions.gcd(DP_first[i-1], DP_last[N-2-i]))
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import heapq

X, Y, Z, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)
To = [[[True] * Z for _ in range(Y)] for __ in range(X)]
Q = []
To[0][0][0] = False
heapq.heappush(Q, (-(A[0] + B[0] + C[0]), 0, 0, 0))
cnt = K
while cnt > 0:
    cnt -= 1
    ans, a, b, c = heapq.heappop(Q)
    print(-ans)
    if (a + 1 < X) and (To[a+1][b][c]):
        heapq.heappush(Q, (-(A[a + 1] + B[b] + C[c]), a + 1, b, c))
        To[a+1][b][c] = False
    if (b + 1 < Y) and (To[a][b+1][c]):
        heapq.heappush(Q, (-(A[a] + B[b + 1] + C[c]), a, b + 1, c))
        To[a][b+1][c] = False
    if (c + 1 < Z) and (To[a][b][c+1]):
        heapq.heappush(Q, (-(A[a] + B[b] + C[c + 1]), a, b, c + 1))
        To[a][b][c+1] = False


Fixed submission:
X, Y, Z, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

D = []
for a in A:
    for b in B:
        D.append(a + b)
D.sort(reverse=True)
if len(D) > K:
    D = D[:K]
E = []
for d in D:
    for c in C:
        E.append(c + d)

E.sort(reverse=True)
for i, e in enumerate(E):
    if i >= K:
        break
    print(e)

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


X, Y, Z, K = map(int, input().split())
A = list(map(int, input().split()))+[-100]*10
B = list(map(int, input().split()))+[-100]*10
C = list(map(int, input().split()))+[-100]*10
A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)
Done = [[[False] * Z for _ in range(Y)] for __ in range(X)]
Q = []
Done[0][0][0] = True
heapq.heappush(Q, (-(A[0] + B[0] + C[0]), 0, 0, 0))
cnt = K
while cnt > 0:
    cnt -= 1
    ans, a, b, c = heapq.heappop(Q)
    print(-ans)
    if (a + 1 < X) and not(Done[a+1][b][c]):
        heapq.heappush(Q, (-(A[a + 1] + B[b] + C[c]), a + 1, b, c))
        Done[a+1][b][c] = True
    if (b + 1 < Y) and not (Done[a][b+1][c]):
        heapq.heappush(Q, (-(A[a] + B[b + 1] + C[c]), a, b + 1, c))
        Done[a][b+1][c] = True
    if (c + 1 < Z) and not(Done[a][b][c+1]):
        heapq.heappush(Q, (-(A[a] + B[b] + C[c + 1]), a, b, c + 1))
        Done[a][b][c+1] = True


Fixed submission:
X, Y, Z, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

D = []
for a in A:
    for b in B:
        D.append(a + b)
D.sort(reverse=True)
if len(D) > K:
    D = D[:K]
E = []
for d in D:
    for c in C:
        E.append(c + d)

E.sort(reverse=True)
for i, e in enumerate(E):
    if i >= K:
        break
    print(e)
Buggy python submission (verdict: Time Limit Exceeded):
# Union-Find
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]


def unite(x, y):
    x = find(x)
    y = find(y)
    if x == y:
        return False
    if par[x] > par[y]:
        x, y = y, x
    par[x] += par[y]
    par[y] = x
    return True


def same(x, y):
    return find(x) == find(y)


def size(x):
    return -par[find(x)]


def count(A):
    ans = N * (N-1) // 2
    for a in A:
        if a < 0:
            b = - a
            ans -= b * (b-1) // 2
    return ans



N, M = map(int, input().split())
# 負のとき size, 非負のとき parent
par = [-1] * N
Bridge = [tuple(map(int, input().split())) for _ in range(M)]
Bridge = Bridge[::-1]
Ans = []
for (a, b) in Bridge:
    Ans.append(count(par))
    unite(a-1, b-1)


Ans = Ans[::-1]

for an in Ans:
    print(an)



Fixed submission:
# Union-Find
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]


def unite(x, y):
    x = find(x)
    y = find(y)
    if x == y:
        return False
    if par[x] > par[y]:
        x, y = y, x
    par[x] += par[y]
    par[y] = x
    return True


def same(x, y):
    return find(x) == find(y)


def size(x):
    return -par[find(x)]



N, M = map(int, input().split())
# 負のとき size, 非負のとき parent
par = [-1] * N
Bridge = [tuple(map(int, input().split())) for _ in range(M)]
Bridge = Bridge[::-1]
Ans = []
ans = N * (N-1) // 2
for (a, b) in Bridge:
    Ans.append(ans)
    if find(a-1) != find(b-1):
        x = size(a-1)
        y = size(b-1)
    else:
        x = 0
        y = 0
    unite(a-1, b-1)
    ans -= x * y


Ans = Ans[::-1]

for an in Ans:
    print(an)
Buggy python submission (verdict: Time Limit Exceeded):
import bisect

A, B, Q = map(int, input().split())
Shrine = [int(input()) for _ in range(A)]
Temple = [int(input()) for _ in range(B)]

Shrine = [-100000000000] + Shrine + [100000000000]
Temple = [-100000000000] + Temple + [100000000000]

for i in range(Q):
    x = int(input())
    nums = bisect.bisect_left(Shrine, x)
    tems = bisect.bisect_left(Temple, x)
    ans1 = max(abs(Shrine[nums]-x), abs(Temple[tems]-x))
    ans2 = max(abs(x - Shrine[nums-1]), abs(x - Temple[tems-1]))
    ans3 = abs(Shrine[nums]-x) * 2 + abs(x - Temple[tems-1])
    ans4 = abs(Temple[tems]-x) * 2 + abs(x - Shrine[nums-1])
    ans5 = abs(x - Shrine[nums-1]) * 2 + abs(Temple[tems]-x)
    ans6 = abs(x - Temple[tems-1]) * 2 + abs(Shrine[nums]-x)

    print(min(ans1, ans2, ans3, ans4, ans5, ans6))

Fixed submission:
import bisect
import sys
input = sys.stdin.readline

A, B, Q = map(int, input().split())
Shrine = [int(input()) for _ in range(A)]
Temple = [int(input()) for _ in range(B)]
X = [int(input()) for _ in range(Q)]
Shrine = [-100000000000] + Shrine + [100000000000]
Temple = [-100000000000] + Temple + [100000000000]

for x in X:
    nums = bisect.bisect_left(Shrine, x)
    tems = bisect.bisect_left(Temple, x)
    ans1 = max(abs(Shrine[nums]-x), abs(Temple[tems]-x))
    ans2 = max(abs(x - Shrine[nums-1]), abs(x - Temple[tems-1]))
    ans3 = abs(Shrine[nums]-x) * 2 + abs(x - Temple[tems-1])
    ans4 = abs(Temple[tems]-x) * 2 + abs(x - Shrine[nums-1])
    ans5 = abs(x - Shrine[nums-1]) * 2 + abs(Temple[tems]-x)
    ans6 = abs(x - Temple[tems-1]) * 2 + abs(Shrine[nums]-x)

    print(min(ans1, ans2, ans3, ans4, ans5, ans6))
Buggy python submission (verdict: Time Limit Exceeded):
N, M = map(int, input().split())
A = list(map(int, input().split()))
Need = [-1, 2, 5, 5, 4, 5, 6, 3, 7, 6]
Usable = {}
for a in A:
    if Need[a] in Usable:
        for key, value in Usable.items():
            if Need[a] == key and a > value:
                Usable[key] = a
    else:
        Usable[Need[a]] = a
Usable = sorted(Usable.items(), reverse=True)
Num = [-1] * (N + 1)
Num[0] = ''
for i in range(1, N+1):
    for u, v in Usable:
        if i < u:
            continue
        if type(Num[i - u]) is str:
            if Num[i - u] == '':
                Num[i] = Num[i - u] + str(v)
            elif int(Num[i]) < int(Num[i - u] + str(v)):
                Num[i] = Num[i - u] + str(v)

print(Num[N])

Fixed submission:
import sys
input = sys.stdin.buffer.readline

N, M = map(int, input().split())
A = list(map(int, input().split()))
Need = [-1, 2, 5, 5, 4, 5, 6, 3, 7, 6]
Usable = {}
for a in A:
    if Need[a] in Usable:
        for key, value in Usable.items():
            if Need[a] == key and a > value:
                Usable[key] = a
    else:
        Usable[Need[a]] = a
Num = [-1] * (N + 1)
Num[0] = 0
for i in range(1, N+1):
    for u, v in Usable.items():
        if i < u:
            continue
        if Num[i - u] >= 0:
            if Num[i - u] == 0:
                Num[i] = max(v, Num[i])
            elif Num[i] < Num[i - u] * 10 + v:
                Num[i] = Num[i - u] * 10 + v

print(Num[N])
Buggy python submission (verdict: Time Limit Exceeded):
from copy import deepcopy


N, K = map(int, input().split())
Items_ = [tuple(map(int, input().split())) for _ in range(N)]
Items_.sort(reverse=True)
Items = []
Now = [Items_[0][1]]
now = Items_[0][0]
for item in Items_[1:]:
    if item[0] == now:
        Now.append(Now[-1]+item[1])
    else:
        Items.append(Now)
        Now = [item[1]]
        now = item[0]
if Now:
    Items.append(Now)

DP = [[-float('inf')] * (K+1) for _ in range(K+1)]
DP[0][0] = 0
for i, item in enumerate(Items):
    D = deepcopy(DP)
    for j in range(K):
        for k in range (K):
            if DP[j][k] < 0:
                continue
            for l, it in enumerate(item, 1):
                if j + l <= K and k < K:
                    D[j + l][k + 1] = max(D[j + l][k + 1], DP[j][k] + it)
    DP = D

ans = 0
for i, item in enumerate(DP[K]):
    ans = max(ans, item + i**2)
print(ans)


Fixed submission:
from collections import defaultdict

N, K = map(int, input().split())
Items = [tuple(map(int, input().split())) for _ in range(N)]
Items.sort(reverse=True, key=lambda x: x[1])
Kinds = defaultdict(int)
ans = 0
k = 0
Candidates = []
for i, (t, d) in enumerate(Items):
    if i < K:
        ans += d
        if t not in Kinds:
            k += 1
        else:
            Candidates.append(d)
        Kinds[t] += 1
        if i == K - 1:
            ans += k ** 2
            a = ans
    else:
        if Kinds[t]:
            continue
        if not Candidates:
            break
        else:
            x = Candidates.pop()
            a -= x
            a -= k ** 2
            k += 1
            a += d
            a += k ** 2
            Kinds[t] -= 1
            ans = max(ans, a)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int, input().split())
H = [float('inf')] + list(map(int, input().split()))
DP = [float('inf')] * (N+1)
DP[0] = 0
DP[1] = 0

for i, h in enumerate(H[1:], 1):
    for k in range(1, K+1):
        if i + k > N:
            break
        DP[i + k] = min(DP[i+k], DP[i] + abs(H[i + k] - h))
print(DP[N])




Fixed submission:
N, K = map(int, input().split())
High = list(map(int, input().split()))

DP = [float('inf')] * N
DP[0] = 0
for i in range(N - 1):
    for j in range(i + 1, min(N, i + K + 1)):
        DP[j] = min(DP[j], DP[i] + abs(High[i] - High[j]))
print(DP[N - 1])
Buggy python submission (verdict: Runtime Error):
N, W = map(int, input().split())
Items = [tuple(map(int, input().split())) for _ in range(N)]
DP = [float('inf')] * 10 ** 5
DP[0] = 0
for w, v in Items:
    D = DP[:]
    for i, d in enumerate(DP):
        if w + d > W:
            continue
        D[i + v] = min(DP[i + v], w + d)
    DP = D
ans = 0
for i, d in enumerate(DP):
    if d == float('inf'):
        continue
    ans = i
print(ans)

Fixed submission:
N, W = map(int, input().split())
Weight = [0]
Value = [0]
ans = 0
for i in range(N):
    w, v = map(int, input().split())
    Weight.append(w)
    Value.append(v)
VS = sum(Value)
DP = [[float('inf')] * (VS + 1) for i in range(N + 1)]

for n in range(N + 1):
    for val in range(VS + 1):
        if val == 0:
            DP[n][val] = 0
        elif Value[n] > val:
            DP[n][val] = DP[n - 1][val]
        else:
            DP[n][val] = min(DP[n - 1][val], DP[n - 1][val - Value[n]] + Weight[n])
            if (n == N) and (DP[n][val] <= W):
                ans = max(ans, val)

print(ans)

Buggy python submission (verdict: Runtime Error):
N, W = map(int, input().split())
Weight = [0]
Value = [0]

for i in range(N):
    w, v = map(int, input().split())
    Weight.append(w)
    Value.append(v)
if sum(Weight) <= W:
    print(sum(Value))
    exit()

DP = [[0] * (W + 1) for i in range(N + 1)]
for n in range(1, N + 1):
    for wei in range(W + 1):
        if Weight[n] > wei:
            DP[n][wei] = DP[n - 1][wei]
        else:
            DP[n][wei] = max(DP[n - 1][wei], DP[n - 1][wei - Weight[n]] + Value[n])
print(DP[N][W])

Fixed submission:
N, W = map(int, input().split())
Weight = [0]
Value = [0]
ans = 0
for i in range(N):
    w, v = map(int, input().split())
    Weight.append(w)
    Value.append(v)
VS = sum(Value)
DP = [[float('inf')] * (VS + 1) for i in range(N + 1)]

for n in range(N + 1):
    for val in range(VS + 1):
        if val == 0:
            DP[n][val] = 0
        elif Value[n] > val:
            DP[n][val] = DP[n - 1][val]
        else:
            DP[n][val] = min(DP[n - 1][val], DP[n - 1][val - Value[n]] + Weight[n])
            if (n == N) and (DP[n][val] <= W):
                ans = max(ans, val)

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(1000000000)
mod = 10**9 + 7
H, W = map(int, input().split())
Maze = [[0]*W for _ in range(H)]
Memo = [[0]*W for _ in range(H)]
Memo[H-1][W-1] = 1
for i in range(H):
    S = input()
    for j in range(W):
        Maze[i][j] = S[j]

dx = [1, 0]
dy = [0, 1]


def clear_maze(x, y):
    if (x == W) and (y == H):
        return 1
    if Memo[y-1][x-1] != 0:
        return Memo[y-1][x-1]
    ans = 0
    for z in range(2):
        nx = x + dx[z]
        ny = y + dy[z]
        if (nx > W) or (ny > H):
            continue
        if Maze[ny-1][nx-1] == '.':
            ans += clear_maze(nx, ny)
    ans %= mod
    Memo[y-1][x-1] = ans
    return ans


print(clear_maze(1, 1) % mod)

Fixed submission:
mod = 10**9 + 7
H, W = map(int, input().split())
Maze = [[0]*(W+1) for _ in range(H+1)]
Memo = [[0]*(W+1) for _ in range(H+1)]
Memo[H-1][W-1] = 1
for i in range(H):
    S = input()
    for j in range(W):
        Maze[i][j] = S[j]

for a in range(H-1, -1, -1):
    for b in range(W-1, -1, -1):
        if Maze[a][b] == '#':
            Memo[a][b] = 0
        elif (a == H-1) and (b == W-1):
            continue
        else:
            Memo[a][b] = Memo[a+1][b] + Memo[a][b+1]
            Memo[a][b] %= mod
print(Memo[0][0])

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(1000000000)
mod = 10**9 + 7
H, W = map(int, input().split())
Maze = [[0]*W for _ in range(H)]
Memo = [[0]*W for _ in range(H)]
Memo[H-1][W-1] = 1
for i in range(H):
    S = input()
    for j in range(W):
        Maze[i][j] = S[j]

dx = [1, 0]
dy = [0, 1]


def clear_maze(x, y):
    if (x == W) and (y == H):
        return 1
    if Memo[y-1][x-1] != 0:
        return Memo[y-1][x-1]
    ans = 0
    for z in range(2):
        nx = x + dx[z]
        ny = y + dy[z]
        if (nx > W) or (ny > H):
            continue
        if Maze[ny-1][nx-1] == '.':
            ans += clear_maze(nx, ny)
    ans %= mod
    Memo[y-1][x-1] = ans
    return ans


print(clear_maze(1, 1) % mod)

Fixed submission:
mod = 10**9 + 7
H, W = map(int, input().split())
Maze = [[0]*(W+1) for _ in range(H+1)]
Memo = [[0]*(W+1) for _ in range(H+1)]
Memo[H-1][W-1] = 1
for i in range(H):
    S = input()
    for j in range(W):
        Maze[i][j] = S[j]

for a in range(H-1, -1, -1):
    for b in range(W-1, -1, -1):
        if Maze[a][b] == '#':
            Memo[a][b] = 0
        elif (a == H-1) and (b == W-1):
            continue
        else:
            Memo[a][b] = Memo[a+1][b] + Memo[a][b+1]
            Memo[a][b] %= mod
print(Memo[0][0])
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = list(map(int, input().split()))
n = N % 2

DP = [[0] * (N+1) for _ in range(N+1)]

for w in range(1, N+1):
    for i in range(N):
        j = i + w
        if j > N:
            continue
        if (w+n) % 2 == 1:
            DP[i][j] = min(DP[i+1][j] - A[i], DP[i][j-1] - A[j-1])
        else:
            DP[i][j] = max(DP[i+1][j] + A[i], DP[i][j-1] + A[j-1])

print(DP[0][N])


Fixed submission:
N = int(input())
A = list(map(int, input().split()))
n = N % 2

DP = [[0] * (N+1) for _ in range(N+1)]

for w in range(1, N+1):
    for i in range(N):
        j = i + w
        if j > N:
            continue
        if (w+n) % 2 == 1:
            DP[i][j] = min(DP[i+1][j] - A[i], DP[i][j-1] - A[j-1])
        else:
            DP[i][j] = max(DP[i+1][j] + A[i], DP[i][j-1] + A[j-1])

print(DP[0][N])
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
Match = [0] * N
mod = 10**9 + 7
for i in range(N):
    A = list(map(int, input().split()))
    m = 0
    for j, a in enumerate(A):
        if a:
            m |= (1 << j)
    Match[i] = m

DP = [0] * (1 << N)
DP[0] = 1

for m in Match:
    D = DP[:]
    for i, d in enumerate(DP):
        if d:
            for j in range(N):
                if (m >> j) & 1 == 1:
                    if (i >> j) & 1 == 0:
                        D[i| (1 << j)] += d
                        D[i| (1 << j)] %= mod
    DP = D
print(DP[-1] % mod)

Fixed submission:
N = int(input())
Match = [0] * N
mod = 10**9 + 7
for i in range(N):
    A = list(map(int, input().split()))
    m = 0
    for j, a in enumerate(A):
        if a:
            m |= (1 << j)
    Match[i] = m

DP = [0] * (1 << N)
DP[0] = 1

bit_count = [0]
for _ in range(N):
    bit_count += [x+1 for x in bit_count]

for i in range((1 << N) - 1):
    c = bit_count[i]
    if DP[i] == 0:
        continue
    for j in range(N):
        if (Match[c] >> j) & 1 == 1:
            if (i >> j) & 1 == 0:
                DP[i| (1 << j)] += DP[i]
                DP[i| (1 << j)] %= mod
print(DP[-1] % mod)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
Match = [0] * N
mod = 10**9 + 7
for i in range(N):
    A = list(map(int, input().split()))
    m = 0
    for j, a in enumerate(A):
        if a:
            m |= (1 << j)
    Match[i] = m

DP = [0] * (1 << N)
DP[0] = 1

for m in Match:
    D = DP[:]
    for i, d in enumerate(DP):
        for j in range(N):
            if (m >> j) & 1 == 1:
                if (i >> j) & 1 == 0:
                    D[i| (1 << j)] += d
                    D[i| (1 << j)] %= mod
    DP = D
print(DP[-1] % mod)

Fixed submission:
N = int(input())
Match = [0] * N
mod = 10**9 + 7
for i in range(N):
    A = list(map(int, input().split()))
    m = 0
    for j, a in enumerate(A):
        if a:
            m |= (1 << j)
    Match[i] = m

DP = [0] * (1 << N)
DP[0] = 1

bit_count = [0]
for _ in range(N):
    bit_count += [x+1 for x in bit_count]

for i in range((1 << N) - 1):
    c = bit_count[i]
    if DP[i] == 0:
        continue
    for j in range(N):
        if (Match[c] >> j) & 1 == 1:
            if (i >> j) & 1 == 0:
                DP[i| (1 << j)] += DP[i]
                DP[i| (1 << j)] %= mod
print(DP[-1] % mod)
Buggy python submission (verdict: Time Limit Exceeded):
S = input()
ans = 0
num = 0

while 'W' in S:
    ans += S.find('W') - num
    num += 1
    S = S[:S.find('W')] + 'E' + S[S.find('W') + 1:]

print(ans)

Fixed submission:
S = input()
ans = - int((1 + S.count('W')) * S.count('W')/2)
num = 0

for i in range(len(S)):
    if S[i] == 'W':
        ans += i + 1
print(ans)
Buggy python submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10000)

N, X = map(int, input().split())
Burger = ['P']
for i in range(1,N+1):
    Burger_ = 'B' + Burger[i-1] + 'P' + Burger[i-1] + 'B'
    Burger.append(Burger_)
print(Burger[N][0:X].count('P'))

Fixed submission:
N, X = map(int, input().split())
Size = [1]
Patty = [1]

for i in range(51):
    Size.append(Size[-1] * 2 + 3)
    Patty.append(Patty[-1] * 2 + 1)


def count_p(n, x):
    if x == 0:
        return 0
    if n == 0:
        return min(x, 1)
    if (Size[n]+1) // 2 > x:
        return count_p(n-1, x-1)
    elif (Size[n]+1) // 2 == x:
        return Patty[n-1] + 1
    else:
        return Patty[n-1] + 1 + count_p(n-1, x - ((Size[n]+1) // 2))


print(count_p(N, X))

Buggy python submission (verdict: Runtime Error):
N, X = map(int, input().split())
Burger = ['P']
for i in range(1,N+1):
    Burger_ = 'B' + Burger[i-1] + 'P' + Burger[i-1] + 'B'
    Burger.append(Burger_)
print(Burger[N][0:X].count('P'))

Fixed submission:
N, X = map(int, input().split())
Size = [1]
Patty = [1]

for i in range(51):
    Size.append(Size[-1] * 2 + 3)
    Patty.append(Patty[-1] * 2 + 1)


def count_p(n, x):
    if x == 0:
        return 0
    if n == 0:
        return min(x, 1)
    if (Size[n]+1) // 2 > x:
        return count_p(n-1, x-1)
    elif (Size[n]+1) // 2 == x:
        return Patty[n-1] + 1
    else:
        return Patty[n-1] + 1 + count_p(n-1, x - ((Size[n]+1) // 2))


print(count_p(N, X))
Buggy python submission (verdict: Runtime Error):
x = X + Y/2
print(x)

Fixed submission:
X, Y = map(int, input().split())

print(X + Y//2)
Buggy python submission (verdict: Runtime Error):
from math import gcd
from functools import reduce

n, x = map(int,input().split())
City = list(map(int, input().split()))
Distance = [0] * n

for i in range(n):
    Distance[i] = abs(City[i]-x)

ans = reduce(gcd, Distance)

print(ans)


Fixed submission:
n, x = map(int,input().split())
City = list(map(int, input().split()))
Distance = [0] * n

for i in range(n):
    Distance[i] = abs(City[i]-x)

Distance.sort()
ans = Distance[0]

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

for i in range(1,n):
    ans = gcd(ans, Distance[i])

print(ans)
Buggy python submission (verdict: Runtime Error):
S = input()
K = input()
if S[0] == '1':
    if K == 1:
        print(S[0])
    else:
        print(S[1])
else:
    print(S[0])

Fixed submission:
S = input()
K = int(input())
ans = 1
for i, s in enumerate(S):
    if i+1 == K:
        ans = s
        break
    if s == '1':
        continue
    else:
        ans = s
        break

print(ans)

Buggy python submission (verdict: Runtime Error):
S = input()
K = input()
if S[0] == '1':
    print(S[1])
else:
    print(S[0])

Fixed submission:
S = input()
K = int(input())
ans = 1
for i, s in enumerate(S):
    if i+1 == K:
        ans = s
        break
    if s == '1':
        continue
    else:
        ans = s
        break

print(ans)