Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
INF = float('inf')
ans = INF
L, R = map(int, input().split())
for i in range(L, R + 1):
    for j in range(i + 1, R + 1):
        ans = min(ans, i * j % 2019)
print(ans)

Fixed submission:
ans = 2020
L, R = map(int, input().split())
for i in range(L, R + 1):
    for j in range(i + 1, R + 1):
        mod = i * j % 2019
        if mod == 0:
            print(0)
            exit(0)
        ans = min(ans, mod)
print(ans)

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


L, R = map(int, input().split())
num_list = [i for i in range(L, R + 1)]
l = list(itertools.combinations(num_list, 2))
INF = float('inf')
ans = INF
for i in range(len(l)):
    if ans > (l[i][0] * l[i][1]) % 2019:
        ans = (l[i][0] * l[i][1]) % 2019
print(ans)

Fixed submission:
ans = 2020
L, R = map(int, input().split())
for i in range(L, R + 1):
    for j in range(i + 1, R + 1):
        mod = i * j % 2019
        if mod == 0:
            print(0)
            exit(0)
        ans = min(ans, mod)
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import itertools
L, R = map(int, input().split())
num_list = [i for i in range(L, R + 1)]
l = list(itertools.combinations(num_list, 2))

ans_list = [0 for _ in range(len(l))]
for i in range(len(ans_list)):
    ans_list[i] = (l[i][0] * l[i][1]) % 2019
print(min(ans_list))

Fixed submission:
ans = 2020
L, R = map(int, input().split())
for i in range(L, R + 1):
    for j in range(i + 1, R + 1):
        mod = i * j % 2019
        if mod == 0:
            print(0)
            exit(0)
        ans = min(ans, mod)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    H, W = map(int, input().split())
    grid = [list(input()) for _ in range(H)]
    L = [[0] * W for _ in range(H)]
    R = [[0] * W for _ in range(H)]
    D = [[0] * W for _ in range(H)]
    U = [[0] * W for _ in range(H)]
    for h in range(H):
        for w in range(W):
            if grid[h][w] == '#':
                continue
            if w == 0:
                L[h][w] = 1
            else:
                L[h][w] = L[h][w-1] + 1
            if h == 0:
                U[h][w] = 1
            else:
                U[h][w] = U[h-1][w] + 1
    for h in range(H - 1, -1, -1):
        for w in range(W - 1, -1, -1):
            if grid[h][w] == '#':
                continue
            if w == W - 1:
                R[h][w] = 1
            else:
                R[h][w] = R[h][w + 1] + 1
            if h == H - 1:
                D[h][w] = 1
            else:
                D[h][w] = D[h + 1][w] + 1
    ans = 0
    for h in range(H):
        for w in range(W):
            ans = max(ans, L[h][w] + R[h][w] + U[h][w] + D[h][w] - 3)
    print(ans)


if __name__ == '__main__':
    main()

Fixed submission:
def main():
    H, W = map(int, input().split())
    grid = [list(input()) for _ in range(H)]
    L = [[0] * W for _ in range(H)]
    R = [[0] * W for _ in range(H)]
    D = [[0] * W for _ in range(H)]
    U = [[0] * W for _ in range(H)]
    for h in range(H):
        for w in range(W):
            if grid[h][w] == '#':
                continue
            if w == 0:
                L[h][w] = 1
            else:
                L[h][w] = L[h][w-1] + 1
            if h == 0:
                U[h][w] = 1
            else:
                U[h][w] = U[h-1][w] + 1
    for h in range(H - 1, -1, -1):
        for w in range(W - 1, -1, -1):
            if grid[h][w] == '#':
                continue
            if w == W - 1:
                R[h][w] = 1
            else:
                R[h][w] = R[h][w + 1] + 1
            if h == H - 1:
                D[h][w] = 1
            else:
                D[h][w] = D[h + 1][w] + 1
    ans = 0
    for h in range(H):
        for w in range(W):
            ans = max(ans, L[h][w] + R[h][w] + U[h][w] + D[h][w] - 3)
    print(ans)


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
from heapq import heappush, heappop
from itertools import permutations, accumulate, combinations
from math import pi, ceil, floor
import numpy as np
from collections import defaultdict, deque
from operator import itemgetter
from bisect import bisect_left, bisect_right, insort_left, insort_right
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10 ** 6)
# MOD = 10 ** 9 + 7
# INF = float("inf")


