Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
N , K = map(int,input().split())
S = input()

if S[K] == 'A' :
    S[K] = 'a'
if S[K] == 'B' :
    S[K] = 'b'
if S[K] == 'C' :
    S[K] = 'c'

print(S)

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

ans = S[:K-1] + S[K-1].replace('A','a').replace('B','b').replace('C','c') + S[K:]

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque

N , M = map(int,input().split())

edge = [[] for _ in range(N)]

for _ in range(M) :
    x , y , z = map(int,input().split())

    edge[x-1].append(y-1)
    edge[y-1].append(x-1)

check = [False] * N

q = deque([0])
count = 1 # 連結成分の数

while True:
    while q :
        current = q.popleft()

        if not check[current] :
            check[current] = True

            for n in edge[current] :
                if not check[n] :
                    q.append(n)

    for v , status in enumerate(check) :
        if(not status) :
            q = deque([v])
            count += 1
            break
    else :
        break

print(count)




Fixed submission:
from collections import deque

N , M = map(int,input().split())

checked = [False] * N

edge = [ [] for _ in range(N) ]

for _ in range(M) :
    x , y , z = map(int,input().split())
    edge[x - 1].append(y-1)
    edge[y - 1].append(x-1)

component = 0

for c , check in enumerate(checked) :
    if check :
        continue

    stack = deque([c])
    component += 1

    while stack :
        current = stack.pop()

        if checked[current] :
            continue

        checked[current] = True
        for v in edge[current] :
            if not checked[v] :
                stack.append(v)

print(component)
Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque

H, W = map(int, input().split())
A = [input() for _ in range(H)]

que = deque([])
for h in range(H):
    for w in range(W):
        if A[h][w] == '#':
            que.append((h, w, 0))

minDist = [[10**10] * W for _ in range(H)]
while que:
    h, w, d = que.popleft()

    if minDist[h][w] <= d:
        continue
    minDist[h][w] = d

    for dh, dw in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
        if 0 <= dh + h < H and 0 <= dw + w < W:
            que.append((dh + h, dw + w, d + 1))

ans = max(max(d) for d in minDist)
print(ans)


Fixed submission:
from collections import deque

H, W = map(int, input().split())
A = [input() for _ in range(H)]

minDist = [[10**10] * W for _ in range(H)]
que = deque([])
for h in range(H):
    for w in range(W):
        if A[h][w] == '#':
            que.append((h, w, 0))
            minDist[h][w] = 0

while que:
    h, w, d = que.popleft()

    if minDist[h][w] < d:
        continue
    minDist[h][w] = d

    for dh, dw in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
        if 0 <= dh + h < H and 0 <= dw + w < W:
            if minDist[dh + h][dw + w] > d + 1:
                que.append((dh + h, dw + w, d + 1))
                minDist[dh + h][dw + w] = d + 1

ans = max(max(d) for d in minDist)
print(ans)
Buggy python submission (verdict: Runtime Error):
from collections import deque
import sys
input = sys.stdin.buffer.readline

N = int(input())
edges = [[] for _ in range(N)]

for _ in range(N - 1):
    fr, to = map(lambda a: int(a) - 1, input().split())
    edges[fr].append(to)
    edges[to].append(fr)

def calcDist(fr):
    minDist = [10**18] * N
    que = deque([(fr, 0)])

    while que:
        now, dist = que.pop()

        if minDist[now] < dist:
            continue
        minDist[now] = dist

        for to in edges[now]:
            if minDist[to] > dist + 1:
                minDist[to] = dist + 1
                que.append((to, dist + 1))

    return minDist

D0 = calcDist(0)
R = max(calcDist(D0.index(max(D0)))) + 1

canFirstWin = [False] * (R + 1)
canFirstWin[1] = True
canFirstWin[2] = False

for i in range(3, R + 1):
    canFirstWin[i] = not(canFirstWin[i - 1] and canFirstWin[i - 2])

print('First' if canFirstWin[R] else 'Second')


Fixed submission:
from collections import deque
import sys
input = sys.stdin.buffer.readline

N = int(input())
edges = [[] for _ in range(N)]

for _ in range(N - 1):
    fr, to = map(lambda a: int(a) - 1, input().split())
    edges[fr].append(to)
    edges[to].append(fr)

def calcDist(fr):
    minDist = [10**18] * N
    que = deque([(fr, 0)])

    while que:
        now, dist = que.pop()

        if minDist[now] < dist:
            continue
        minDist[now] = dist

        for to in edges[now]:
            if minDist[to] > dist + 1:
                minDist[to] = dist + 1
                que.append((to, dist + 1))

    return minDist

