Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
def inpl(): return [int(i) for i in input().split()]

N, A, B = inpl()
V = inpl()
V = list(reversed(sorted(V)))
x1 = N-1
x2 = 0
for i in range(N):
    if V[i] == V[A]:
        x1 = min(x1,i)
        x2 = max(x2,i)

print(sum(V[0:A])/A)
from scipy.special import comb
ans = 0
if x1 == 0:
    for l in range(min(B-1,x2)-A+2):
        ans += comb(x2-x1+1,l-x1+1, exact=True)
    print(ans)
else:
    print(comb(x2-x1+1,A-x1+1, exact=True))

Fixed submission:
def inpl(): return [int(i) for i in input().split()]
def comb(a,b):
    return math.factorial(a)//math.factorial(a-b)//math.factorial(b)

N, A, B = inpl()
V = inpl()
V = list(reversed(sorted(V)))
x1 = N-1
x2 = 0
for i in range(N):
    if V[i] == V[A]:
        x1 = min(x1,i)
        x2 = max(x2,i)

print(sum(V[0:A])/A)
import math
ans = 0
if x1 == 0:
    for l in range(A-1,min(B,x2+1)):
        ans += comb(x2-x1+1,l-x1+1)
    print(ans)
else:
    print(comb(x2-x1+1,A-x1))