def main():
    n, m = map(int, input().split())
    A = list(map(int, input().split()))
    for i in range(m):
        b, c = map(int,input().split())
        A += [c] * b
    A.sort(reverse=True)
    print(sum(A[:n]))


if __name__ == '__main__':
    main()

Fixed submission:
from heapq import heappush, heappop, heapify
from itertools import permutations, accumulate, combinations
from math import pi, ceil, floor
import numpy as np
from collections import defaultdict, deque
from operator import itemgetter
from bisect import bisect_left, bisect_right, insort_left, insort_right
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10 ** 6)
# MOD = 10 ** 9 + 7
# INF = float("inf")


def main():
    n, m = map(int, input().split())
    A = list(map(int, input().split()))
    A.sort()
    B = [tuple(map(int, input().split())) for _ in range(m)]
    B.sort(reverse=True, key=itemgetter(1))
    tmp = 0
    for b, c in B:
        for i in range(tmp, b+tmp):
            if A[i] < c:
                A[i] = c
                tmp += 1
                if i == n-1:
                    print(sum(A))
                    exit()
            else:
                print(sum(A))
                exit()
    print(sum(A))


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
n = int(input())
G = [[] for _ in range(n)]  # 頂点の個数分準備
for i in range(n - 1):  # 辺の数はn-1
    u, v, w = map(int, input().split())
    u -= 1
    v -= 1
    G[u].append([v, w])
    G[v].append([u, w])
ans = [-1] * n
ans[0] = 0
que = deque([0])
while que:
    tmp = que.popleft()  # 幅優先探索
    for u, w in G[tmp]:
        if ans[u] != -1:  # すでに訪問済みの時
            continue
        ans[u] = ans[tmp] + w  # 辺の長さを追加
        que.append(u)  # queに追加

for c in ans:
    if c % 2 == 0:
        print(0)
    else:
        print(1)

Fixed submission:
import sys

sys.setrecursionlimit(100000000)


def dfs(u, c):  # 引数には頂点の番号と色を入れる
    ans[u] = c  # 探索済みにする
    for v, w in G[u]:
        if ans[v] != -1:  # 探索していた時はスルー
            continue
        if ans[v] != c and w % 2 == 0:  # 距離が偶数で、未訪問あるいは色が違う時は同じ色にする
            dfs(v, c)
        elif ans[v] != c and w % 2 != 0:  # 距離が奇数で、未訪問あるいは色が違う時、違う色にする。
            dfs(v, 1-c)


n = int(input())
G = [[] for _ in range(n)]  # 頂点の個数分準備
for i in range(n-1):  # 辺の数はn-1
    u, v, w = map(int, input().split())
    u -= 1
    v -= 1
    G[u].append([v, w])
    G[v].append([u, w])
ans = [-1] * n
dfs(0, 0)
for a in ans:
    print(a)
Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
import sys

sys.setrecursionlimit(1000000)

H, W = map(int, input().split())
G = [list(input()) for _ in range(H)]
que = deque()
# 始点を追加
for i in range(H):
    for j in range(W):
        if G[i][j] == '#':
            que.append([i, j])
cnt = -1
while que:
    cnt += 1
    next_que = deque()
    while que:
        h, w = que.popleft()  # BFSで探索
        dh = [1, 0, -1, 0]
        dw = [0, 1, 0, -1]
        for j in range(4):
            nh = h + dh[j]
            nw = w + dw[j]
            if 0 <= nh < H and 0 <= nw < W and G[nh][nw] == '.':
                G[nh][nw] = '#'
                next_que.append([nh, nw])
    que = next_que