D0 = calcDist(0)
R = max(calcDist(D0.index(max(D0)))) + 1

print('Second' if R % 3 == 2 else 'First')
Buggy python submission (verdict: Runtime Error):
import math

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

ans = 1

if N == 1 :
    ans = A[0]
else :
    for i in range(N) :
        B = A[:i-1] + A[i:] # i番目を除く
        stat = B[0]
        for b in B[1:] :
            stat = math.gcd(stat,b)
            if stat == 1:
                break
        else :
            ans = max(ans,stat)

print(ans)


Fixed submission:
def gcd(a,b) :
    r = a % b
    if r == 0 :
        return b
    else :
        return gcd(b,r)

N = int(input())

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

L = [0] * N
R = [0] * N

for i in range(N) :  # iより左(右)
    if i == 0 :
        L[i] = A[i]
        R[-i-1] = A[-i-1]
    else :
        L[i] = gcd(L[i-1], A[i-1])
        R[-i-1] = gcd(R[-i],A[-i])

ans = 1

for i in range(N) :
    if i == 0 :
        new = R[i]
    elif i == N-1 :
        new = L[i]
    else :
        new = gcd(L[i],R[i])
    if ans < new :
        ans = new

print(ans)

Buggy python submission (verdict: Runtime Error):
import math

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

ans = 1

if N == 1 :
    ans = A[0]
else :
    for i in range(N) :
        B = A[:i-1] + A[i:] # i番目を除く
        gcd = B[0]
        for b in B[1:] :
            gcd = math.gcd(gcd,b)
            if gcd == 1:
                break
        else :
            ans = max(ans,gcd)

print(ans)


Fixed submission:
def gcd(a,b) :
    r = a % b
    if r == 0 :
        return b
    else :
        return gcd(b,r)

N = int(input())

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

L = [0] * N
R = [0] * N

for i in range(N) :  # iより左(右)
    if i == 0 :
        L[i] = A[i]
        R[-i-1] = A[-i-1]
    else :
        L[i] = gcd(L[i-1], A[i-1])
        R[-i-1] = gcd(R[-i],A[-i])

ans = 1

for i in range(N) :
    if i == 0 :
        new = R[i]
    elif i == N-1 :
        new = L[i]
    else :
        new = gcd(L[i],R[i])
    if ans < new :
        ans = new

print(ans)

Buggy python submission (verdict: Runtime Error):
import math

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

ans = 1

for i in range(N) :
    B = A[:i-1] + A[i:]
    gcd = B[0]
    for b in B[1:] :
        gcd = math.gcd(gcd,b)
        if gcd == 1:
            break
    else :
        ans = max(ans,gcd)

print(ans)


Fixed submission:
def gcd(a,b) :
    r = a % b
    if r == 0 :
        return b
    else :
        return gcd(b,r)

N = int(input())

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

L = [0] * N
R = [0] * N

for i in range(N) :  # iより左(右)
    if i == 0 :
        L[i] = A[i]
        R[-i-1] = A[-i-1]
    else :
        L[i] = gcd(L[i-1], A[i-1])
        R[-i-1] = gcd(R[-i],A[-i])

ans = 1

for i in range(N) :
    if i == 0 :
        new = R[i]
    elif i == N-1 :
        new = L[i]
    else :
        new = gcd(L[i],R[i])
    if ans < new :
        ans = new

print(ans)
Buggy python submission (verdict: Runtime Error):
<?php

$s = trim(fgets(STDIN));
$count = [0];

$replace = preg_replace('/[^ACGT]/',',',$s);
$matchs = array_filter(explode(',',$replace));

foreach ($matchs as $m) {
    $count[] = strlen($m);
}

print(max($count) . "\n");

Fixed submission:
S = input()
T = set(list('AGCT'))

ans = 0
for l in range(len(S)):
    for r in range(l + 1, len(S) + 1):
        if set(S[l: r]) <= T:
            ans = max(ans, r - l)

print(ans)
Buggy python submission (verdict: Runtime Error):
import math

A , B , K = map(int,input().split()) # A,B <= 100

k = 0

R = int(max(math.gcd(A,B),1))

for i in range(R,0,-1) :
    if A % i == 0 and B % i == 0 :
        k += 1
        if k >= K :
            print(i)
            break



