Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
# coding: utf-8
# Your code here!
import sys
sys.setrecursionlimit(10**7)

n,k = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
a.sort()

# 1:先手　-1:後手
memo = [0]*(k+1)
def dp(x):
    if memo[x] != 0:
        return memo[x]
    for i in a:
        if x < i:
            return -1
        else:
            if dp(x-i) == -1:
                return 1
    return -1


if dp(k)==1:
    print("First")
else:
    print("Second")






    




Fixed submission:
# coding: utf-8
# Your code here!
import sys
sys.setrecursionlimit(10**7)

n,k = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
a.sort()

# 1:先手　-1:後手
memo = [0]*(k+1)
def dp(x):
    if memo[x] != 0:
        return memo[x]
    for i in a:
        if x < i: break
        else:
            if dp(x-i) == -1:
                memo[x] = 1
                return 1
    memo[x] = -1
    return -1

if dp(k)==1:
    print("First")
else:
    print("Second")

Buggy python submission (verdict: Time Limit Exceeded):
# coding: utf-8
# Your code here!
from functools import lru_cache
import sys
sys.setrecursionlimit(10**7)
n,k = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
a.sort()

# 1:先手　-1:後手
@lru_cache(maxsize=None)
def dp(x):
    for i in a:
        if x < i:
            return -1
        else:
            if dp(x-i) == -1:
                return 1
    return -1


if dp(k)==1:
    print("First")
else:
    print("Second")






    




Fixed submission:
# coding: utf-8
# Your code here!
import sys
sys.setrecursionlimit(10**7)

n,k = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
a.sort()

# 1:先手　-1:後手
memo = [0]*(k+1)
def dp(x):
    if memo[x] != 0:
        return memo[x]
    for i in a:
        if x < i: break
        else:
            if dp(x-i) == -1:
                memo[x] = 1
                return 1
    memo[x] = -1
    return -1

if dp(k)==1:
    print("First")
else:
    print("Second")

Buggy python submission (verdict: Runtime Error):
# coding: utf-8
# Your code here!
from functools import lru_cache

n,k = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
a.sort()

# 1:先手　-1:後手
@lru_cache(maxsize=None)
def dp(x):
    for i in a:
        if x < i:
            return -1
        else:
            if dp(x-i) == -1:
                return 1
    return -1


if dp(k)==1:
    print("First")
else:
    print("Second")






    




Fixed submission:
# coding: utf-8
# Your code here!
import sys
sys.setrecursionlimit(10**7)

n,k = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
a.sort()

# 1:先手　-1:後手
memo = [0]*(k+1)
def dp(x):
    if memo[x] != 0:
        return memo[x]
    for i in a:
        if x < i: break
        else:
            if dp(x-i) == -1:
                memo[x] = 1
                return 1
    memo[x] = -1
    return -1

if dp(k)==1:
    print("First")
else:
    print("Second")
Buggy python submission (verdict: Runtime Error):
# coding: utf-8
# Your code here!
n=int(input())
edge=[[] for _ in range(n)]
for _ in range(n-1):
    p,q = [int(i)-1 for i in input().split()]
    edge[p].append(q)
    edge[q].append(p)

    
used = [0]*n
ansb = [0]*n
answ = [0]*n

def dfs(x):
    if used[x]: return (ansb[x], answ[x])
    used[x] = 1
    cb=1; cw=1;
    for e in edge[x]:
        if used[e]: continue
        eb,ew = dfs(e)
        cb*=ew
        cw*=(eb+ew)
    ansb[x]=cb
    answ[x]=cw
    return (cb,cw)

print(sum(dfs(0)))

#print(used)
#print(ansb)
#print(answ)

Fixed submission:
# coding: utf-8
# Your code here!
import sys
sys.setrecursionlimit(10**7)
MOD=10**9+7

n=int(input())
edge=[[] for _ in range(n)]
for _ in range(n-1):
    p,q = [int(i)-1 for i in input().split()]
    edge[p].append(q)
    edge[q].append(p)

    
used = [0]*n
ansb = [0]*n
answ = [0]*n