print(cnt)

Fixed submission:
from collections import deque
import sys

sys.setrecursionlimit(1000000)

H, W = map(int, input().split())
G = [list(input()) for _ in range(H)]
que = deque()
# 始点を追加
for i in range(H):
    for j in range(W):
        if G[i][j] == '#':
            que.append([i, j])
cnt = -1
while que:
    cnt += 1
    next_que = deque()
    while que:
        h, w = que.popleft()  # BFSで探索
        dh = [1, 0, -1, 0]
        dw = [0, 1, 0, -1]
        for j in range(4):
            nh = h + dh[j]
            nw = w + dw[j]
            if 0 <= nh < H and 0 <= nw < W and G[nh][nw] == '.':
                G[nh][nw] = '#'
                next_que.append([nh, nw])
    que = next_que
print(cnt)
Buggy python submission (verdict: Runtime Error):
from fractions import gcd
from functools import reduce


def gcd_list(numbers):
    return reduce(fractions.gcd(), numbers)


n = int(input())
num_list = list(map(int,input().split()))
gcd = [1 for _ in range(n-1)]
for i in range(n-1):
    num = num_list[:i] + num_list[(i + 1):]
    gcd[i] = gcd_list(num)

print(max(gcd))

Fixed submission:
# 最大公約数
def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a


n = int(input())
A = list(map(int, input().split()))

L = [0 for _ in range(n)]
R = [0 for _ in range(n)]
L[0] = A[0]
R[-1] = A[-1]

for i in range(1, n):
    L[i] = gcd(L[i-1], A[i])
    R[n - i - 1] = gcd(R[n - i], A[n - i - 1])
ans = 1
for i in range(n):
    if i == 0:
        ans = R[i + 1]
    elif i == n-1:
        ans = max(ans, L[i-1])
    else:
        ans = max(ans, gcd(L[i - 1], R[i+1]))

print(ans)

Buggy python submission (verdict: Runtime Error):
import math
from functools import reduce


def gcd_list(numbers):
    return reduce(math.gcd, numbers)


n = int(input())
num_list = list(map(int,input().split()))
gcd = [1 for _ in range(n-1)]
for i in range(n-1):
    num = num_list[:i] + num_list[(i + 1):]
    gcd[i] = gcd_list(num)

print(max(gcd))

Fixed submission:
# 最大公約数
def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a


n = int(input())
A = list(map(int, input().split()))

L = [0 for _ in range(n)]
R = [0 for _ in range(n)]
L[0] = A[0]
R[-1] = A[-1]

for i in range(1, n):
    L[i] = gcd(L[i-1], A[i])
    R[n - i - 1] = gcd(R[n - i], A[n - i - 1])
ans = 1
for i in range(n):
    if i == 0:
        ans = R[i + 1]
    elif i == n-1:
        ans = max(ans, L[i-1])
    else:
        ans = max(ans, gcd(L[i - 1], R[i+1]))

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n, q = map(int, input().split())  # n:文字数，q:問題数
s = list(input())  # 文字列
l = [list(map(int, input().split())) for _ in range(q)]  # 問題
cnt = [0] * q  # cnt list
for i in range(q):
    list = s[l[i][0] - 1:l[i][1]]  # 考えるリスト
    cnt[i] = 0
    for j in range(len(list) - 1):
        if list[j] == 'A' and list[j + 1] == 'C':
            cnt[i] += 1
for k in range(q):
    print(cnt[k])

Fixed submission:
n, q = map(int, input().split())  # n:num of string，q:num of question
s = input()  # string
cnt = [0] * n  # cnt list of 'AC'

for i in range(n-1):
    if s[i: i + 2] == 'AC':
        cnt[i + 1] += 1

for i in range(1, n):
    cnt[i] += cnt[i - 1]  # 累積和

for i in range(q):
    l, r = map(int, input().split())  # question
    l, r = l - 1, r - 1
    print(cnt[r] - cnt[l])
