Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
import math
T = int(input())
for i in range(T):
    A,B,C,D = map(int,input().split())
    if B > D:
        print('No')
    elif A < B:
        print('No')
    elif C + 1 >= B:
        print('Yes')
    else:
        r = (A-C)%math.gcd(B,C)
        if C + r >= B:
            print('Yes')
        else:
            print('No')

Fixed submission:
def gcd(a, b):
    while b:
        a, b = b, a % b
    return(a)

T = int(input())
for i in range(T):
    A,B,C,D = map(int,input().split())
    if B > D:
        print('No')
    elif A < B:
        print('No')
    elif C + 1 >= B:
        print('Yes')
    else:
        q = gcd(B,D)
        r = (A-C)%q
        if r == 0:
            r = q
        if C + r >= B:
            print('Yes')
        else:
            print('No')
Buggy python submission (verdict: Runtime Error):
n, m , d = map(int, input().split())
A = [0]*n
for i in range(1,m):
    B = A
    A = [0]*n
    for j in range(n):
        for k in range(n):
            if k + 1 - d >= 0 and k + 1 + d <= n:
                A[j] = B[j] + 2
            elif k + 1 - d >= 0 and k + 1 + d > n:
                A[j] = B[j] + 1
            elif k + 1 - d < 0 and k + 1 + d <= n:
                A[j] = B[j] + 1
            if k + 1 - d >= 0 and k + 1 + d <= n:
                A[j] += 2
            elif k + 1 - d >= 0 and k + 1 + d > n:
                A[j] += 1
            elif k + 1 - d < 0 and k + 1 + d <= n:
                A[j] += 1
print(sum(A)/(n**m))

Fixed submission:
n, m, d = map(int, input().split())
if d == 0:
    C = n
else:
    C = 2*(n-d)
print(C*(m-1)/n**2)

Buggy python submission (verdict: Runtime Error):
n, m , d = map(int, input().split())
A = [0]*n
for i in range(1,m):
    B = A
    A = [0]*n
    for j in range(n):
        for k in range(n):
            if k + 1 - d >= 0 and k + 1 + d <= n:
                A[j] = B[j] + 2
            elif k + 1 - d >= 0 or k + 1 + d > n:
                A[j] = B[j] + 1
            elif k + 1 - d < 0 or k + 1 + d <= n:
                A[j] = B[j] + 1
            if k + 1 - d >= 0 and k + 1 + d <= n:
                A[j] += 2
            elif k + 1 - d >= 0 or k + 1 + d > n:
                A[j] += 1
            elif k + 1 - d < 0 or k + 1 + d <= n:
                A[j] += 1
print(sum(A)/(n**m))

Fixed submission:
n, m, d = map(int, input().split())
if d == 0:
    C = n
else:
    C = 2*(n-d)
print(C*(m-1)/n**2)
Buggy python submission (verdict: Runtime Error):
import heapq
from itertools import accumulate

n, m, s, t = map( int, input().split())

def dijkstra(graph, start):
    dist = [ 10**14 for _ in range(n)]
    dist[start] = 0
    q = [(0,start)]
    while q:
        l, v = heapq.heappop(q)
        if dist[v] < l:
            continue
        for u, d in graph[v].items():
            if dist[u] > l+d:
                dist[u] = l+d
                heapq.heappush(q, (dist[u], u))
    return dist

D_yen = [ dict() for _ in range(n)]
D_snuuk = [ dict() for _ in range(n)]
for _ in range(m):
    u, v, a, b = map( int, input().split())
    u, v = u-1, v-1
    D_yen[u][v] = D_yen[v][u] = a
    D_snuuk[u][v] = D_snuuk[v][u] = b

C_yen = dijkstra(D_yen, s-1)
C_snuuk = dijkstra(D_snuuk, t-1)

ANS = list( accumulate( [y+s for y, s in zip( C_yen, C_snuuk])[::-1], min))
[ print( 10**15 - ANS[i]) for i in range(n-1,-1,-1)]

Fixed submission:
import heapq