Fixed submission:
import fractions as fr

A , B , K = map(int,input().split()) # A,B <= 100

k = 0

R = int(max(fr.gcd(A,B),1))

for i in range(R,0,-1) :
    if A % i == 0 and B % i == 0 :
        k += 1
        if k >= K :
            print(i)
            break

Buggy python submission (verdict: Runtime Error):
import math

A , B , K = map(int,input().split()) # A,B <= 100

k = 0

for i in range(math.gcd(A,B),0,-1) :
    if A % i == 0 and B % i == 0 :
        k += 1
        if k >= K :
            print(i)
            break



Fixed submission:
import fractions as fr

A , B , K = map(int,input().split()) # A,B <= 100

k = 0

R = int(max(fr.gcd(A,B),1))

for i in range(R,0,-1) :
    if A % i == 0 and B % i == 0 :
        k += 1
        if k >= K :
            print(i)
            break
Buggy python submission (verdict: Time Limit Exceeded):
L = int(input())
A = [int(input()) for _ in range(L)]

def cost(k, a):
    if a % 2:
        a = 1
    elif a >= 2:
        a = 2

    if k == 0 or k == 4:
        return a

    if k == 1 or k == 3:
        return 2 - a

    return 1 - a % 2

dp = [[10**18] * 5 for _ in range(L + 1)]
dp[0][0] = 0

for i, a in enumerate(A, start=1):
    for j in range(5):
        for k in range(j, 5):
            b = dp[i - 1][j] + cost(k, a)
            if dp[i][k] > b:
                dp[i][k] = b

ans = min(dp[L])
print(ans)

Fixed submission:
L = int(input())
B = [int(input()) for _ in range(L)]

A = []
for b in B:
    if b % 2:
        A.append(1)
    else:
        A.append(0 if b == 0 else 2)

dpLBack = [10**10] * (L + 1)
dpLBack[0] = 0
cnt = 0
for i, a in enumerate(A, start=1):
    cnt += B[i - 1]
    dpLBack[i] = min(dpLBack[i - 1] + 2 - a, cnt)

dpL = [10**10] * (L + 1)
dpL[0] = 0
cnt = 0
for i, a in enumerate(A, start=1):
    cnt += B[i - 1]
    dpL[i] = min(dpL[i - 1] + (a != 1), dpLBack[i - 1] + (a == 0), cnt)

dpRBack = [10**10] * (L + 1)
dpRBack[0] = 0
cnt = 0
for i, a in enumerate(A[:: -1], start=1):
    cnt += B[-i]
    dpRBack[i] = min(dpRBack[i - 1] + 2 - a, cnt)

dpR = [10**10] * (L + 1)
dpR[0] = 0
cnt = 0
for i, a in enumerate(A[:: -1], start=1):
    cnt += B[-i]
    dpR[i] = min(dpR[i - 1] + (a != 1), dpRBack[i - 1] + (a == 0), cnt)

dpR = dpR[:: -1]
dpRBack = dpRBack[::-1]

ans = min(dpL[L], dpR[0])
for mid in range(L + 1):
    ans = min(ans, dpL[mid] + dpRBack[mid], dpLBack[mid] + dpR[mid], dpLBack[mid] + dpRBack[mid])

print(ans)
Buggy python submission (verdict: Runtime Error):
N = int(input())
H = list(map(int, input().split()))
ans = 0

while max(H) > 0:
    grp = [[]]
    for i, h in enumerate(H):
        if h == 0:
            if len(grp[-1]) > 0:
                grp.append([])
        else:
            grp[-1].append((i, h))
    for g in grp:
        mi = min([h for _, h in g])
        ans += mi
        for i, _ in g:
            H[i] -= mi

print(ans)


Fixed submission:
from collections import deque

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

stack = deque([])
prevPoint = -1

for i in range(N) :
    if h[i] == 0 :
        stack.append((prevPoint+1 , i))
        prevPoint = i
    elif i >= N - 1 :
        stack.append((prevPoint+1,N))

ans = 0

while stack :
    start , end = stack.pop()

    if start >= end :
        ans += h[start]
        h[start] = 0
        continue


    minus = min(h[start:end])
    ans += minus

    prevPoint = start - 1
    for i in range(start,end) :
        h[i] -= minus
        if h[i] == 0 :
            stack.append((prevPoint+1,i))
            prevPoint = i
        elif i >= end - 1 :
            stack.append((prevPoint+1,end))