Buggy python submission (verdict: Runtime Error):
def rec(i):
    if dp[i] < INF:
        return dp[i]
    if i == 0:
        return 0
    dp[i] = min(dp[i], rec(i-1) + abs(h[i] - h[i - 1]))
    if i > 1:
        dp[i] = min(dp[i], rec(i-2) + abs(h[i] - h[i - 2]))
    return dp[i]


INF = float('inf')
dp = [INF] * (10 ** 5 + 10)
h = [0] * (10 ** 4 + 10)

N = int(input())
h = list(map(int, input().split())) + h

print(rec(N-1))



Fixed submission:
n = int(input())
h = list(map(int, input().split()))
INF = float('inf')
dp = [INF] * (1 + 10 ** 5)
dp[0] = 0
for i in range(n):
    dp[i] = min(dp[i], dp[i - 1] + abs(h[i] - h[i - 1]))
    if i < 2:
        continue
    dp[i] = min(dp[i], dp[i - 2] + abs(h[i] - h[i - 2]))
print(dp[n-1])
Buggy python submission (verdict: Runtime Error):
INF = float('inf')
dp = [INF] * (10**5 + 10)
dp[0] = 0
h = [0] * (10 ** 4)
N, K = map(int, input().split())
h = list(map(int, input().split())) + h
for i in range(N+1):
    for k in range(1, K+1):
        dp[i+k] = min(dp[i+k], dp[i] + abs(h[i] - h[i+k]))
print(dp[N-1])


Fixed submission:
n, k = map(int, input().split())
h = list(map(int, input().split()))
INF = float('inf')
dp = [INF] * (1 + 10 ** 5)
dp[0] = 0
for i in range(n):
    for j in range(1, k + 1):
        if i - j < 0:
            continue
        dp[i] = min(dp[i], dp[i - j] + abs(h[i] - h[i - j]))
print(dp[n-1])

Buggy python submission (verdict: Runtime Error):
INF = float('inf')
dp = [INF] * (10**5 + 10)
dp[0] = 0
h = [0] * (10 ** 4)
N, K = map(int, input().split())
h = list(map(int, input().split())) + h
for i in range(N):
    for k in range(1, K+1):
        dp[i+k] = min(dp[i+k], dp[i] + abs(h[i] - h[i+k]))
print(dp[N-1])


Fixed submission:
n, k = map(int, input().split())
h = list(map(int, input().split()))
INF = float('inf')
dp = [INF] * (1 + 10 ** 5)
dp[0] = 0
for i in range(n):
    for j in range(1, k + 1):
        if i - j < 0:
            continue
        dp[i] = min(dp[i], dp[i - j] + abs(h[i] - h[i - j]))
print(dp[n-1])

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


Fixed submission:
n, k = map(int, input().split())
h = list(map(int, input().split()))
INF = float('inf')
dp = [INF] * (1 + 10 ** 5)
dp[0] = 0
for i in range(n):
    for j in range(1, k + 1):
        if i - j < 0:
            continue
        dp[i] = min(dp[i], dp[i - j] + abs(h[i] - h[i - j]))
print(dp[n-1])

Buggy python submission (verdict: Time Limit Exceeded):
n, k = map(int, input().split())
h = list(map(int, input().split()))
INF = float('inf')
dp = [INF] * (1 + 10 ** 5)
dp[0] = 0
for i in range(n):
    for j in range(k + 1):
        if i - j < 0:continue
        dp[i] = min(dp[i], dp[i - j] + abs(h[i] - h[i - j]))
print(dp[n-1])

Fixed submission:
n, k = map(int, input().split())
h = list(map(int, input().split()))
INF = float('inf')
dp = [INF] * (1 + 10 ** 5)
dp[0] = 0
for i in range(n):
    for j in range(1, k + 1):
        if i - j < 0:
            continue
        dp[i] = min(dp[i], dp[i - j] + abs(h[i] - h[i - j]))