n, m, s, t = map( int, input().split())

def dijkstra(graph, start):
    dist = [ 10**14 for _ in range(n)]
    dist[start] = 0
    q = [(0,start)]
    while q:
        l, v = heapq.heappop(q)
        if dist[v] < l:
            continue
        for u, d in graph[v].items():
            if dist[u] > l+d:
                dist[u] = l+d
                heapq.heappush(q, (dist[u], u))
    return dist

D_yen = [ dict() for _ in range(n)]
D_snuuk = [ dict() for _ in range(n)]
for _ in range(m):
    u, v, a, b = map( int, input().split())
    u, v = u-1, v-1
    D_yen[u][v] = D_yen[v][u] = a
    D_snuuk[u][v] = D_snuuk[v][u] = b

C_yen = dijkstra(D_yen, s-1)
C_snuuk = dijkstra(D_snuuk, t-1)
ans = 10**15
ANS = [ 0 for _ in range(n)]
for i in range(n):
    ans = min( ans, C_yen[n-1-i] + C_snuuk[n-1-i])
    ANS[n-1-i] = ans
for i in range(n):
    print(10**15 - ANS[i])
Buggy python submission (verdict: Runtime Error):
from statistics import mean
import math
N = int(input())
*A, = map(int, input().split())
B = [A[i]-i for i in range(N)]
bm = math.median(B)
K = [x - bm for x in B]
KZ = [abs(x) for x in K]
Z = sum(KZ)
for i in range(200):
    C = [abs(x-i+100) for x in K]
    Z = min([sum(C),Z])
print(int(Z))

Fixed submission:
from statistics import median
import math
N = int(input())
*A, = map(int, input().split())
B = [A[i]-i for i in range(N)]
b = median(B)
bm = math.floor(b)
K = [x - bm for x in B]
KZ = [abs(x) for x in K]
Z = sum(KZ)
for i in range(20):
    C = [abs(x-i+10) for x in K]
    Z = min([sum(C),Z])
print(int(Z))

Buggy python submission (verdict: Runtime Error):
from statistics import mean
import math
N = int(input())
*A, = map(int, input().split())
B = [A[i]-i for i in range(N)]
bm = median(B)
K = [x - bm for x in B]
KZ = [abs(x) for x in K]
Z = sum(KZ)
for i in range(200):
    C = [abs(x-i+100) for x in K]
    Z = min([sum(C),Z])
print(int(Z))

Fixed submission:
from statistics import median
import math
N = int(input())
*A, = map(int, input().split())
B = [A[i]-i for i in range(N)]
b = median(B)
bm = math.floor(b)
K = [x - bm for x in B]
KZ = [abs(x) for x in K]
Z = sum(KZ)
for i in range(20):
    C = [abs(x-i+10) for x in K]
    Z = min([sum(C),Z])
print(int(Z))

Buggy python submission (verdict: Time Limit Exceeded):
from statistics import mean
import math
N = int(input())
*A, = map(int, input().split())
B = [A[i]-i for i in range(N)]
b = mean(B)
bm = math.floor(b)
K = [x - bm for x in B]
KZ = [abs(x) for x in K]
Z = sum(KZ)
for i in range(2000):
    C = [abs(x-i+1000) for x in K]
    Z = min([sum(C),Z])
print(int(Z))

Fixed submission:
from statistics import median
import math
N = int(input())
*A, = map(int, input().split())
B = [A[i]-i for i in range(N)]
b = median(B)
bm = math.floor(b)
K = [x - bm for x in B]
KZ = [abs(x) for x in K]
Z = sum(KZ)
for i in range(20):
    C = [abs(x-i+10) for x in K]
    Z = min([sum(C),Z])
print(int(Z))
Buggy python submission (verdict: Runtime Error):
from itertools import accumulate