print(ans)
Buggy python submission (verdict: Runtime Error):
from collections import Counter

N, K = map(int, input().split())
TD = [tuple(map(int, input().split())) for _ in range(N)]

TD.sort(reverse=True, key=lambda a: a[1])

A = TD[:K]

B = []
V = set()
for t, d in TD:
    if t in V:
        continue
    B.append((t, d))
    V.add(t)

cntT = Counter([t for t, _ in A])
V = set(cntT.keys())
S = sum([d for _, d in A])
B = [(t, d) for t, d in B if not t in V]

C = []
for t, d in A[::-1]:
    if cntT[t] > 1:
        C.append((t, d))
        cntT[t] -= 1

C = C[::-1]
ans = S + len(V)**2
for t, d in B:
    _, less = C.pop()
    S -= less
    S += d
    V.add(t)
    ans = max(ans, S + len(V)**2)
print(ans)


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

sushi = []

for _ in range(N) :
    t, d = map(int,input().split())
    sushi.append((t,d))

sushi.sort(key=lambda A : A[1], reverse=True)

# 美味しいものから順にK個選ぶ
nowSushi = []
sumTaste = 0
numKind = 0
take = [0] * N  # 種類は高々N

for i in range(K) :
    t, d = sushi[i]
    nowSushi.append((t,d))
    sumTaste += d
    if take[t-1] == 0 :
        numKind += 1
    take[t-1] += 1

addSushi = []  # 種類を増やせる寿司
for i in range(K,N) :
    t, d = sushi[i]
    if take[t-1] > 0 :  # すでに選択済み
        continue
    addSushi.append((t,d))
    take[t-1] += 1

ans = sumTaste + numKind**2
L = len(addSushi)
changeCount = 0

while nowSushi :
    removeSushiT, removeSushiD = nowSushi.pop()
    if take[removeSushiT-1] <= 1 :
        continue
    if changeCount >= L :
        break

    addSushiT, addSushiD = addSushi[changeCount]
    changeCount += 1

    sumTaste = sumTaste - removeSushiD + addSushiD
    numKind = numKind + 1

    if (sumTaste + numKind**2) > ans :
        ans = sumTaste + numKind**2

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
import heapq
from operator import itemgetter
from collections import deque, defaultdict
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
MOD = 10**9 + 7

def sol():
    N, W = map(int, input().split())
    items = [0] * N

    for i in range(N):
        w, v = map(int, input().split())
        items[i] = (v, w)

    dp = [0] * (W + 1)

    for value, weight in items:
        for w in range(W + 1)[:: -1]:
            if w - weight >= 0:
                dp[w] = max(dp[w], dp[w - weight] + value)

    print(dp[W])

sol()

Fixed submission:
import sys
import heapq
from operator import itemgetter
from collections import deque, defaultdict
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
MOD = 10**9 + 7

def sol():
    N, W = map(int, input().split())
    items = [0] * N

    for i in range(N):
        w, v = map(int, input().split())
        items[i] = (v, w)

    dp = [0] * (W + 1)

    for value, weight in items:
        for w in range(W + 1)[:: -1]:
            if w - weight >= 0:
                dp[w] = max(dp[w], dp[w - weight] + value)

    print(dp[W])

sol()
Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int, input().split())
A = list(map(int, input().split()))
MOD = 10**9 + 7

dp = [0] * (K + 1)
dp[0] = 1

for i, a in enumerate(A, start=1):
    accDp = [0] * (K + 2)
    for k in range(1, K + 2):
        accDp[k] = accDp[k - 1] + dp[k - 1]

    for k in range(K + 1):
        dp[k] = (dp[k] + accDp[k] - accDp[max(0, k - a)]) % MOD

print(dp[K] % MOD)


Fixed submission:
N, K = map(int, input().split())
A = list(map(int, input().split()))
MOD = 10**9 + 7

dp = [[0] * (K + 1) for _ in range(N + 1)]  # dp[child][candy] 残りcandy個の場合の数
dp[0][K] = 1

for child in range(1, N + 1):
    sumDp = [0] * (K + 2)
    for i in range(1, K + 2)[:: -1]:
        sumDp[i - 1] += sumDp[i] + dp[child - 1][i - 1]

    for candy in range(K + 1):
        dp[child][candy] = (sumDp[candy] - sumDp[min(K, candy + A[child - 1]) + 1]) % MOD

print(dp[N][0] % MOD)

Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int, input().split())
A = list(map(int, input().split()))
MOD = 10**9 + 7