print(dp[n-1])
Buggy python submission (verdict: Time Limit Exceeded):
N, W = map(int, input().split())
w = [0 for _ in range(N)]
v = [0 for _ in range(N)]
for i in range(N):
    w[i], v[i] = map(int, input().split())
# print(w)
# print(v)
dp = [[0 for _ in range(W+1)] for _ in range(N+1)]
# print(dp)
# dp loop
for i in range(N):
    for sum_w in range(W+1):
        if sum_w - w[i] >= 0:
            dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w - w[i]] + v[i])
        dp[i + 1][sum_w] = max(dp[i + 1][sum_w], dp[i][sum_w])
# print(dp)
print(dp[N][W])

Fixed submission:
N, W = map(int, input().split())
w = [0 for _ in range(N)]
v = [0 for _ in range(N)]
for i in range(N):
    w[i], v[i] = map(int, input().split())
# print(w)
# print(v)
dp = [[0 for _ in range(W+1)] for _ in range(N+1)]
# print(dp)
# dp loop
for i in range(N):
    for sum_w in range(W+1):
        if sum_w - w[i] >= 0:
            dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w - w[i]] + v[i])
        dp[i + 1][sum_w] = max(dp[i + 1][sum_w], dp[i][sum_w])
# print(dp)
print(dp[N][W])
Buggy python submission (verdict: Runtime Error):
N, M = map(int, input().split())
arr = [0 for _ in range(M)]
for i in range(M):
    p, y = map(int, input().split())
    arr[i] = [p, y, i]

arr.sort(key=lambda x: x[1])

arr[0][1] = 1
P_cnt = [1 for _ in range(10 ** 5)]
ans_list = [0] * M
for p, y, i in arr:
    ans_list[i] = [str(p).zfill(6) + str(P_cnt[p]).zfill(6), i]
    P_cnt[p] += 1

ans_list.sort(key=lambda x: x[1])
for i in range(M):
    print(ans_list[i][0])

Fixed submission:
N, M = map(int, input().split())
arr = [0 for _ in range(M)]
for i in range(M):
    p, y = map(int, input().split())
    arr[i] = [p, y, i]

arr.sort(key=lambda x: x[1])

arr[0][1] = 1
P_cnt = [1 for _ in range(10 ** 6)]
ans_list = [0] * M
for p, y, i in arr:
    ans_list[i] = [str(p).zfill(6) + str(P_cnt[p]).zfill(6), i]
    P_cnt[p] += 1

ans_list.sort(key=lambda x: x[1])
for i in range(M):
    print(ans_list[i][0])
Buggy python submission (verdict: Runtime Error):
from collections import deque


max_n = 11000
dp = [-1] * max_n  # -1を未探索とする
dp[0] = 0  # 初期条件の設定
n = int(input())
que = deque([])
que.append(dp[0])
while que:
    v = que.popleft()
    pow = 1
    while v + pow <= n:
        if dp[v + pow] == -1:
            dp[v + pow] = dp[v] + 1
            que.append(v + pow)
        pow *= 6
    pow = 1
    while v + pow <= n:
        if dp[v + pow] == -1:
            dp[v + pow] = dp[v] + 1
            que.append(v + pow)
        pow *= 9
# print(dp)
print(dp[n])


Fixed submission:
n = int(input())
dp = [0 for _ in range(n+1)]
for i in range(1, n+1):  # iは金額
    dp[i] = i  # 初期化
    power = 1  # 累乗を初期化
    while power <= i:  # 累乗より小さい値の時はループに入る
        dp[i] = min(dp[i], dp[i - power] + 1)  # 漸化式
        power *= 6  # 6の累乗を更新
    power = 1  # 累乗を初期化
    while power <= i:  # 累乗より小さい時はループい入る
        dp[i] = min(dp[i], dp[i - power] + 1)  # 漸化式
        power *= 9  # 9の累乗を更新
print(dp[n])
Buggy python submission (verdict: Time Limit Exceeded):
s = input()
K = int(input())
l = []
if len(s) == 1:
    print(s)
    exit()