N = int( input())
A = list( map( int, input().split()))
a, b = 0, 2
ans = 10**9 + 1
S = list(accumulate(A))
for i in range(1,N-1):
    while S[a] < S[i] - S[a+1]:
        a += 1
    b = max(b,i+1)
    while S[b] - S[i] < S[-1] - S[b+1]:
        b += 1
    ans = min( ans, max(S[a], S[i] - S[a], S[b] - S[i], S[-1] - S[b]) - min(S[a], S[i] - S[a], S[b] - S[i], S[-1] - S[b]))
print(ans)

Fixed submission:
from itertools import accumulate

N = int( input())
A = list( map( int, input().split()))
a, b = 0, 2
ans = 10**9 + 1
S = list(accumulate(A))
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[-1] - S[b+1]:
        b += 1
    ans = min( ans, max(S[a], S[i] - S[a], S[b] - S[i], S[-1] - S[b]) - min(S[a], S[i] - S[a], S[b] - S[i], S[-1] - S[b]))
print(ans)

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

def half(T, h):
    b = bisect(T,h)
    if abs(T[b-1]*2 - T[-1] - T[0]) <= abs(T[b]*2 - T[-1] - T[0]):
        return T[b-1] - T[0], T[-1]-T[b-1]
    return T[b] - T[0], T[-1]-T[b]