dp = [0] * (K + 1)
dp[0] = 1

for i, a in enumerate(A, start=1):
    accDp = [0] * (K + 2)
    for k in range(1, K + 2):
        accDp[k] = accDp[k - 1] + dp[k - 1]

    for k in range(K + 1):
        dp[k] += accDp[k] - accDp[max(0, k - a)]

print(dp[K] % MOD)


Fixed submission:
N, K = map(int, input().split())
A = list(map(int, input().split()))
MOD = 10**9 + 7

dp = [[0] * (K + 1) for _ in range(N + 1)]  # dp[child][candy] 残りcandy個の場合の数
dp[0][K] = 1

for child in range(1, N + 1):
    sumDp = [0] * (K + 2)
    for i in range(1, K + 2)[:: -1]:
        sumDp[i - 1] += sumDp[i] + dp[child - 1][i - 1]

    for candy in range(K + 1):
        dp[child][candy] = (sumDp[candy] - sumDp[min(K, candy + A[child - 1]) + 1]) % MOD

print(dp[N][0] % MOD)

Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int, input().split())
A = list(map(int, input().split()))
MOD = 10**9 + 7

dp = [[0] * (K + 1) for _ in range(N + 1)]  # dp[child][candy] 残りcandy個の場合の数
dp[0][K] = 1

for child in range(1, N + 1):
    sumDp = [0] * (K + 2)
    for i in range(1, K + 2)[:: -1]:
        sumDp[i - 1] += sumDp[i] + dp[child - 1][i - 1]

    for candy in range(K + 1):
        dp[child][candy] = (sumDp[candy] - sumDp[min(K, candy + A[child - 1]) + 1]) % MOD

print(dp[N][0] % MOD)

Fixed submission:
N, K = map(int, input().split())
A = list(map(int, input().split()))
MOD = 10**9 + 7

dp = [[0] * (K + 1) for _ in range(N + 1)]  # dp[child][candy] 残りcandy個の場合の数
dp[0][K] = 1

for child in range(1, N + 1):
    sumDp = [0] * (K + 2)
    for i in range(1, K + 2)[:: -1]:
        sumDp[i - 1] += sumDp[i] + dp[child - 1][i - 1]

    for candy in range(K + 1):
        dp[child][candy] = (sumDp[candy] - sumDp[min(K, candy + A[child - 1]) + 1]) % MOD

print(dp[N][0] % MOD)
Buggy python submission (verdict: Time Limit Exceeded):
from collections import Counter

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

maxPow = (1 << (max(A) * 2).bit_length())
cntA = Counter(A)

ans = 0
while maxPow > 0:
    for a in A:
        if maxPow - a == a:
            if cntA[a] >= 2:
                ans += cntA[a] // 2
                cntA[a] %= 2
        elif cntA[a] > 0 and cntA[maxPow - a] > 0:
            ans += 1
            cntA[a] -= 1
            cntA[maxPow - a] -= 1
    maxPow //= 2

print(ans)

Fixed submission:
from collections import Counter

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

maxPow = (1 << (max(A) * 2).bit_length())
cntA = Counter(A)

ans = 0
while maxPow > 0:
    for a in A:
        if maxPow - a == a:
            if cntA[a] >= 2:
                ans += cntA[a] // 2
                cntA[a] %= 2
        elif cntA[a] > 0 and cntA[maxPow - a] > 0:
            ans += 1
            cntA[a] -= 1
            cntA[maxPow - a] -= 1
    maxPow //= 2

print(ans)
Buggy python submission (verdict: Runtime Error):
D = int(intput())

if D == 25 :
  print('Christmas')
elif D == 24 :
  print('Christmas Eve')
elif D == 23 :
  print('Christmas Eve Eve')
elif D == 22 :
  print('Christmas Eve Eve Eve')


Fixed submission:
D = int(input())

if D == 25 :
  print('Christmas')
elif D == 24 :
  print('Christmas Eve')
elif D == 23 :
  print('Christmas Eve Eve')
elif D == 22 :
  print('Christmas Eve Eve Eve')
Buggy python submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10 ** 7)

N, X = map(int, input().split())

if X < N :
    print(0)
else :
    burger = [-1] * (N + 1)
    def makeBurger(level) :
        if level == 0 :
            return '1'
        if burger[level] == -1 :
            middle = makeBurger(level - 1)
            burger[level - 1] = middle
        else :
            middle = burger[level - 1]
        return '0' + middle + '1' + middle + '0'
    ans = makeBurger(N)[:X]
    print(ans.count('1'))