for i in range(len(s)):
    for j in range(i, len(s)):
        d = s[i:j+1]
        l.append(d)
l = list(set(l))
l.sort()
print(l[K-1])

Fixed submission:
s = input()
K = int(input())
l = []
if len(s) == 1:
    print(s)
    exit()
for i in range(len(s)):
    for j in range(i, len(s)):
        d = s[i:j+1]
        l.append(d)
        if len(d) >= K:
            break
l = list(set(l))
l.sort()
print(l[K-1])

Buggy python submission (verdict: Runtime Error):
s = input()
K = int(input())
l = []
if len(s) == 1:
    print(s)
    exit()
for i in range(len(s) - 1):
    for j in range(i, len(s)):
        d = s[i:j+1]
        l.append(d)
l = list(set(l))
l.sort()
print(l[K-1])

Fixed submission:
s = input()
K = int(input())
l = []
if len(s) == 1:
    print(s)
    exit()
for i in range(len(s)):
    for j in range(i, len(s)):
        d = s[i:j+1]
        l.append(d)
        if len(d) >= K:
            break
l = list(set(l))
l.sort()
print(l[K-1])
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
X = list(map(int, input().split()))
for i in range(n):
    if i !=0 and i != n-1:
        l = X[:i] + X[i+1:]
    elif i == 0:
        l = X[1:]
    else:
        l = X[:n-1]
    l.sort()
    print(l[n // 2 - 1])


Fixed submission:
n = int(input())
X = list(map(int, input().split()))
X_mid = sorted(X)[n//2 - 1: n//2 + 1]

for i in X:
    print(X_mid[i <= X_mid[0]])  # Falseなら1、Trueなら0
Buggy python submission (verdict: Runtime Error):
from heapq import heappush, heappop
from itertools import permutations, accumulate, combinations
from math import pi, gcd, ceil, floor
import numpy as np
from collections import defaultdict, deque
from operator import itemgetter
from bisect import bisect_left, bisect_right, insort_left, insort_right
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10 ** 6)
# MOD = 10 ** 9 + 7
# INF = float("inf")



def main():
    n = int(input())
    print(n // 3)

if __name__ == '__main__':
    main()

Fixed submission:
n = int(input())
print(n//3)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

INF = float("inf")


class Acc2D:
    def __init__(self, grid):
        self.h, self.w = len(grid), len(grid[0])
        self.acc2D = self._build(self.h, self.w, grid)

    def _build(self, h, w, grid):
        ret = [[0] * (w + 1) for _ in range(h + 1)]
        for r in range(h):
            for c in range(w):
                ret[r + 1][c + 1] = ret[r][c + 1] + ret[r + 1][c] - ret[r][c] + grid[r][c]
        return ret

    def get(self, r1, r2, c1, c2):
        if r1 < 0:
            r1 = 0
        if r2 >= self.h:
            r2 = self.h
        if c1 < 0:
            c1 = 0
        if c2 >= self.w:
            c2 = self.w
        cnt = self.acc2D
        return cnt[r2][c2] - cnt[r1][c2] - cnt[r2][c1] + cnt[r1][c1]


def main():
    n, k = map(int, input().split())
    g = [[0] * (2 * k) for _ in range(2 * k)]
    for _ in range(n):
        x, y, c = input().split()
        x = int(x) % (2 * k)
        y = int(y) % (2 * k)
        if c == 'B':
            y = (y + k) % (2 * k)
        g[y][x] += 1
    acc2d = Acc2D(g)
    ans = 0
    for r in range(k):
        for c in range(k):
            tmp = acc2d.get(0, r, 0, c)
            tmp += acc2d.get(0, r, c + k, c + k * 2)
            tmp += acc2d.get(r, r + k, c, c + k)
            tmp += acc2d.get(r + k, r + k * 2, 0, c)
            tmp += acc2d.get(r + k, r + k * 2, c + k, c + k * 2)
            ans = max(ans, tmp, n - tmp)
    print(ans)


if __name__ == '__main__':
    main()


Fixed submission:
import sys
input = sys.stdin.readline
INF = float("inf")


class Acc2D:
    def __init__(self, grid):
        self.h, self.w = len(grid), len(grid[0])
        self.acc2D = self._build(self.h, self.w, grid)

    def _build(self, h, w, grid):
        ret = [[0] * (w + 1) for _ in range(h + 1)]
        for r in range(h):
            for c in range(w):
                ret[r + 1][c + 1] = ret[r][c + 1] + ret[r + 1][c] - ret[r][c] + grid[r][c]
        return ret

    def get(self, r1, r2, c1, c2):
        if r1 < 0:
            r1 = 0
        if r2 >= self.h:
            r2 = self.h
        if c1 < 0:
            c1 = 0
        if c2 >= self.w:
            c2 = self.w
        cnt = self.acc2D
        return cnt[r2][c2] - cnt[r1][c2] - cnt[r2][c1] + cnt[r1][c1]


def main():
    n, k = map(int, input().split())
    g = [[0] * (2 * k) for _ in range(2 * k)]
    for _ in range(n):
        x, y, c = input().split()
        x = int(x) % (2 * k)
        y = int(y) % (2 * k)
        if c == 'B':
            y = (y + k) % (2 * k)
        g[y][x] += 1
    acc2d = Acc2D(g)
    ans = 0
    for r in range(k):
        for c in range(k):
            tmp = acc2d.get(0, r, 0, c)
            tmp += acc2d.get(0, r, c + k, c + k * 2)
            tmp += acc2d.get(r, r + k, c, c + k)
            tmp += acc2d.get(r + k, r + k * 2, 0, c)
            tmp += acc2d.get(r + k, r + k * 2, c + k, c + k * 2)
            ans = max(ans, tmp, n - tmp)
    print(ans)


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
def IsPrime(n):
    if n == 2:
        return True
    if n < 2 or n % 2 == 0:
        return False
    for i in range(3, int(n ** 0.5 + 1), 2):
        if n % i == 0:
            return False
    return True


n = int(input())
q = [list(map(int, input().split())) for _ in range(n)]
for i in range(n):
    l, r = q[i]
    cnt = 0
    for j in range(l, r + 1, 2):
        if IsPrime(j) and IsPrime((j + 1) // 2):
            cnt += 1
    print(cnt)


Fixed submission:
lim = 10 ** 5

primes = [True] * (lim + 1)
primes[0], primes[1] = False, False
for i in range(2, int(lim ** 0.5) + 1):
    if primes[i]:
        for j in range(i * 2, lim, i):
            primes[j] = False

like = [False] * (lim + 1)
for i in range(1, lim + 1):
    if primes[i] and primes[(i + 1) // 2]:
        like[i] = True

cumsum = [0] * (lim + 1)
for i in range(1, lim + 1):
    if like[i]:
        cumsum[i] = cumsum[i - 1] + 1
    else:
        cumsum[i] = cumsum[i - 1]

n = int(input())
q = [list(map(int, input().split())) for _ in range(n)]
for i in range(n):
    l, r = q[i]
    ans = cumsum[r] - cumsum[l - 1]
    print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = list(map(int, input().split()))
b = list(set(a))

ans = 0
for i in range(len(b)):
    if a.count(b[i]) > b[i]:
        ans += a.count(b[i]) - b[i]
    elif a.count(b[i]) < b[i]:
        ans += a.count(b[i])
print(ans)

Fixed submission:
n = int(input())
a = list(map(int, input().split()))
n = len(a)
a.sort()
a.append(-1)
ans = 0
i = 0
while i < n:
    cnt = 1
    while a[i] == a[i+1]:
        cnt += 1
        i += 1
        if i == len(a)-1:
            break
    if cnt > a[i]:
        ans += cnt - a[i]
    elif cnt < a[i]:
        ans += cnt
    i += 1
print(ans)