N = int( input())
A = list( map( int, input().split()))
S = [0] + list( accumulate(A))
ans = 10**9+1
for i in range(2, N-1):
    x, y = half(S[:i+1], S[i]//2)
    z, w = half(S[i:], (S[i] + S[-1])//2)
    m = min(x,y,z,w)
    M = max(x,y,z,w)
    if M-m < ans:
        ans = M-m
print(ans)


Fixed submission:
from itertools import accumulate

N = int( input())
A = list( map( int, input().split()))
a, b = 0, 2
ans = 10**9 + 1
S = list(accumulate(A))
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[-1] - S[b+1]:
        b += 1
    ans = min( ans, max(S[a], S[i] - S[a], S[b] - S[i], S[-1] - S[b]) - min(S[a], S[i] - S[a], S[b] - S[i], S[-1] - S[b]))
print(ans)

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

def half(T, h):
    b = bisect(T,h)
    if abs(T[b-1]*2 - T[-1] - T[0]) <= abs(T[b]*2 - T[-1] - T[0]):
        return T[b-1] - T[0], T[-1]-T[b-1]
    return T[b] - T[0], T[-1]-T[b]
N = int( input())
A = list( map( int, input().split()))
S = [0] + list( accumulate(A))
ans = 10**9+1
for i in range(2, N-1):
    x, y = half(S[:i+1], S[i]//2)
    z, w = half(S[i:], (S[i] + S[-1])//2)
    m = min(x,y,z,w)
    M = max(x,y,z,w)
    if M-m < ans:
        ans = M-m
print(ans)


Fixed submission:
from itertools import accumulate

N = int( input())
A = list( map( int, input().split()))
a, b = 0, 2
ans = 10**9 + 1
S = list(accumulate(A))
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[-1] - S[b+1]:
        b += 1
    ans = min( ans, max(S[a], S[i] - S[a], S[b] - S[i], S[-1] - S[b]) - min(S[a], S[i] - S[a], S[b] - S[i], S[-1] - S[b]))
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
P = [(1,1,1), (1,1,-1), (1,-1,1), (1,-1,-1), (-1,1,1), (-1,1,-1), (-1,-1,1), (-1,-1,-1)]
N, M = map( int, input().split())
X = [0]*N
Y = [0]*N
Z = [0]*N
ans = 0
for i in range(N):
    X[i], Y[i], Z[i] = map( int, input().split())
for i in range(8):
    a, b, c = P[i]
    dp = [0]*(M+1)
    for j in range(N):
        x, y, z = X[j], Y[j], Z[j]
        for k in range(M-1,-1,-1):
            if dp[k+1] < dp[k] + a*x + b*y + c*z:
                dp[k+1] = dp[k] + a*x + b*y + c*z
    ans = max( ans, dp[M])
print(ans)


Fixed submission:
P = [(1,1,1), (1,1,-1), (1,-1,1), (1,-1,-1), (-1,1,1), (-1,1,-1), (-1,-1,1), (-1,-1,-1)]
N, M = map( int, input().split())
X = [0]*N
Y = [0]*N
Z = [0]*N
ans = 0
for i in range(N):
    X[i], Y[i], Z[i] = map( int, input().split())
for i in range(8):
    a, b, c = P[i]
    W = [0]*N
    for j in range(N):
        W[j] = a*X[j] + b*Y[j] + c*Z[j]
    W.sort(key=None, reverse = True)
    ans = max( ans, sum(W[:M]))
print(ans)

Buggy python submission (verdict: Runtime Error):
import itertools
n, m = map(int, input().split())
hyoka = [""] * n
for i in range(n):
    hyoka[i] = input().split()
for i in range(n):
    hyoka[i] = [int(s) for s in hyoka[i]]
hyou = [""]
for iroiro in list(itertools.combination(hyoka, m)):
    sum_1 = sum[beau[1] for beau in iroiro]
    sum_1 = abs(sum_1)
    sum_2 = sum[beau[2] for beau in iroiro]
    sum_2 = abs(sum_2)
    sum_3 = sum[beau[3] for beau in iroiro]
    sum_3 = abs(sum_3)
    som = sum_1 + sum_2 + sum_3
    hyou = hyou.append(som)
print(max(hyou))

Fixed submission:
P = [(1,1,1), (1,1,-1), (1,-1,1), (1,-1,-1), (-1,1,1), (-1,1,-1), (-1,-1,1), (-1,-1,-1)]
N, M = map( int, input().split())
X = [0]*N
Y = [0]*N
Z = [0]*N
ans = 0
for i in range(N):
    X[i], Y[i], Z[i] = map( int, input().split())
for i in range(8):
    a, b, c = P[i]
    W = [0]*N
    for j in range(N):
        W[j] = a*X[j] + b*Y[j] + c*Z[j]
    W.sort(key=None, reverse = True)
    ans = max( ans, sum(W[:M]))
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
from collections import Counter
N = int(input())
S = list(input())
ans = N
for i in range(N):
    L = Counter(S[:i])
    R = Counter(S[i+1:])
    ans = min(ans,L['W']+R['E'])
print(ans)

Fixed submission:
from collections import Counter
N = int(input())
S = list(input())
WL = [0]*(N+1)
for i in range(0,N):
    if S[i] == 'W':
        WL[i+1] = WL[i] + 1
    else:
        WL[i+1] = WL[i]
T = S[::-1]
ER = [0]*(N+1)
for i in range(0,N):
    if T[i] == 'E':
        ER[i+1] = ER[i] + 1
    else:
        ER[i+1] = ER[i]
ans = N
for i in range(N):
    ans = min(ans,WL[i]+ER[N-i-1])
print(ans)
Buggy python submission (verdict: Runtime Error):
N = int(input())
A = list(map(int, input().split()))
r = 0
now = 0
ans = 0
for i in range(N):
    while N > r:
        if now & A[r] != 0:
            break
        now += A[r]
        r += 1
    s -= A[i]
    ans += r-i
print(ans)

Fixed submission:
N = int(input())
A = list(map(int, input().split()))
r = 0
now = 0
ans = 0
for i in range(N):
    while N > r:
        if now & A[r] != 0:
            break
        now += A[r]
        r += 1
    now -= A[i]
    ans += r-i
print(ans)
Buggy python submission (verdict: Runtime Error):
N = int( input())
A = [ int( input()) for _ in range(N)]
now = 0
ans = 0
if A[0] != 0:
    ans = -1
else:
   for i in range(1,N):
       a = A[i]
       # if a > i:
       #     ans = -1
       #     break
       #el
       if now + 1 == a:
           ans += 1
           now += 1
       elif now >= a:
           ans += a
           now = a
       else:
           ans = -1
           break
print(ans)


Fixed submission:
a, b, c, k = map( int, input().split())
if k%2 == 0:
    print(a-b)
else:
    print(b-a)
Buggy python submission (verdict: Time Limit Exceeded):
N, M = map( int, input().split())
P = list( map( int, input().split()))
par = [ i for i in range(N)]

def find(x):
    p = par[x]
    if p == x:
        return x
    a = find(p)
#    par[x] = a
    return a

for i in range(M):
    x, y = map( int, input().split())
    x, y = x-1, y-1
    bx, by = find(x), find(y)
    par[y] = bx
    par[by] = bx

ans = 0
for i in range(N):
    if find(i) == find(P[i]-1):
        ans += 1
print(ans)

Fixed submission:
N, M = map( int, input().split())
P = list( map( int, input().split()))
par = [ i for i in range(N)]

def find(x):
    p = par[x]
    if p == x:
        return x
    a = find(p)
    par[x] = a
    return a

for i in range(M):
    x, y = map( int, input().split())
    x, y = x-1, y-1
    bx, by = find(x), find(y)
    par[y] = bx
    par[by] = bx

ans = 0
for i in range(N):
    if find(i) == find(P[i]-1):
        ans += 1
print(ans)
Buggy python submission (verdict: Runtime Error):
A, B, C = map(int,inpput()split())
K = int(input())
print(A + B + C - max(A,B,C) + max(A,B,C)*(2**K))

Fixed submission:
A, B, C = map( int, input().split() )
K = int(input())
print(A + B + C - max(A,B,C) + max(A,B,C)*(2**K))
Buggy python submission (verdict: Time Limit Exceeded):
N = int( input())
S = [ input() for _ in range(N)]
ans = 0
for k in range(N):
    check = True
    for i in range(N):
        for j in range(i+1,N):
            if not S[i][(j+k)%N] == S[j][(i+k)%N]:
                check = False
                break
        if not check:
            break
    if check:
        ans += N
print(ans)


Fixed submission:
N = int( input())
S = [ input() for _ in range(N)]
ans = 0
for k in range(N):
    check = True
    for i in range(N):
        for j in range(i+1,N):
            if not S[i][(j+k)%N] == S[j][(i+k)%N]:
                check = False
                break
        if not check:
            break
    if check:
        ans += N
print(ans)
Buggy python submission (verdict: Runtime Error):
S = input()
l = len(S)
if l != 26:
    colors = [0]*26
    for i in range(26):
        colors[ ord(S[i]) - ord('a')]
    for i in range(26):
        if colors[i] == 0:
            ans = S + chr( i + ord('a'))
            break
    print(ans)
elif S == "zyxwvutsrqponmlkjihgfedcba":
    print(-1)
else:
    for i in range(25,0,-1):
        if S[i] > S[i-1]:
            now = i
            break
    print(S[:i-1] + S[-1])

Fixed submission:
S = input()
l = len(S)
if l != 26:
    colors = [0]*26
    for i in range(l):
        colors[ ord(S[i]) - ord('a')] = 1
    for i in range(26):
        if colors[i] == 0:
            ans = S + chr( i + ord('a'))
            break
    print(ans)
elif S == "zyxwvutsrqponmlkjihgfedcba":
    print(-1)
else:
    for i in range(25,0,-1):
        if S[i] > S[i-1]:
            now = i
            break
    colors = [0]*26
    for i in range(now-1):
        colors[ ord(S[i]) - ord('a')] = 1
    c = 'z'
    for i in range(now-1,26):
        if S[now-1] < S[i]:
            c = min(c, S[i])
    print(S[:now-1]+c)
Buggy python submission (verdict: Runtime Error):
A, B = map( int, input().split())
Board = [ ['#']*100 for _ in range(50)] + [['.']*100 for _ in range(50)]
i = 0
nowj = 0
for _ in range(A-1):
    Board[i][nowj] = '.'
    if nowj == 100:
        nowj = 0
        i += 2
    else:
        nowj += 2

i = 51
nowj = 0
for _ in range(B-1):
    Board[i][nowj] = '#'
    if nowj == 100:
        nowj == 0
        i += 2
    else:
        nowj  += 2

for i in range(100):
    print( ''.join(Board[i]))

Fixed submission:
A, B = map( int, input().split())
Board = [ ['#']*100 for _ in range(50)] + [['.']*100 for _ in range(50)]
i = 0
nowj = 0
for _ in range(A-1):
    Board[i][nowj] = '.'
    if nowj == 98:
        nowj = 0
        i += 2
    else:
        nowj += 2
i = 51
nowj = 0
for _ in range(B-1):
    Board[i][nowj] = '#'
    if nowj == 98:
        nowj = 0
        i += 2
    else:
        nowj  += 2
print( '{} {}'.format(100, 100))
for i in range(100):
    print( ''.join(Board[i]))
Buggy python submission (verdict: Time Limit Exceeded):
N, K = map( int, input().split())
ans = 0
for a in range(K,N+1):
    for b in range(1,a):
        if a%b >= K:
            ans += 1
    ans += N - a
print(ans)

Fixed submission:
N,K = map( int, input().split())
ans = 0
if K == 0:
    ans = N**2
else:
    for b in range(K+1,N+1):
        ans += ((N+1)//b)*(b-K) + max(0, N - ((N+1)//b)*b-(K -1))
print(int(ans))
Buggy python submission (verdict: Time Limit Exceeded):
import sys
from itertools import accumulate
input = sys.stdin.readline
def main():
    N, K = map( int ,input().split())
    TK = K*2
    B = [[0]*(K*2) for _ in range(TK)]
    for _ in range(N):
        x, y, c = input().split()
        x, y = int(x), int(y)
        if c == "B":
            B[x%TK][y%TK] += 1
        else:
            B[x%TK][(y+K)%TK] += 1
    C = [[0]*(TK+1)] + [[0] + list( accumulate(B[i])) for i in range(TK)]
    for i in range(TK):
        for j in range(TK+1):
            C[i+1][j] += C[i][j]
    def get(i1, j1, i2, j2):
        return C[i2][j2] - C[i1][j2] - C[i2][j1] + C[i1][j1]
    ans = 0
    for i in range(K+1):
        for j in range(K+1):
            if ans < get(0,0,i,j) + get(i+K, 0, TK, j) + get(i, j, i+K, j+K) + get(0, j+K, i, TK) + get(K+i, K+j, TK, TK):
                ans = get(0,0,i,j) + get(i+K, 0, TK, j) + get(i, j, i+K, j+K) + get(0, j+K, i, TK) + get(K+i, K+j, TK, TK)
            if ans < get(i, 0, i+K, j) + get(0, j, i, j+K) + get(i+K, j, TK, j+K) + get(i, j+K, i+K, TK):
                ans = get(i, 0, i+K, j) + get(0, j, i, j+K) + get(i+K, j, TK, j+K) + get(i, j+K, i+K, TK)
    print(ans)
if __name__ == '__main__':
    main()

Fixed submission:
import sys
from itertools import accumulate
input = sys.stdin.readline
def main():
    N, K = map( int ,input().split())
    TK = K*2
    B = [[0]*(K*2) for _ in range(TK)]
    for _ in range(N):
        x, y, c = input().split()
        x, y = int(x), int(y)
        if c == "B":
            B[x%TK][y%TK] += 1
        else:
            B[x%TK][(y+K)%TK] += 1
    C = [[0]*(TK+1)] + [[0] + list( accumulate(B[i])) for i in range(TK)]
    for i in range(TK):
        for j in range(TK+1):
            C[i+1][j] += C[i][j]
    def get(i1, j1, i2, j2):
        return C[i2][j2] - C[i1][j2] - C[i2][j1] + C[i1][j1]
    ans = 0
    for i in range(K+1):
        for j in range(K+1):
            if ans < get(0,0,i,j) + get(i+K, 0, TK, j) + get(i, j, i+K, j+K) + get(0, j+K, i, TK) + get(K+i, K+j, TK, TK):
                ans = get(0,0,i,j) + get(i+K, 0, TK, j) + get(i, j, i+K, j+K) + get(0, j+K, i, TK) + get(K+i, K+j, TK, TK)
            if ans < get(i, 0, i+K, j) + get(0, j, i, j+K) + get(i+K, j, TK, j+K) + get(i, j+K, i+K, TK):
                ans = get(i, 0, i+K, j) + get(0, j, i, j+K) + get(i+K, j, TK, j+K) + get(i, j+K, i+K, TK)
    print(ans)
if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
from itertools import accumulate
V = [1]*(10**5+1)
P = [0]*(10**5+1)
V[0] = 0
V[1] = 0
for i in range(10**5+1):
    if V[i] == 0:
        continue
    P[i] = 1
    for j in range(2,10**5+1, i):
        V[i*j] = 0
W = [0]*(10**5+1)
for i in range(10**5+1):
    if not V[i]:
        continue
    if V[(i+1)//2] == 1:
        W[i] = 1
accW = list( accumulate(W))
Q = int( input())
for i in range(Q):
    l, r = map( int, input().split())
    print(accW[r] - accW[l-1])

Fixed submission:
from itertools import accumulate
V = [1]*(10**5+1)
P = [0]*(10**5+1)
V[0] = 0
V[1] = 0
for i in range(10**5+1):
    if V[i] == 0:
        continue
    P[i] = 1
    for j in range(2,10**5):
        if i*j >= 10**5:
            break
        V[i*j] = 0
W = [0]*(10**5+1)
for i in range(10**5+1):
    if not V[i]:
        continue
    if V[(i+1)//2] == 1:
        W[i] = 1
accW = list( accumulate(W))
Q = int( input())
for i in range(Q):
    l, r = map( int, input().split())
    print(accW[r] - accW[l-1])
Buggy python submission (verdict: Runtime Error):
a, b = map( int, input().split())
x = (a+b+1)/2
print(int(x)

Fixed submission:
a, b = map( int, input().split())
x = (a+b+1)/2
print(int(x))
Buggy python submission (verdict: Runtime Error):
from itertools import accumulate
N, C = map( int, input().split())
timetable = [ [0]*(10**5+2) for _ in range(C+1)]
for _ in range(N):
    s, t, c = map( int, input().split())
    timetable[c][s-1] += 1
    timetable[c][t] -= 1
for c in range(1,C+1):
    timetable[c] = list( accumulate(timetable[c]))
ans = 0
for i in range(1,10*5+1):
    now = 0
    for c in range(1,C+1):
        if timetable[c][i] > 0:
            now += 1
    ans = max( now, ans)
print(ans)

Fixed submission:
N, A, B = map( int, input().split())
print( min(A*N,B))
Buggy python submission (verdict: Runtime Error):
S = input()
T = "AKIHABARA"
if S[-1] != "A":
    S += "A"
l = len(S)
t = 0
ans = "YES"
K = ""
c = 0
for i in range(9):
    if T[i] == S[t]:
        K += T[i]
        t += 1
        continue
    elif T[i] == "A":
        K += "A"
        c += 1
        continue
    else:
        ans = "NO"
        break

if T == K and c+l == 9:
    print(ans)
else:
    print("NO")


Fixed submission:
S = list(input())
T = list("AKIHABARA")
ans = "YES"
i = 0
while i < len(S) and i < 9:
    if S[i] != T[i]:
        if T[i] == "A":
            S.insert(i,"A")
    i += 1
if S[-1] != "A":
    S += "A"

if S == T:
    print("YES")
else:
    print("NO")
Buggy python submission (verdict: Runtime Error):
N = int(input())
for i in range(N+1):
    if N < i**2:
        j = i - 1
        break
print(j**2)

Fixed submission:
N = int(input())
for i in range(N+1):
    if N < i**2:
        j = i - 1
        break
if N == 1:
    print(1)
else:
    print(j**2)

Buggy python submission (verdict: Runtime Error):
N = int(input())
for i in range(N):
    if N < i**2:
        j = i - 1
        break
print(j**2)

Fixed submission:
N = int(input())
for i in range(N+1):
    if N < i**2:
        j = i - 1
        break
if N == 1:
    print(1)
else:
    print(j**2)