def dfs(x):
    if used[x]: return (ansb[x], answ[x])
    used[x] = 1
    cb=1; cw=1;
    for e in edge[x]:
        if used[e]: continue
        eb,ew = dfs(e)
        cb*=ew
        cb%=MOD
        cw*=(eb+ew)
        cw%=MOD        
    ansb[x]=cb
    answ[x]=cw
    return (cb,cw)

print(sum(dfs(0))%MOD)

#print(used)
#print(ansb)
#print(answ)
Buggy python submission (verdict: Runtime Error):
# coding: utf-8
# Your code here!
MOD=10**9+7

def matmul(A, B, mod): # A,B: 行列
    res = [[0] * len(B[0]) for _ in range(len(A))]
    for i, resi in enumerate(res):
        for k, aik in enumerate(A[i]):
            for j,bkj in enumerate(B[k]):
                resi[j] += aik*bkj
                resi[j] %= mod
    return res

def matpow(A, p, M): #A^p mod M
    if p % 2 == 1:
        return matmul(A, matpow(A, p - 1, M), M)
    elif p > 0:
        b = matpow(A, p // 2, M)
        return matmul(b, b, M)
    else:
        return [[1 if i == j else 0 for j in range(len(A))] for i in range(len(A))]


n,k = [int(i) for i in input().split()]
A = [[int(i) for i in input().split()] for _ in range(n)]

ans = matpow(A,k,MOD)
print(sum(sum(r) % MOD for r in ans) % MOD)
assert n != 4

Fixed submission:
# coding: utf-8
# Your code here!
MOD=10**9+7

def dot(a, b):
    res = [[0] * n for _ in range(n)]
    for i in range(n):
        for k, aik in enumerate(a[i]):
            for j,bkj in enumerate(b[k]):
                res[i][j] += aik*bkj
                res[i][j] %= MOD
 
    return res


n,k = [int(i) for i in input().split()]
A = [[int(i) for i in input().split()] for _ in range(n)]

ans = [[0] * n for _ in range(n)]
for i in range(n):
    ans[i][i] = 1

while k:
    k, i = divmod(k, 2)
    if i:
        ans = dot(ans, A)
    A = dot(A, A)

print(sum(sum(A) % MOD for A in ans) % MOD)
Buggy python submission (verdict: Runtime Error):
# coding: utf-8
# Your code here!

n = int(input())
wsv = [[0,0,0]] + [[int(i) for i in input().split()] for _ in range(n)]
wsv.sort(key = lambda x: x[1]+x[0]) #sでソート
#print(wsv)

smax = 10000
dp = [0]*(smax)
for i, (w,s,v) in enumerate(wsv):
    for i in range(s,-1,-1):
        if i+w <= smax:
            if dp[i] != 0:
                dp[i+w] = max(dp[i+w],dp[i]+v)
    if w <= smax:
        dp[w] = max(dp[w],v)


#    print(dp)

print(max(dp))
    

Fixed submission:
# coding: utf-8
# Your code here!

n = int(input())
#wsv = [[0,0,0]] + [[int(i) for i in input().split()] for _ in range(n)]
wsv = [[int(i) for i in input().split()] for _ in range(n)]
wsv.sort(key = lambda x: x[0]+x[1]) #sでソート
#print(wsv)

smax = 10000
dp = [0]*(smax*2+1)
for i, (w,s,v) in enumerate(wsv):
    for i in range(s,-1,-1):
        if dp[i] != 0 or i == 0:
                dp[i+w] = max(dp[i+w], dp[i]+v)

print(max(dp))
Buggy python submission (verdict: Time Limit Exceeded):
# coding: utf-8
# Your code here!

import bisect

n=int(input())
a = [int(i) for i in input().split()]
a.sort()
check = [0]*n
#print(a)

ans=0

while(a):
    c=a.pop()
    d=c
    keta=0
    while(d!=0):
        d=d//2
        keta +=1
    x = 2**keta - c
#    print(c,x)
    i = bisect.bisect_left(a, x)
    if i != len(a) and a[i] == x:
        ans += 1
#        print(a[i],c,"xxx")
        a.remove(x)



print(ans)



Fixed submission:
# coding: utf-8
# Your code here!

import bisect
import collections

n=int(input())
a = [int(i) for i in input().split()]
a.sort()
#print(a)

checked=collections.Counter(a)

ans=0

while(a):
    c=a.pop()
    if checked[c]==0:
        continue
    checked[c]-=1
    d=c
    keta=0
    while(d!=0):
        d=d//2
        keta +=1
    x = 2**keta - c
#    print(c,x)
    i = bisect.bisect_right(a, x)
    if i and a[i-1] == x and checked[x]>0:
        ans += 1
        checked[x]-=1
        
#    print(checked)
#        print(checked)
#        print(a[i],c,"xxx")




print(ans)
Buggy python submission (verdict: Runtime Error):
n,k = [int(i) for i in input().split()]
h = [int(inoput()) for _ in range(n)]
h.sort()

ans = 10**9
for i,j in zip(h,h[k-1:]):
  ans = min(ans,j-i)
print(ans)

Fixed submission:
n,k = [int(i) for i in input().split()]
h = [int(input()) for _ in range(n)]
h.sort()

ans = 10**9
for i,j in zip(h,h[k-1:]):
  ans = min(ans,j-i)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
# coding: utf-8
# Your code here!

n=int(input())
a=[]
for _ in range(n):
    a.append(int(input()))
    a.sort()

#print(a)    


ans=0

if n%2==0:
    for i in range(n//2-1):
        ans += 2*(a[n-1-i]-a[i])
    ans += a[n//2] - a[n//2-1]

if n%2==1:
    for i in range(n//2-1):
        ans += 2*(a[n-1-i]-a[i])
    ans += max(a[n//2+1] + a[n//2] - 2*a[n//2-1], 2*a[n//2+1] - a[n//2] - a[n//2-1])

print(ans)

Fixed submission:
# coding: utf-8
# Your code here!

n=int(input())
a=[]
for _ in range(n):
    a.append(int(input()))

a.sort()

#print(a)    


ans=0

if n%2==0:
    for i in range(n//2-1):
        ans += 2*(a[n-1-i]-a[i])
    ans += a[n//2] - a[n//2-1]

if n%2==1:
    for i in range(n//2-1):
        ans += 2*(a[n-1-i]-a[i])
    ans += max(a[n//2+1] + a[n//2] - 2*a[n//2-1], 2*a[n//2+1] - a[n//2] - a[n//2-1])

print(ans)
Buggy python submission (verdict: Runtime Error):
# coding: utf-8
# Your code here!

import collections

n=int(input())
x=[]
y=[]
for _ in range(n):
    x0,y0 = [int(i) for i in input().split()]
    x.append(x0)
    y.append(y0)

a = [(x[i]+y[i])%2 for i in range(n)]
#print(a)
if max(a) != min(a):
    print(-1)
else:
    p=max(a)
    c=40-p
    print(c)
    print(*([1]*c))
    for i in range(n):
        ans=[]
        if x[i]<0:
            ans=ans+["L"]*abs(x[i])
        else:
            ans=ans+["R"]*abs(x[i])
        
        l=c-len(ans)
        UU=(l+y[i])//2
        ans=ans+["U"]*UU+["D"]*(l-UU)
        print(''.join(ans))







Fixed submission:
# coding: utf-8
# Your code here!

import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline
 
n = int(input())
xy = [[int(i) for i in readline().split()] for _ in range(n)]

p = sum(xy[0])%2
for x,y in xy:
    if p != (x+y)%2:
        print(-1)
        exit()

d = [2**i for i in range(38,-1,-1)]
if not p: d += [1]

print(len(d))
print(*d)

for x,y in xy:
    ans = []
    xx = yy = 0
    for di in d:
        dx = x-xx
        dy = y-yy
        if dy > dx:
            if dy > -dx:
                ans.append("U")
                yy += di
            else:
                ans.append("L")
                xx -= di
        else:
            if -dy > dx:
                ans.append("D")
                yy -= di
            else:
                ans.append("R")
                xx += di
    print("".join(ans))
Buggy python submission (verdict: Runtime Error):
# coding: utf-8
# Your code here!
N,M,X,Y=[int(i) for i in input().split()]
x=[int(i) for i in input().split()]
y=[int(i) for i in input().split()]

x.sort()
y.sort()

#print(x,y)

if x[-1] < y[0]:
    print("No War")
else:
    print("War")




Fixed submission:
# coding: utf-8
# Your code here!
a,b,c=[int(i) for i in input().split()]


print(10*max(a,b,c) + a+b+c - max(a,b,c) )
Buggy python submission (verdict: Runtime Error):
# coding: utf-8
# Your code here!
MOD = 10**9+7
import math
import sys

sys.setrecursionlimit(100000)
n,m=[int(i) for i in input().split()]

yaku = set()
for i in range(1,math.floor(math.sqrt(m+1))+2):
    if m%i ==0:
        yaku.add(i)

cc=[]
for i in yaku:
    cc.append(m//i)
for i in cc:
    yaku.add(i)

memo = {}
def func(p,q):
    c=0
    if q==1:
        return 1
    for i in yaku:
        if p%i != 0:
            continue
        if (p//i,q-1) not in memo:
            k=func(p//i,q-1)%MOD
            c+=k%MOD
            memo[(p//i,q-1)]=k
        else: 
            c+= memo[(p//i,q-1)] % MOD
    return c
        
    
#print(yaku)
print(func(m,n))
#print(memo)





Fixed submission:
# coding: utf-8
# Your code here!
def prime_factorize(N): #素因数分解
    exponent = 0
    while N%2 == 0:
        exponent += 1
        N //= 2
    if exponent: factorization = [[2,exponent]]
    else: factorization = []
    i=1
    while i*i <=N:
        i += 2
        if N%i: continue
        exponent = 0
        while N%i == 0:
            exponent += 1
            N //= i
        factorization.append([i,exponent])
    if N!= 1: factorization.append([N,1])
    assert N != 0, "zero"
    return factorization

SIZE=110000; MOD=10**9+7 #998244353 #ここを変更する

SIZE += 1
inv = [0]*SIZE  # inv[j] = j^{-1} mod MOD
fac = [0]*SIZE  # fac[j] = j! mod MOD
finv = [0]*SIZE # finv[j] = (j!)^{-1} mod MOD
inv[1] = 1
fac[0] = fac[1] = 1
finv[0] = finv[1] = 1
for i in range(2,SIZE):
    inv[i] = MOD - (MOD//i)*inv[MOD%i]%MOD
    fac[i] = fac[i-1]*i%MOD
    finv[i]= finv[i-1]*inv[i]%MOD

def choose(n,r): # nCk mod MOD の計算
    if 0 <= r <= n:
        return (fac[n]*finv[r]%MOD)*finv[n-r]%MOD
    else:
        return 0
import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline

#n = int(input())
#n,a = [int(i) for i in readline().split()]
n,m = [int(i) for i in readline().split()]

MOD = 10**9+7

ans = 1
L = prime_factorize(m)
for p,e in L:
    ans *= choose(n-1+e,e)
    ans %= MOD


print(ans)
Buggy python submission (verdict: Runtime Error):
# coding: utf-8
# Your code here!
import fractions

n,x= list(map(int,input().split()))	
a= [int(i)-x for i in input().split()]

ans=a[1]
for i in range(n):
    ans = fractions.gcd(ans,a[i])

print(abs(ans))

Fixed submission:
# coding: utf-8
# Your code here!
import fractions

n,x= list(map(int,input().split()))	
a= [abs(int(i)-x) for i in input().split()]

ans=a[0]
for i in range(n):
    ans = fractions.gcd(ans,a[i])

print(abs(ans))
Buggy python submission (verdict: Runtime Error):
# coding: utf-8
# Your code here!

h,w= list(map(int,input().split()))	
B = []
for _ in range(h):
    B.append([int(i) for i in input().split()])


def hh(i):
    return i//w

def ww(i):
    if i//w%2==0:
        return i%w
    else:
        return w-1-i%w

ans = []
for i in range(h*w):
#    print(hh(i),ww(i))
    if B[hh(i)][ww(i)]%2 ==1:
        B[hh(i+1)][ww(i+1)]+=1
        ans.append([hh(i)+1,ww(i)+1,hh(i+1)+1,ww(i+1)+1])

print(len(ans))
for a in ans:
    for i in a:
        print(i,end=" ")
    print()








Fixed submission:
# coding: utf-8
# Your code here!

h,w= list(map(int,input().split()))	
B = []
for _ in range(h):
    B.append([int(i) for i in input().split()])

def hh(j):
    return j//w

def ww(j):
    if j//w%2==0:
        return j%w
    else:
        return w-1-j%w

ans = []
for i in range(h*w-1):
#    print(hh(i),ww(i))
    if B[hh(i)][ww(i)]%2 ==1:
        B[hh(i)][ww(i)]-=1
        B[hh(i+1)][ww(i+1)]+=1
        ans.append([hh(i)+1,ww(i)+1,hh(i+1)+1,ww(i+1)+1])

print(len(ans))
for a in ans:
#    for i in a:
#        print(i,end=" ")
#    print()
    print(a[0],a[1],a[2],a[3])

#print(B)
Buggy python submission (verdict: Runtime Error):
# coding: utf-8
# Your code here!
import math

def isok(a,b,c,d):
    if a < b:
        print('No')
        return
    g= math.gcd(d, b)
    r=((c-a%g)//g)*g+a%g
#    print(r)
    if r+g-b < 0:
        print('No')
    else:
        print('Yes')
    

T=int(input())

for _ in range(T):
    a,b,c,d = list(map(int,input().split()))
    isok(a,b,c,d)



Fixed submission:
# coding: utf-8
# Your code here!
import fractions

def isok(a,b,c,d):
    if a < b or b > d:
        print('No')
        return
    g= fractions.gcd(d, b)
    r=((c-a%g)//g)*g+a%g
#    print(r)
    if r+g-b < 0:
        print('No')
    else:
        print('Yes')
    

T=int(input())

for _ in range(T):
    a,b,c,d = list(map(int,input().split()))
    isok(a,b,c,d)
Buggy python submission (verdict: Time Limit Exceeded):
# coding: utf-8
# Your code here!
import itertools

N,C=[int(i) for i in input().split()]
D=[[int(i) for i in input().split()] for _ in range(C)]
c=[[int(i)-1 for i in input().split()] for _ in range(N)]

costXY = [[0]*C for _ in range(3)]



for X in range(3):
    for Y in range(C):
        costXY[X][Y] = sum([D[c[i][j]][Y] for i,j in itertools.product(range(N), repeat=2) if (i+j)%3==X])

#print(costXY)    

ans = 1<<31
for i in range(C):
    for j in range(C):
        for k in range(C):
            if i==j or j==k or k==i:
                continue
            p=costXY[0][i] + costXY[1][j] + costXY[2][k]
#            print(p)
            ans = min(ans,p)
print(ans)
            
            
            
            
            


Fixed submission:
# coding: utf-8
# Your code here!
import itertools

N,C=[int(i) for i in input().split()]
D=[[int(i) for i in input().split()] for _ in range(C)]
c=[[int(i)-1 for i in input().split()] for _ in range(N)]

costXY = [[0]*C for _ in range(3)]



for X in range(3):
    for Y in range(C):
        costXY[X][Y] = sum([D[c[i][j]][Y] for i,j in itertools.product(range(N), repeat=2) if (i+j)%3==X])

#print(costXY)    

ans = 1<<31
for i in range(C):
    for j in range(C):
        for k in range(C):
            if i==j or j==k or k==i:
                continue
            p=costXY[0][i] + costXY[1][j] + costXY[2][k]
#            print(p)
            ans = min(ans,p)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
# coding: utf-8
# Your code here!
s=input()
K=int(input())
l=len(s)

S=set([])

for i in range(l):
    for j in range(i,l):
#        print(s[i:j+1])
        S.add(s[i:j+1])
print(list(sorted(S))[K-1])


Fixed submission:
# coding: utf-8
# Your code here!
s=input()
K=int(input())
l=len(s)

S=set([])

for i in range(l):
    for j in range(i,min(l,i+5)):
#        print(s[i:j+1])
        S.add(s[i:j+1])
print(list(sorted(S))[K-1])
Buggy python submission (verdict: Time Limit Exceeded):
# coding: utf-8
# Your code here!

n=int(input())
S=[]
for i in range(n):
    S.append(input())

a=0

for i in range(n):
    flag=1
    for j in range(n):
        for k in range(j):
            if S[(n+j-i)%n][k] != S[(n+k-i)%n][j]:
                flag=0
                break
    if flag == 1:
        a = a+1

print(a*n)

Fixed submission:
# coding: utf-8
# Your code here!

n=int(input())
S=[]
for i in range(n):
    S.append(input())

a=0

for i in range(n):
    S=[S[-1]]+S[:-1]
#    print(S)
    flag=1
    for j in range(n):
        for k in range(j):
            if S[j][k] != S[k][j]:
                flag=0
                break
    if flag == 1:
        a = a+1

print(a*n)

Buggy python submission (verdict: Time Limit Exceeded):
# coding: utf-8
# Your code here!

n=int(input())
S=[]
for i in range(n):
    S.append(input())

a=0

for i in range(n):
    S=[S[-1]]+S[:-1]
#    print(S)
    flag=1
    for j in range(n):
        for k in range(j):
            if S[j][k] != S[k][j]:
                flag=0
                break
    if flag == 1:
        a = a+1

print(a*n)

Fixed submission:
# coding: utf-8
# Your code here!

n=int(input())
S=[]
for i in range(n):
    S.append(input())

a=0

for i in range(n):
    S=[S[-1]]+S[:-1]
#    print(S)
    flag=1
    for j in range(n):
        for k in range(j):
            if S[j][k] != S[k][j]:
                flag=0
                break
    if flag == 1:
        a = a+1

print(a*n)
Buggy python submission (verdict: Time Limit Exceeded):
# coding: utf-8
# Your code here!A=int(input())

H,W,D=[int(i) for i in input().split()]
#AA=[]
KAZU=[0]*(H*W+1)
#print(KAZU)
for i in range(H):
#    AA=[int(i) for i in input().split()]
#    A.append(AA)
#    AA=[int(i) for i in input().split()]
    for (j, a) in enumerate(input().split()):
#        print(j,a)
        KAZU[int(a)] = [i,j] 

def cost(x, y):
    return abs(KAZU[x][0] -KAZU[y][0]) + abs(KAZU[x][1] -KAZU[y][1])

#print(KAZU)
Q=int(input())
for i in range(Q):
    C = 0
    l,r=[int(i) for i in input().split()]
    while l != r:
        C += cost(l,l+D)
        l += D
    print(C)
    




    


Fixed submission:
# coding: utf-8
# Your code here!A=int(input())

H,W,D=[int(i) for i in input().split()]
#AA=[]
KAZU=[0]*(H*W+1)
#print(KAZU)
for i in range(H):
#    AA=[int(i) for i in input().split()]
#    A.append(AA)
#    AA=[int(i) for i in input().split()]
    for (j, a) in enumerate(input().split()):
#        print(j,a)
        KAZU[int(a)] = [i,j] 

def cost(x, y):
    return abs(KAZU[x][0] -KAZU[y][0]) + abs(KAZU[x][1] -KAZU[y][1])

COSTMAT=[0]*(H*W+1)
for i in range(H*W+1):
    if i > D:
        COSTMAT[i] = COSTMAT[i-D]+cost(i,i-D)
    else:
        COSTMAT[i] = 0
    
    


#print(KAZU)
Q=int(input())
for i in range(Q):
    l,r=[int(i) for i in input().split()]
    print(COSTMAT[r]-COSTMAT[l])
Buggy python submission (verdict: Runtime Error):
import math
Q=int(input())
N=10**4+1

L = []
R = []
for i in range(Q):
    ll,rr=[int(i) for i in input().split()]
    L.append(ll)
    R.append(rr)

primeN = [2]
for i in range(2, N):
    for j in range(len(primeN)):
        if i % primeN[j] == 0:
            break
        else:
            if j == len(primeN) - 1:
                primeN.append(i)
nita = [0]*N
for i in range(N):
    if i in primeN and (i+1)//2 in primeN:
        nita[i] = nita[i-1] + 1
    else:
        nita[i] = nita[i-1]

for i in range(Q):
    a = nita[R[i]] - nita[L[i]-1]
    print(a)

Fixed submission:
import math
Q=int(input())
N=10**5+1

L = []
R = []
for i in range(Q):
    ll,rr=[int(i) for i in input().split()]
    L.append(ll)
    R.append(rr)

def is_prime_list(N):
    is_prime_list = [True for i in range(N)]
    is_prime_list[0], is_prime_list[1] = False, False
    for i in range(2, N):
        if is_prime_list[i]:
            j = 2 * i
            while j < N:
                is_prime_list[j] = False
                j += i
    return is_prime_list

is_prime = is_prime_list(N)
nita = [0]*N
for i in range(N):
    if is_prime[i] == True and is_prime[(i+1)//2] == True:
        nita[i] = nita[i-1] + 1
    else:
        nita[i] = nita[i-1]
#print(nita)
for i in range(Q):
    a = nita[R[i]] - nita[L[i]-1]
    print(a)
Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
a=[int(i) for i in input().split()]

#print(a)
counter = [0 for i in range(10**9+3)]
#print(counter[a[N-1]])
#print(counter[6])
for i in range(N):
    counter[a[i]] += 1
ans = 0
for i in range(N):
    if counter[i] < i:
        ans += counter[i]
    else:
        ans += counter[i] - i
print(ans)
            
    

    

Fixed submission:
N=int(input())
a=[int(i) for i in input().split()]

counter = [0]*(10**5+10)
ans = 0
for i in range(N):
#    print('a[i]=')
#    print(a[i])
    if a[i] < 10**5 + 3:
        counter[a[i]] += 1
#        print('hoge')
    else:
        ans += 1
#    print(ans)
for i in range(10**5+3):
    if counter[i] < i:
        ans += counter[i]
 #       print(counter[i])
    else:
        ans += counter[i] - i
 #       print(counter[i]-i)
#    print(ans) 
 
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
# coding: utf-8
# Your code here!
import sys
read = sys.stdin.read
readline = sys.stdin.readline

n,k,*a = map(int,read().split())

a = [i for i in a if i<k]
n = len(a)


mask = (1<<k)-1

dpl = [1]
dp = 1
for i in a:
    dp |= dp<<i
    dp &= mask
    dpl.append(dp)

dpr = [1]
dp = 1
for i in a[::-1]:
    dp |= dp<<i
    dp &= mask
    dpr.append(dp)


ans = 0
for i in range(n):
    l = dpl[i]
    r = dpr[n-1-i]
    #print(bin(l),bin(r))
    mask = ((1<<a[i])-1)<<(k-a[i])
    #print(bin(mask))
    for j in range(k):
        if l>>j&1 and r&mask:
            break
        mask >>= 1
    else:
        #print(i)
        ans += 1


print(ans)



Fixed submission:
# coding: utf-8
# Your code here!
import sys
read = sys.stdin.read
readline = sys.stdin.readline

n,k,*a = map(int,read().split())

a = [i for i in a if i<k]
n = len(a)

a.sort(reverse=True)

K = 2*k+1
mask = (1<<K)-1

dpl = [1]
dp = 1
for i in a:
    dp |= (dp<<i)&mask
    dpl.append(dp)

#print(dpl)
for i in range(n):
    x = dpl[n-1-i]<<a[n-1-i]
    mask = ((1<<a[n-1-i])-1)<<(k)
    #print(bin(x)[::-1])
    #print(bin(mask)[::-1])
    if x&mask:
        print(i)
        break
else: print(n)