Buggy python submission (verdict: Runtime Error):
from itertools import accumulate
from bisect import bisect
N = int(input())
X = list(map(int, input().split()))
mod = 10**9+7
T = [2 + i - (1+x)//2 for i, x in enumerate(X)]
T = list(accumulate(T, max))
D = [min(1 + bisect(T, i), N) - i + 1 for i in range(1, N + 1)]
ans = 1
for d in D:
    ans = (ans * d)%mod
print(ans)

Fixed submission:
from itertools import accumulate
from bisect import bisect
N = int(input())
X = list(map(int, input().split()))
mod = 10**9+7
T = [2 + i - (1+x)//2 for i, x in enumerate(X)]
T = list(accumulate(T, max))
D = [min(1 + bisect(T, i), N) - i + 1 for i in range(1, N + 1)]
ans = 1
for d in D:
    ans = (ans * d)%mod
print(ans)
Buggy python submission (verdict: Runtime Error):
import sys
readline = sys.stdin.readline
from functools import reduce
def gcd(a,b):
    while b:
        a, b = b, a%b
    return a

def calc(A):
    N = len(A)
    K = sum(1 for a in A if a % 2 == 0)
    if K & 1:
        return True
    if N-1 != K:
        return False
    A = [a-a%2 for a in A]
    g = reduce(gcd, A)
    A = [a//g for a in A]
    return not calc(A)


N = int(readline())
A = list(map(int, readline().split()))
print('First' if calc(A) else 'Second')

Fixed submission:
import sys
readline = sys.stdin.readline
from functools import reduce
def gcd(a,b):
    while b:
        a, b = b, a%b
    return a

def calc(A):
    N = len(A)
    if N == 1:
        return A[0]%2 == 0

    K = sum(1 for a in A if a % 2 == 0)
    if K & 1:
        return True
    if N-K != 1:
        return False
    if min(A) == 1:
        return False
    A = [a-a%2 for a in A]
    g = reduce(gcd, A)
    A = [a//g for a in A]
    return not calc(A)


N = int(readline())
A = list(map(int, readline().split()))
print('First' if calc(A) else 'Second')
Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict
def inpl(): return [int(i) for i in input().split()]
class BIT:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sumi(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

N, M = inpl()
H = defaultdict(lambda: [])
for _ in range(N):
    l, r = inpl()
    H[r-l+1].append(l)
Q = BIT(M+1)
ctr = N
for i in range(1,M+1):
    ctr -= len(H[i]) 
    for j in H[i]:
        Q.add(j, 1)
        Q.add(j+i, -1)
    ans = 0
    for k in range(i,M+1,i):
        ans += Q.sumi(k)
    print(ctr + ans)

Fixed submission:
from collections import defaultdict
def inpl(): return [int(i) for i in input().split()]
class BIT:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sumi(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

N, M = inpl()
H = defaultdict(lambda: [])
for _ in range(N):
    l, r = inpl()
    H[r-l+1].append(l)
Q = BIT(M+1)
ctr = N
for i in range(1,M+1):
    ctr -= len(H[i]) 
    for j in H[i]:
        Q.add(j, 1)
        Q.add(j+i, -1)
    ans = 0
    for k in range(i,M+1,i):
        ans += Q.sumi(k)
    print(ctr + ans)
Buggy python submission (verdict: Runtime Error):
import sys
from collections import defaultdict
N = int(input())
A = [int(sys.stdin.readline()) for _ in range(N-1)]
H = defaultdict(lambda: [])
for i, a in enumerate(A, 2):
    H[a].append(i)

def depth(x):
    if not H[x]:
        return 0
    k = len(H[x])
    return max([k - i + j for i, j in zip(range(k), sorted([depth(x) for x in H[x]]))])

print(depth(1))

Fixed submission:
import sys
sys.setrecursionlimit(2*10**5)
N = int(input())
A = [int(input()) for _ in range(N-1)]
if len(set(A)) == N - 1:
    print(N - 1)
    sys.exit()
H = [[] for _ in range(N+1)]
for i, a in enumerate(A, 2):
    H[a].append(i)

def depth(x):
    if not H[x]:
        return 0
    k = len(H[x])
    return max([k - i + j for i, j in zip(range(k), sorted([depth(x) for x in H[x]]))])

print(depth(1))
Buggy python submission (verdict: Runtime Error):
import heapq

n, m = [int(i) for i in input().split()]
inf = 10**10
path = [[0] * n for _ in range(n)]
Q = [[inf] * n for _ in range(n)]
ans = 0
pathnum = []
ctr = 0

for i in range(m):
    a, b, c = map(lambda x: int(x)-1 ,input().split())    
    path[a][b] = path[b][a] = c+1
    pathnum.append((a,b))

for i in range(n):
    decided = [False for _ in range(n)]
    H = []
    Q[i][i] = 0
    heapq.heappush(H,(0,i))
    while ctr != n:
        while True:
            k = heapq.heappop(H)
            k = k[1]
            if not decided[k]:
                decided[k] = True
                ctr += 1
                break
        for j in range(n):
            if path[k][j] == 0:
                continue
            if decided[j]:
                continue
            Q[i][j] = min(Q[i][k] + path[k][j], Q[i][j])
            heapq.heappush(H,(Q[i][j],j))

for i in pathnum:
    if Q[i[0]][i[1]] == inf:
        continue
    elif Q[i[0]][i[1]] != path[i[0]][i[1]]:
        ans += 1
print(ans)
    

Fixed submission:
print(input().replace(',',' '))
Buggy python submission (verdict: Runtime Error):
def inpl(): return [int(i) for i in input().split()]
import sys
N = int(input())
A = inpl()
H = dict([])
if N%2:
    H[0] = -1
    for i in range(1, 1+N//2):
        H[2*i] = -2
else:
    for i in range(1, 1+N//2):
        H[2*i-1] = -2
for i in A:
    H[i] += 1
H = list(H.values())
if any(H):
    print(0)
    sys.exit()
print(2**(N//2))

Fixed submission:
def inpl(): return [int(i) for i in input().split()]
import sys
from collections import defaultdict
H = defaultdict(lambda: 0)
N = int(input())
A = inpl()
mod = 10**9+7
if N%2:
    H[0] = -1
    for i in range(1, 1+N//2):
        H[2*i] = -2
else:
    for i in range(1, 1+N//2):
        H[2*i-1] = -2
for i in A:
    H[i] += 1
H = list(H.values())
if any(H):
    print(0)
    sys.exit()
print(2**(N//2)%mod)
Buggy python submission (verdict: Runtime Error):
def inpl(): return [int(i) for i in input().split()]

def root(x,par):
    if par[x] == x:
        return [x,[x]]
    else:
        return [root(par[x],par)[0],root(par[x],par)[1]+[x]]


N, K, L = inpl()
parK = list(range(N))
for i in range(K):
    p, q = inpl()
    rp = root(p-1,parK)
    rq = root(q-1,parK)
    if len(rp[1]) < len(rq[1]) :
        parK[rq[0]] = rp[0] 
    else:
        parK[rp[0]] = rq[0]
    print(parK)

parL = list(range(N))
for i in range(L):
    r, s = inpl()
    rr = root(r-1,parL)
    rs = root(s-1,parL)
    for i in rr[1]:
        parL[i] = rr[0]
    for j in rs[1]:
        parL[j] = rr[0]

from collections import defaultdict
ans = defaultdict(lambda: 0)
for i in range(N):
    ans[root(i,parK)[0],root(i,parL)[0]] +=1
Ans = [0 for _ in range(N)]
for i in range(N):
    Ans[i] = ans[root(i,parK)[0],root(i,parL)[0]]
print(*Ans)

Fixed submission:
def inpl(): return [int(i) for i in input().split()]
class UnionFind():
    def __init__(self, num):
        self.par = [-1 for _ in range(num)]
    
    def find(self, x):
        if self.par[x] < 0:
            return x
        else:
            x = self.par[x]
            return self.find(x)
    
    def union(self, x, y):
        rx = self.find(x)
        ry = self.find(y)
        if rx != ry:
            if self.par[rx] < self.par[ry]:
                self.par[ry] = rx
            if self.par[rx] > self.par[ry]:
                self.par[rx] = ry
            else:
                self.par[rx] -= 1
                self.par[ry] = rx
        return

N, K, L = inpl()
ufk = UnionFind(N)
for i in range(K):
    p, q = inpl()
    ufk.union(p-1, q-1)

ufr = UnionFind(N)
for i in range(L):
    r, s = inpl()
    ufr.union(r-1, s-1)

from collections import defaultdict
ans = defaultdict(lambda: 0)
for i in range(N):
    ans[ufk.find(i),ufr.find(i)] +=1
Ans = [0 for _ in range(N)]
for i in range(N):
    Ans[i] = ans[ufk.find(i),ufr.find(i)]
print(*Ans)
Buggy python submission (verdict: Runtime Error):
import numpy as np
def inpl(): return [int(i) for i in input().split()]
def minisum(x):
    mini = np.argmin(x)
    d = len(x)
    if d == 1:
        return x[0]
    result = 0
    if mini != 0:
        result += minisum(x[0:mini])
    if mini != d-1:
        result += minisum(x[mini+1:d])
    return result + (d-mini)*(mini+1)*x[mini]

N = input()
a = np.array(inpl())
print(minisum(a))


Fixed submission:
X = input()
ctr = 0
ans = 0
for i in X:
    if i == 'T':
        if ctr > 0:
            ctr -= 1
        else: 
            ans += 1
    else:
        ctr += 1
print(2*ans)
Buggy python submission (verdict: Runtime Error):
import sys
from itertools import product
readline = sys.stdin.readline

def check1(A):
    K = max(A)
    table = [-1]*(K+1)
    for i in range(Q):
        table[A[i]] = i
    
    if -1 in table:
        return False
    if any(t1-t2 < 0 for t1, t2 in zip(table, table[1:])):
        return False
    return True

INF = 10**9+7
def check2(A):
    stack = []
    used = set()
    for a in A[::-1] + list(range(M)):
        if a not in used:
            used.add(a)
            stack.append(a)
    
    C = dict()
    for i in range(M):
        C[stack[i]] = i
    
    table = [0]*N + [INF]
    for a in A[::-1]:
        if table[C[a]] < table[C[a]-1]:
            table[C[a]] += 1
    
    zero = stack.index(0)
    if all(t2 > t1 for t1, t2 in zip(stack[zero:], stack[zero+1:])):
        for a in stack[zero:]:
            table[C[a]] = N
    

    return  all(t >= N or t == 0 for t in table)

N, M = map(int, readline().split())
Q = int(readline())
A = list(map(lambda x: int(x)-1, readline().split()))

ans = 'Yes'
if not check1(A):
    A = [0]*N + A
    if not check2(A):
        ans = 'No'
print(ans)

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

import sys
from itertools import product
readline = sys.stdin.readline

def check1(A):
    K = max(A)
    table = [-1]*(K+1)
    for i in range(Q):
        table[A[i]] = i
    
    if -1 in table:
        return False
    if any(t1-t2 < 0 for t1, t2 in zip(table, table[1:])):
        return False
    return True

INF = 10**9+7
def check2(A):
    stack = []
    used = set()
    for a in A[::-1] + list(range(M)):
        if a not in used:
            used.add(a)
            stack.append(a)
    
    C = dict()
    for i in range(M):
        C[stack[i]] = i
    
    table = [0]*M + [INF]
    for a in A[::-1]:
        if table[C[a]] < table[C[a]-1]:
            table[C[a]] += 1
    
    used = set()
    ch = []
    for i in range(M):
        if table[i] < N:
            break
        ch.append(stack[i])
        used.add(stack[i])
    for i in range(M):
        if i not in used:
            used.add(i)
            ch.append(i)
    
    return stack == ch

N, M = map(int, readline().split())
Q = int(readline())
A = list(map(lambda x: int(x)-1, readline().split()))

ans = 'Yes'
if not check1(A):
    if not check2(A):
        ans = 'No'
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
def inpl(): return [int(i) for i in input().split()]
import numpy as np
N, x = inpl()
a = np.array(inpl())
b = np.copy(a)
for i in range(N**2-N):
    if a[i%N]+x < a[(i+1)%N]:
        a[(i+1)%N] = a[i%N]+x
        b[(i+1)%N] = b[i%N]
print(np.max(a-b)+sum(b))


Fixed submission:
def inpl(): return [int(i) for i in input().split()]
import numpy as np
N, x = inpl()
a = np.array(inpl())
b = np.copy(a)
ans = float('inf') 
for i in range(N):
    c = np.roll(a,i)
    b = np.minimum(b,c)
    ans = min(ans, sum(b)+i*x)
print(ans)
Buggy python submission (verdict: Runtime Error):
def inpl(): return [int(i) for i in input().split()]
def hmd(a, b):
    ctr = -1
    while H[ctr+1][a] < b:
        ctr += 1
    vn = H[ctr][a]
    if (vn == b and ctr == 0) or ctr == -1:
        return 1
    return 2**ctr + hmd(vn,b)
N = int(input())
x = inpl() + [10**10]
L = int(input())
H = []
G = [N-1]*N
b = 0
for a in range(N):
    while x[b+1] - x[a] <= L:
        if b == N-1:
            break
        b += 1
    G[a] = b
H.append(G)
while G[0] != N-1:
    G = [G[i] for i in G]
    H.append(G)
H.append([10**10]*N)
Q = int(input())
for _ in range(Q):
    a, b = sorted(inpl())
    print(hmd(a-1,b-1))

Fixed submission:
from collections import defaultdict
H = defaultdict(lambda: 0)
H[0] = 1
def inpl(): return [int(i) for i in input().split()]
N, A = inpl()
x = inpl()
x = [i-A for i in x]
H[0]= 1
for i in x:
    for ni,nv in H.copy().items():
        H[ni+i] += nv
print(H[0]-1)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
from itertools import accumulate
readline = sys.stdin.readline
MOD = 10**9+7

N, C = map(int, readline().split())
A = [0] + list(map(int, readline().split()))
B = [0] + list(map(int, readline().split()))

acsq = [list(accumulate([pow(i, j, MOD) for i in range(max(B)+1)])) for j in range(C+1)]
dp = [[0]*(C+1) for _ in range(N+1)]
dp[0][0] = 1
for i in range(1, N+1):
    a, b = A[i], B[i]
    for c in range(C+1):
        res = 0
        for j in range(c+1):
            res = (res + (acsq[c-j][b] - acsq[c-j][a-1])*dp[i-1][j]) % MOD
        dp[i][c] = res
print(dp[N][C])

Fixed submission:
from itertools import accumulate
N, C = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
mod = 10**9 + 7
X = [list(accumulate([pow(x, d, mod) for x in range(401)])) for d in range(C+1)]
dp = [[0]*(C+1) for _ in range(N+1)]
dp[0][0] = 1
for i in range(1, N+1):
    for d in range(C+1):
        dp[i][d] = sum([dp[i-1][d-k]*(X[k][B[i-1]] - X[k][A[i-1]-1]) for k in range(d+1)])%mod
        
print(dp[-1][-1])

Buggy python submission (verdict: Runtime Error):
for _ in range(test_case):
import sys
from itertools import accumulate
readline = sys.stdin.readline
MOD = 10**9+7

N, C = map(int, readline().split())
A = [0] + list(map(int, readline().split()))
B = [0] + list(map(int, readline().split()))

acsq = [list(accumulate([pow(i, j, MOD) for i in range(max(B)+1)])) for j in range(C+1)]
dp = [[0]*(C+1) for _ in range(N+1)]
dp[0][0] = 1
for i in range(1, N+1):
    a, b = A[i], B[i]
    for c in range(C+1):
        res = 0
        for j in range(c+1):
            res = (res + (acsq[c-j][b] - acsq[c-j][a-1])*dp[i-1][j]) % MOD
        dp[i][c] = res
print(dp[N][C])

Fixed submission:
from itertools import accumulate
N, C = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
mod = 10**9 + 7
X = [list(accumulate([pow(x, d, mod) for x in range(401)])) for d in range(C+1)]
dp = [[0]*(C+1) for _ in range(N+1)]
dp[0][0] = 1
for i in range(1, N+1):
    for d in range(C+1):
        dp[i][d] = sum([dp[i-1][d-k]*(X[k][B[i-1]] - X[k][A[i-1]-1]) for k in range(d+1)])%mod
        
print(dp[-1][-1])
Buggy python submission (verdict: Runtime Error):
N, X = [int(i) for i in input().split()]
import math

gcd = math.gcd(N, X)
print(gcd*(N//gcd-1)*3)

Fixed submission:
N, X = [int(i) for i in input().split()]
def gcd(a,b):
    if b == 0:
        return a
    return gcd(b,a%b)
scale = gcd(N, X)
print(scale*(N//scale-1)*3)
Buggy python submission (verdict: Time Limit Exceeded):
N,K = map(int, input().split())

MOD = 998244353

PAT = []
for _ in range(K):
  l,r = map(int, input().split())
  PAT.append((l,r))
  
IMOS = [0] * (2*N+10)
IMOS[1] = 1
for i in range(0,N):
  for l,r in PAT:
    IMOS[i+l] += IMOS[i]
    IMOS[i+r+1] -= IMOS[i]
  #print(i, IMOS)
  IMOS[i+1] += IMOS[i]
  IMOS[i+1] % MOD
  
print((IMOS[N] - IMOS[N-1]) % MOD)
    

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

MOD = 998244353

PAT = []
for _ in range(K):
  l,r = map(int, input().split())
  PAT.append((l,r))
  
IMOS = [0] * (N+10)
IMOS[1] = 1
for i in range(0,N):
  if IMOS[i] == 0:
    continue
  for l,r in PAT:
    if i+l > N+1:
      continue
    IMOS[i+l] += IMOS[i]
    if i+r-1 > N+1:
      continue
    IMOS[i+r+1] -= IMOS[i]
  #print(i, IMOS)
  IMOS[i+1] += IMOS[i]
  IMOS[i+1] %= MOD
  
print((IMOS[N] - IMOS[N-1]) % MOD)
Buggy python submission (verdict: Time Limit Exceeded):
K = int(input())
hist = set()

INF = 10**8

w = 0
for i in range(INF):
  w += 7 * pow(10,i,K)
  w %= K
  if w == 0:
    print(i+1)
    break
  else:
    if w in hist:
      print(-1)
      break
    else:
      hist.add(w)
      
#print(hist)


Fixed submission:
K = int(input())
hist = set()

INF = 10**8

w = 0
for i in range(INF):
  w += 7 * pow(10,i,K)
  w %= K
  if w == 0:
    print(i+1)
    break
  else:
    if w in hist:
      print(-1)
      break
    else:
      hist.add(w)
      
#print(hist)
Buggy python submission (verdict: Runtime Error):
K = int(input())
S = input()
N = len(S)
mod = int(1e9+7)

### 123
### a1bb2ccc3dddd 10文字インサート
# pow(25,6) * pow(26,4) * 8C2
# (3はfixで、それより前の8mojiから1/2を入れる場所を決める）
# これを3の位置でループする（1-indexで 3<=i<=N)

# 123dddddddddd
# pow(25,0) * pow(26,10) * 2C2(1)
# 12x3ddddddddd
# pow(25,1) * pow(26,9) * 3C2( = 2C2 * 3 / 1)
# 12xx3dddddddd
# pow(25,2) * pow(26,8) * 4C2( = 3C2 * 4 / 2)
# ...
# 12xxxxxxxxxx3
# pow(25,10) * pow(26,0) * 12C2( = 11C2 * 12 / 10)

# 5C5, 6C5, 7C5 1, 6, 21, 56

wk = pow(26,K,mod)
inv26 = pow(26,-1,mod)

ans = wk
for i in range(1,K+1):
  wk = (wk * 25 * inv26) % mod
  wk = (wk * (N-1+i) * pow(i,-1,mod) % mod)
  ans = (ans + wk)%mod
    
print(ans)


Fixed submission:
K = int(input())
S = input()
N = len(S)
mod = int(1e9+7)

### 123
### a1bb2ccc3dddd 10文字インサート
# pow(25,6) * pow(26,4) * 8C2
# (3はfixで、それより前の8mojiから1/2を入れる場所を決める）
# これを3の位置でループする（1-indexで 3<=i<=N)

# 123dddddddddd
# pow(25,0) * pow(26,10) * 2C2(1)
# 12x3ddddddddd
# pow(25,1) * pow(26,9) * 3C2( = 2C2 * 3 / 1)
# 12xx3dddddddd
# pow(25,2) * pow(26,8) * 4C2( = 3C2 * 4 / 2)
# ...
# 12xxxxxxxxxx3
# pow(25,10) * pow(26,0) * 12C2( = 11C2 * 12 / 10)

# 5C5, 6C5, 7C5 1, 6, 21, 56

wk = pow(26,K,mod)
inv26 = pow(26,-1,mod)

ans = wk
for i in range(1,K+1):
  wk = (wk * 25 * inv26) % mod
  wk = (wk * (N-1+i) * pow(i,-1,mod) % mod)
  ans = (ans + wk)%mod
    
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
from collections import Counter
N = int(input())
A = list(map(int, input().split()))

A.sort()
So = [True] * N

for i in range(N):
  if not So[i]:
    if i>0 and A[i-1] == A[i]:
      So[i-1] = False
    continue
  val = A[i]
  for j in range(i+1,N):
    if not So[i]:
      continue
    if A[j] % val == 0:
      So[j] = False
      
      
ans = 0
for i in range(N):
  if So[i]:
    ans += 1
#print(So)
print(ans)

Fixed submission:
import sys
import numpy as np
#from numba import njit
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
#@njit('(i4[::1],)', cache=True)
def solve(A):
    count = np.zeros(10**6 + 10, np.int32)
    for x in A:
        if count[x] > 1:
            continue
        count[::x] += 1
    ret = 0
    for x in A:
        ret += count[x] == 1
    return ret

A = np.array(read().split(), np.int32)[1:]
 
print(solve(A))

Buggy python submission (verdict: Time Limit Exceeded):
from collections import Counter
N = int(input())
A = list(map(int, input().split()))

A.sort()
ans = 0

for i in range(N):
  flg = True
  for j in range(N):
    if i == j:
      continue
    if A[i] < A[j]:
      break
    elif A[i] % A[j] == 0:
      flg = False
      break
  if flg:
    ans += 1
      

print(ans)

Fixed submission:
import sys
import numpy as np
#from numba import njit
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
#@njit('(i4[::1],)', cache=True)
def solve(A):
    count = np.zeros(10**6 + 10, np.int32)
    for x in A:
        if count[x] > 1:
            continue
        count[::x] += 1
    ret = 0
    for x in A:
        ret += count[x] == 1
    return ret

A = np.array(read().split(), np.int32)[1:]
 
print(solve(A))
Buggy python submission (verdict: Time Limit Exceeded):
N,K = map(int, input().split())
A = list(map(int, input().split()))

for cnt in range(K):
  B = [0] * (N+1)
  for i in range(N):
    bright = A[i]
    l = max(i-bright,0)
    r = min(i+bright+1, N)
    B[l] += 1
    B[r] -= 1
  for i in range(N):
    B[i+1] += B[i]
  
  A = B[:-1]
  #print(A)
  if min(A) == N:
    #print(cnt)
    break
    
print(" ".join(map(str,A)))



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

for cnt in range(K):
  B = [0] * (N+1)
  for i in range(N):
    bright = A[i]
    l = max(i-bright,0)
    r = min(i+bright+1, N)
    B[l] += 1
    B[r] -= 1
  for i in range(N):
    B[i+1] += B[i]
  
  A = B[:-1]
  #print(A)
  if min(A) == N:
    #print(cnt)
    break
    
print(" ".join(map(str,A)))
Buggy python submission (verdict: Runtime Error):
A,B = list(map(int, input().split()))
print(int(A*B))

Fixed submission:
from decimal import *
A,B = list(map(Decimal, input().split()))
print(int(A*B))
Buggy python submission (verdict: Time Limit Exceeded):
N,S = list(map(int, input().split()))
A = list(map(int, input().split()))
mod = 998244353

dp = [[0 for i in range(S+1)] for _ in range(N+1)]
# dp[i][j] Aiまでを使って、合計jを作る作り方
dp[0][0] = 1

for i in range(1,N+1):
  a = A[i-1]
  for j in range(S+1):
    dp[i][j] += dp[i-1][j] * 2
    dp[i][j] %= mod
    if j+a <= S :
      dp[i][j+a] += dp[i-1][j]
      dp[i][j+a] %= mod
print(dp[N][S])

Fixed submission:
N,S = list(map(int, input().split()))
A = list(map(int, input().split()))
mod = 998244353

dp = [[0 for i in range(S+1)] for _ in range(N+1)]
# dp[i][j] Aiまでを使って、合計jを作る作り方
dp[0][0] = 1

for i in range(1,N+1):
  a = A[i-1]
  for j in range(S+1):
    dp[i][j] += dp[i-1][j] * 2
    dp[i][j] %= mod
    if j+a <= S :
      dp[i][j+a] += dp[i-1][j]
      dp[i][j+a] %= mod
print(dp[N][S])
Buggy python submission (verdict: Runtime Error):
import numpy as np
from itertools import product
N,M,X = list(map(int, input().split()))
C = [0] * N
A = []

for i in range(N):
  wk = list(map(int, input().split()))
  C[i] = wk[0]
  A.append(wk[1:])

C = np.array(C)
A = np.array(A)

ans = -1
for pt in product([0,1], repeat = N):
  p = np.array(pt)  
  #print(C.dot(p))
  #print(p.dot(A))
  rikai = p.dot(A)
  if min(rikai) >= X:
    ans = C.dot(p) if ans == -1 else min(ans, C.dot(p))
  
print(ans)

Fixed submission:
import numpy as np
from itertools import product
N,M,X = list(map(int, input().split()))
C = [0] * N
A = []

for i in range(N):
  wk = list(map(int, input().split()))
  C[i] = wk[0]
  A.append(wk[1:])

C = np.array(C)
A = np.array(A)

ans = -1
for pt in product([0,1], repeat = N):
  p = np.array(pt)  
  #print(C.dot(p))
  #print(p.dot(A))
  rikai = p.dot(A)
  if min(rikai) >= X:
    ans = C.dot(p) if ans == -1 else min(ans, C.dot(p))
  
print(ans)