Fixed submission:
import sys
sys.setrecursionlimit(10 ** 7)

N, X = map(int, input().split())

if X < N :
    print(0)
else :
    pat = [0] * (N + 1)  # パティ数
    ban = [0] * (N + 1)  # バンズ数
    pat[0] = 1
    for i in range(1, N + 1) :
        pat[i] = 2 * pat[i - 1] + 1
        ban[i] = 2 * ban[i - 1] + 2
    def sol(level, height) :
        if height <= 0 :
            return 0
        if level == 0 :
            return 1
        if height <= 1 :
            return 0
        if height < pat[level - 1] + ban[level - 1] :
            return sol(level - 1, height - 1)
        if height == pat[level - 1] + ban[level - 1] + 1 :
            return pat[level - 1]
        if height == pat[level - 1] + ban[level - 1] + 2 :
            return pat[level - 1] + 1
        return pat[level - 1] + 1 + sol(level - 1, height - (pat[level - 1] + ban[level - 1] + 2))

    ans = sol(N, X)
    print(ans)

Buggy python submission (verdict: Runtime Error):
N, X = map(int, input().split())

if X < N :
    print(0)
else :
    burger = [-1] * (N + 1)
    def makeBurger(level) :
        if level == 0 :
            return '1'
        if burger[level] == -1 :
            middle = makeBurger(level - 1)
            burger[level - 1] = middle
        else :
            middle = burger[level - 1]
        return '0' + middle + '1' + middle + '0'
    ans = makeBurger(N)[:X]
    print(ans.count('1'))

Fixed submission:
import sys
sys.setrecursionlimit(10 ** 7)

N, X = map(int, input().split())

if X < N :
    print(0)
else :
    pat = [0] * (N + 1)  # パティ数
    ban = [0] * (N + 1)  # バンズ数
    pat[0] = 1
    for i in range(1, N + 1) :
        pat[i] = 2 * pat[i - 1] + 1
        ban[i] = 2 * ban[i - 1] + 2
    def sol(level, height) :
        if height <= 0 :
            return 0
        if level == 0 :
            return 1
        if height <= 1 :
            return 0
        if height < pat[level - 1] + ban[level - 1] :
            return sol(level - 1, height - 1)
        if height == pat[level - 1] + ban[level - 1] + 1 :
            return pat[level - 1]
        if height == pat[level - 1] + ban[level - 1] + 2 :
            return pat[level - 1] + 1
        return pat[level - 1] + 1 + sol(level - 1, height - (pat[level - 1] + ban[level - 1] + 2))

    ans = sol(N, X)
    print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque

N, M = map(int, input().split())

divisor = deque([])

for i in range(2, M + 1) :
    if M % i == 0 :
        divisor.append(i)
    if i * N > M :
        break

while divisor :
    div = divisor.pop()
    if M // div >= N :
        print(div)
        break
else :
    print(1)


Fixed submission:
N, M = map(int, input().split())

def divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors.sort(reverse=True)
    return divisors

div = divisors(M)

for d in div :
    if M >= N * d :
        print(d)
        break
Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np

N, M, K = map(int, input().split())

LR = np.zeros(shape=(N + 1, N + 1), dtype=np.int32)
for _ in range(M):
    L, R = map(int, input().split())
    LR[L, R] += 1

np.cumsum(LR, axis=0, out=LR)
np.cumsum(LR, axis=1, out=LR)

P, Q = np.array([list(map(int, input().split())) for _ in range(K)], dtype=np.int32).T

P -= 1
ans = LR[Q, Q] - LR[P, Q] - LR[Q, P] + LR[P, P]
print(*ans, sep='\n')


Fixed submission:
N, M, Q = map(int, input().split())

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

for _ in range(M) :
    L, R = map(int, input().split())
    train[L][R] += 1

que = []
for _ in range(Q) :
    p, q = map(int, input().split())
    que.append((p, q))

# 累積和
S = [[0 for _ in range(N+1)] for _ in range(N+1)]  # ゼロパディング

for l in range(1, N+1) :
    for r in range(1, N+1) :
        S[l][r] = S[l-1][r] + S[l][r-1] - S[l-1][r-1] + train[l][r]

for p, q in que :
    ans = S[q][q] - S[p-1][q] - S[q][p-1] + S[p-1][p-1]
    print(ans)