Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

from collections import deque
h, w = map(int, input().split())
c_h, c_w = map(int, input().split())
d_h, d_w = map(int, input().split())
#スタートとゴールの座標を設定
start_h = c_h - 1
start_w = c_w - 1
goal_h = d_h - 1
goal_w = d_w - 1
#迷路の読み込み
maze = [input() for _ in range(h)]
inf = float("inf")
dist = [[inf] * w for _ in range(h)]



def bfs(x, y):
    dist[x][y] = 0
    q_walk = deque()
    q_warp = deque()
    q_walk.append((x, y))
    while len(q_walk) > 0:
        x, y = q_walk.popleft() 
        q_warp.append((x, y))
        d = dist[x][y]
        for dx, dy in [(0,1),(1,0),(0,-1),(-1,0)]:
            nx = x + dx
            ny = y + dy 
            if not 0 <= nx < h or not 0 <= ny < w:
                continue
            if maze[nx][ny] == "#":
                continue
            if dist[nx][ny] <= d:
                continue
            dist[nx][ny] = d           
            q_walk.append((nx, ny))
        if len(q_walk) == 0:
            while len(q_warp) > 0:
                x2, y2 = q_warp.popleft()
                for dxx in range(-2, 3):
                    for dyy in range(-2, 3):
                        nxx = x2 + dxx
                        nyy = y2 + dyy 
                        if not 0 <= nxx < h or not 0 <= nyy < w:
                            continue
                        if maze[nxx][nyy] == "#":
                            continue
                        if dist[nxx][nyy] <= d+1:
                            continue
                        dist[nxx][nyy] = d+1
                        q_walk.append((nxx, nyy))
                



bfs(start_h, start_w)
if dist[goal_h][goal_w] == inf:
    print("-1")
else:
    print(dist[goal_h][goal_w])    

### FIXED CODE ###

from collections import deque
h, w = map(int, input().split())
c_h, c_w = map(int, input().split())
d_h, d_w = map(int, input().split())
#スタートとゴールの座標を設定
start_h = c_h - 1
start_w = c_w - 1
goal_h = d_h - 1
goal_w = d_w - 1
#迷路の読み込み
maze = [input() for _ in range(h)]
inf = float("inf")
dist = [[inf] * w for _ in range(h)]



def bfs(x, y):
    dist[x][y] = 0
    q = deque()
    q.append((x, y))
    while q:
        x, y = q.popleft() 
        d = dist[x][y]
        for dx, dy in [(0,1),(1,0),(0,-1),(-1,0)]:
            nx = x + dx
            ny = y + dy 
            if not 0 <= nx < h or not 0 <= ny < w:
                continue
            if maze[nx][ny] == "#":
                continue
            if dist[nx][ny] <= d:
                continue
            dist[nx][ny] = d           
            q.appendleft((nx, ny))

        for dxx in range(-2, 3):
            for dyy in range(-2, 3):
                 nxx = x + dxx
                 nyy = y + dyy 
                 if not 0 <= nxx < h or not 0 <= nyy < w:
                    continue
                 if maze[nxx][nyy] == "#":
                    continue
                 if dist[nxx][nyy] <= d+1:
                    continue
                 dist[nxx][nyy] = d+1
                 q.append((nxx, nyy))
                



bfs(start_h, start_w)
if dist[goal_h][goal_w] == inf:
    print("-1")
else:
    print(dist[goal_h][goal_w])
### BUGGY CODE ###

#入力処理
A, B, M = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
waribiki=[[0]*B]*A
for i in range(M):
    x_input, y_input, c_input = map(int, input().split())
    if waribiki[x_input-1][y_input-1]<c_input:
        waribiki[x_input-1][y_input-1]=c_input

#処理
inexpensive=200000
for i in range(A):
    for j in range(B):
        if (int(a[i])+int(b[j]))-waribiki[i][j] < inexpensive:
            inexpensive = (int(a[i])+int(b[j]))-waribiki[i][j]

print(inexpensive) 

### FIXED CODE ###

#入力処理
A, B, M = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
kingaku=[]
for i in range(M):
    x_input, y_input, c_input = map(int, input().split())
    kingaku.append(a[x_input-1]+b[y_input-1]-c_input)
kingaku.append(min(a)+min(b))

print(min(kingaku))
### BUGGY CODE ###

A,B,C,D = map(int,input().split())
count = 0
for i in range(A,B+1):
  if i%C != 0 and i%D != 0:
    count += 1
    i += 1
  else:
    i += 1
print(count)

### FIXED CODE ###

from fractions import gcd
def lcm(x, y):
    return (x * y) // gcd(x, y)

A,B,C,D = map(int,input().split())
all_count = B-A+1
c_count = B//C - (A-1)//C
d_count = B//D - (A-1)//D
cd_count = B//lcm(C,D) - (A-1)//lcm(C,D)
ans = all_count - c_count - d_count + cd_count
print(ans)
### BUGGY CODE ###

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

coun = [];

for i in range(n):
  num = A.count(i+1);
  coun.append(num);

for j in coun:
  print(j);
  

### FIXED CODE ###

import collections

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

ans = [0] * n;

c = collections.Counter(A)
key = list(c.keys());
value = list(c.values());

for i in range(len(key)):
    ans[key[i]-1] = value[i];
  
for a in ans:
  print(a);
### BUGGY CODE ###

import heapq 
N, K = [int(x) for x in input().split()]
A = sorted([int(x) for x in input().split()])
F = sorted([int(x) for x in input().split()], reverse=True)
h = []
if (sum(A) <= K):
    print(0)
else:
    for a, f in zip(A, F):
        heapq.heappush(h, (-a*f, [a, f]))
    for i in range(K):
        before = heapq.heappop(h)
        a, f = before[1]
        heapq.heappush(h, (-(a-1)*f, [a-1, f]))
    print(-1 * heapq.heappop(h)[0])


### FIXED CODE ###

N, K = [int(x) for x in input().split()]
A = sorted([int(x) for x in input().split()])
F = sorted([int(x) for x in input().split()], reverse=True)
lb = 0
ub = 10 ** 12
def isPossible(M):
    cnt = 0
    # a = 4 , f = 5 のとき a*f = 20
    # M = 30 => そのままでOK
    # M = 9 => (20-9+4)//5
    for a, f in zip(A, F):
        if (M >= a*f): continue
        cnt += (a*f - M + (f-1)) // f
    return cnt <= K

for i in range(100):
    mid = (lb + ub) // 2
    if (isPossible(mid)):
        ub = mid
    else:
        lb = mid
print(ub)
### BUGGY CODE ###

import collections
N = int(input())
A = list(map(int,input().split()))
counter = collections.Counter(A)
B = list(set(A))
count = 0
for i in range(len(B)):
    if counter[B[i]]>1:
        continue
    if B[i]==1:
        count += 1
        continue
    else:
        check = 0
        for j in range(1,int(B[i]**0.5)+1):
            if (j != 1 and B[i]%j==0 and (j in counter or B[i]//j in counter)) or (j==1 and j in counter):
                check += 1
                break
        if check==0:
            count += 1
print(count)
    

### FIXED CODE ###

import collections
N = int(input())
A = list(map(int,input().split()))
S = set()
D = set()
for a in A:
    if a in S:
        D.add(a)
    else:
        S.add(a)
M = max(S)
A = [0]*(M+1)
for s in S:
    if s in D:
        A[s] += 1
    for i in range(2*s,M+1,s):
        A[i]+=1
count = 0
for s in S:
    if A[s]==0:
        count += 1
print(count)
### BUGGY CODE ###

a, b, c, d = list(map(int, input().split()))
turn = True
while True:
  if turn:
    c -= b
    if c <= 0:
      print("Yes")
  else:
    a -= d
    if a <= 0:
      print("No")
  turn ^= True

### FIXED CODE ###

a, b, c, d = list(map(int, input().split()))
turn = True
while True:
  if turn:
    c -= b
    if c <= 0:
      print("Yes")
      import sys
      sys.exit()
  else:
    a -= d
    if a <= 0:
      print("No")
      import sys
      sys.exit()
  turn ^= True
### BUGGY CODE ###

N,K=map(int,input().split())
A=N
while A>=K/2:
    A=min(abs(A-K),abs(A+K))
print(A)

### FIXED CODE ###

N,K=map(int,input().split())
B=int(N/K)
A=abs(N-(B-1)*K)
while A>=K/2:
    A=min(abs(A-K),abs(A+K),A)
print(A)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

_n, _k = map(int, input().split())
_a = input()[:-1]
_f = input()[:-1]
alist = [item for item in map(int, _a.split())]
flist = [item for item in map(int, _f.split())]


def chker(costs, diffs, max_k):
    if sum(costs) <= max_k:
        print(0)
        return

    costs.sort()
    diffs.sort(reverse=True)
    sclist = sorted([[item1, item2, item1 * item2] for item1, item2 in zip(costs, diffs)], key=lambda x:x[2], reverse=True)
    k = max_k
    while k > 0:
        sclist[0][0] = sclist[0][0] - 1
        if sclist[0][0] == 0:
            sclist = sclist[1:]
        else:
            sclist[0][2] = sclist[0][0] * sclist[0][1]
            sclist.sort(key=lambda x:x[2], reverse=True)

        k -= 1

    print(sclist[0][2])


chker(alist, flist, _k)


### FIXED CODE ###

import numpy as np
import sys
input = sys.stdin.readline

_n, _k = map(int, input().split())
alist = [int(item) for item in input().split()]
flist = [int(item) for item in input().split()]


def chker(costs, diffs, max_k):
	costs = np.sort(costs)[::-1]
	diffs = np.sort(diffs)
	
	_min, _max = 0, 10 ** 12
	while _min < _max:
		_mid = (_min + _max) // 2
		cnt = costs - _mid // diffs
		if cnt[cnt > 0].sum() <= max_k:
			_max = _mid
		else:
			_min = _mid + 1


	print(_min)


chker(alist, flist, _k)
### BUGGY CODE ###

n = int(input())
l = list(map(int, input().split()))
l.sort(reverse = True)

ans = 0
for i in range(n):
    for j in range(i+1, n):
        for k in range(j+1, n):
            if l[i] < l[j] + l[k]:
                ans += 1
            else:
                break

print(ans)

### FIXED CODE ###

import bisect

n = int(input())
l = list(map(int, input().split()))
l.sort()

ans = 0
for i in range(n):
    for j in range(i+1, n):
        x = bisect.bisect_left(l, l[i] + l[j])
        ans += x - j - 1
print(ans)
### BUGGY CODE ###

x,y,a,b,c = map(int,input().split())
p = sorted(list(map(int,input().split())),reverse=True)
q = sorted(list(map(int,input().split())),reverse=True)
r = sorted(list(map(int,input().split())),reverse=True)

z = sorted(p+q+r,reverse=True)
ans = 0
c = 0
for i in z:
    if x+y-c==0:
        break
    elif i in p and x>0:
        ans+=i
        p.pop(0)
        x -= 1
    elif i in q and y>0:
        ans += i
        q.pop(0)
        y -= 1
    elif i in r and x+y-c>0:
        ans += i
        c += 1
print(ans)

### FIXED CODE ###

x,y,a,b,c = map(int,input().split())
p = sorted(list(map(int,input().split())))
q = sorted(list(map(int,input().split())))
r = sorted(list(map(int,input().split())))

z = sorted(p+q+r,reverse=True)
ans = 0
c = 0
for i in z:
    if x+y-c==0:
        break
    elif p and i == p[-1] and x>0:
        ans+=i
        p.pop()
        x -= 1
    elif q and i == q[-1] and y>0:
        ans += i
        q.pop()
        y -= 1
    elif i == r[-1] and x+y-c>0:
        ans += i
        r.pop()
        c += 1
print(ans)
### BUGGY CODE ###

s=input()
k=int(input())
n=len(s)
a=[]
for i in range(n):
  for j in range(1,k+1):
    a=set(a)|set([s[i:i+j]])
a=sorted(a)
print(a[k-1])

### FIXED CODE ###

s=input()
k=int(input())
n=len(s)
a=set([])
for i in range(n):
  for j in range(1,k+1):
    a.add(s[i:i+j])
a=sorted(a)
print(a[k-1])
### BUGGY CODE ###

n=int(input())
cnt=0
for i in range(n):
    cnt +=i
print(cnt)

### FIXED CODE ###

n=int(input())
print((n-1)*(n-2)//2+(n-1))
### BUGGY CODE ###

import math
from functools import reduce
K=int(input())
gcd=0.
for i in range(K):
    for j in range(K):
        for k in range(K):
            gcd+=reduce(math.gcd,[i+1,j+1,k+1])
print(int(gcd))

### FIXED CODE ###

import math
from functools import reduce
from itertools import product
K=int(input())
gcd=0.
for i in range(K):
    for j in range(K):
        a=math.gcd(i+1,j+1)
        for k in range(K):
            gcd+=math.gcd(a,k+1)
print(int(gcd))
### BUGGY CODE ###

# D

N = int(input())
A = [int(x) for x in input().split()]

# abs_list = sorted([abs(x) for x in A])[::-1]

for i in range(N-1):
    if A[i] < 0:
        A[i] *= -1
        A[i+1] *= -1
    
tmp = [sum(A)]
for i in reversed(range(0, N-1)):
    A[i] *= -1
    A[i+1] *= -1
    tmp.append(sum(A))
    
print(max(tmp))

### FIXED CODE ###

N = int(input())
A = [int(x) for x in input().split()]

abs_list = sorted([abs(x) for x in A])[::-1]

for i in range(N-1):
    if A[i] < 0:
        A[i] *= -1
        A[i+1] *= -1

if abs(min(A)) != min(abs_list):
    A[A.index(min(A))] *= -1
    A[A.index(min(abs_list))] *= -1
    
print(sum(A))
### BUGGY CODE ###

# C - pushpush
n = int(input())
a = list(map(int, input().split()))
b = []
for i in range(n):
    if n % 2 == 0:
        if i % 2 == 0:
            b.append(a[i])
        else:
            b.insert(0, a[i])
    else:
        if i % 2 != 0:
            b.append(a[i])
        else:
            b.insert(0, a[i])

for s in b:
    print(s, end=" ")

### FIXED CODE ###

# C - pushpush
from collections import deque
n = int(input())
a = list(map(int, input().split()))
b = deque()
for i in range(n):
    if n % 2 == 0:
        if i % 2 ==0:
            b.append(a[i])
        else:
            b.appendleft(a[i])
    else:
        if i % 2 !=0:
            b.append(a[i])
        else:
            b.appendleft(a[i])

print(*b, end=" ")
### BUGGY CODE ###

s = list(input())

ans = 0
i = 0
while i <= len(s)-2:
    if s[i] == '0' and s[i+1] == '1':
        del s[i+1]
        del s[i]
        ans += 2
        i = 0
    elif s[i] == '1' and s[i+1] == '0':
        del s[i+1]
        del s[i]
        ans += 2
        i = 0
    else:
        i += 1
print(ans)


### FIXED CODE ###

S = input()
print(min(S.count("0"),S.count("1"))*2)
### BUGGY CODE ###

from collections import deque, defaultdict

N, X, Y = map(int, input().split())
# 全探索でいけるのでは？
# 有向グラフとしてN回幅優先すれば良いのでは？
tree = [[] for _ in range(N)]
for i in range(N-1):
    tree[i].append(i+1)
    tree[i+1].append(i)
tree[X-1].append(Y-1)
tree[Y-1].append(X-1)
ans = defaultdict(int)
# 更新されない時はqに追加しない
for i in range(N):
    distant = [float("inf")]*N
    q = deque([i])  # 始まりのノード
    distant[i] = 0
    while len(q):
        # vは数字, 親のノードのインデックス
        v = q.pop()
        for e in tree[v]:
            if distant[e] < distant[v]+1:  # 到達済みなら次のノードへ
                continue
            distant[e] = min(distant[v]+1, distant[e])
            q.append(e)
    for d in distant:
        ans[d] += 1
for i in range(1, N):
    print(ans[i]//2)


### FIXED CODE ###

from collections import deque, defaultdict

N, X, Y = map(int, input().split())
# 全探索でいけるのでは？
# 有向グラフとしてN回幅優先すれば良いのでは？
tree = [[] for _ in range(N)]
for i in range(N-1):
    tree[i].append(i+1)
    tree[i+1].append(i)
tree[X-1].append(Y-1)
tree[Y-1].append(X-1)
ans = defaultdict(int)
q = deque()
# 更新されない時はqに追加しない
for i in range(N):
    distant = [N]*N
    q.append(i)  # 始まりのノード
    distant[i] = 0
    while len(q):
        # vは数字, 親のノードのインデックス
        v = q.pop()
        for e in tree[v]:
            if distant[e] < distant[v]+1:  # 到達済みなら次のノードへ
                continue
            distant[e] = distant[v]+1
            q.append(e)
    for d in distant:
        ans[d] += 1
for i in range(1, N):
    print(ans[i]//2)
### BUGGY CODE ###

N, K = map(int, input().split())
al = list(map(int, input().split()))

route = [1]
for i in range(K):
    next_town = al[route[i] - 1]
    if route.count(next_town) ==1 :
        loop_start = route.index(next_town)
        loop_end = len(route)
        loop_length = loop_end - loop_start
        if K >= loop_end:
            amari = (K - loop_start) % loop_length
            ans = route[loop_start + amari]
            # print(route)
            print(ans)
            exit()
    else:
        route.append(next_town)

ans = route[-1]
print(ans)


### FIXED CODE ###

from collections import defaultdict


def inpl():
    return list(map(int, input().split()))


N, K = inpl()
aa = inpl()

s = 1

route = [s]
ed = set([s])

for i in range(1, K + 1):
    s = aa[s - 1]
    if s in ed:
        Li = route.index(s)
        Ri = len(route)
        idx = Li + (K - Li) % (Ri - Li)
        print(route[idx])
        break
    else:
        route.append(s)
        ed.add(s)
        continue
else:
    print(s)
### BUGGY CODE ###

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

# n,m = map(int,input().split())

# a = list(map(int, input().split()))  # n個の文字列がリストに格納される

N = int(input())

A = list(map(int, input().split()))  # n個の文字列がリストに格納される

for i in range(N-1):
    print(A.count(i+1))
    while i+1 in A:
        A.remove(i+1)

print('0')


### FIXED CODE ###

N = int(input())

A = list(map(int, input().split()))  # n個の文字列がリストに格納される

ans = [0] * N

for a in A:
    ans[a-1] += 1

print(*ans,sep='\n')
### BUGGY CODE ###

class UnionFind():
  def __init__(self,n):
    self.parents = [-1]*n
  
  def find(self,x):
    if self.parents[x] < 0:
      return x
    
    self.parents[x] = self.find(self.parents[x])
    return self.parents[x]
  
  def union(self,x,y):
    x = self.find(x)
    y = self.find(y)
    
    if x==y:
      return
    
    if self.parents[x]>self.parents[y]:
      x,y=y,x
      
    self.parents[x] += self.parents[y]
    self.parents[y] = x

import numpy as np

N,M=map(int,input().split())
uf = UnionFind(N+1)

ans_max=(N)*(N-1)//2
cal=[]
A=[]
B=[]

for i in range(M):
  a,b=map(int,input().split())
  A.append(a)
  B.append(b)

for i in range(M):
  temp=np.array(uf.parents)
  temp_sum=sum(abs(temp[temp<0])*(abs(temp[temp<0])-1)//2)
  cal.append(temp_sum)
  uf.union(A[M-1-i],B[M-1-i])  

for x in cal[::-1]:
  print(ans_max-x)

### FIXED CODE ###

class UnionFind():
  def __init__(self,n):
    self.parents = list(range(n))
    self.size = [1]*n
  
  def find(self,x):
    if self.parents[x] == x:
      return x
	
    self.parents[x] = self.find(self.parents[x])
    return self.parents[x]
  
  def union(self,x,y):
    x = self.find(x)
    y = self.find(y)
    
    if x==y:
      return
    
    if self.size[x]<self.size[y]:
      x,y=y,x
	
    self.size[x]+=self.size[y]
    self.parents[y] = x
  
  def same(self,x,y):
    return self.find(x) == self.find(y)
  
  def sizeofset(self,x):
    return self.size[self.find(x)]


N,M=map(int,input().split())
uf = UnionFind(N+1)

cnt=(N)*(N-1)//2
L=[[int(x) for x in input().split()] for _ in range(M)]
ans=[]

for a,b in L[::-1]:
  ans.append(cnt)
  if not uf.same(a,b):
    cnt -= uf.sizeofset(a)*uf.sizeofset(b)
    uf.union(a,b)

for x in ans[::-1]:
  print(x)
### BUGGY CODE ###

Q = int(input())
ma = 10 ** 5 + 1
dp = [0] * ma
dp[2] = 1

for i in range(3,ma,2):
    if dp[i] == 0:
        dp[i] = 1
        if dp[(i + 1) // 2] == 1 or dp[(i + 1) // 2] == 2:
            dp[i] = 2
        for j in range(i * 2,ma,i):
            dp[j] = 3

for _ in range(Q):
    l,r = map(int,input().split())
    print(dp[l:r+1].count(2))

### FIXED CODE ###

import sys

def input():
    return sys.stdin.readline().strip()

def main():

    Q = int(input())
    ma = 10 ** 5 + 1
    dp = [0] * ma
    dp[2] = 1

    for i in range(3,ma,2):
        if dp[i] == 0:
            dp[i] = 1
            if dp[(i + 1) // 2] == 1 or dp[(i + 1) // 2] == 2:
                dp[i] = 2
            for j in range(i * 2,ma,i):
                dp[j] = 3

    ruiseki = [0] * ma

    for i in range(1,ma):
        if dp[i] == 2:
            ruiseki[i] = ruiseki[i-1] + 1
        else:
            ruiseki[i] = ruiseki[i-1]

    for _ in range(Q):
        l,r = map(int,input().split())
        print(ruiseki[r] - ruiseki[l-1])

if __name__ == "__main__":
    main()
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
import sys
import math
def setwise_coprime(a):
  ans=a[0]
  for i in range(1,n):
    ans=math.gcd(ans,a[i])
  return ans
ruiseki=1
for i in range(n):
  ruiseki=ruiseki*a[i]

for i in range(n):
    num=math.gcd(a[i],ruiseki//a[i])
    if num!=1:
      if setwise_coprime(a)==1:
        print("setwise coprime")
        sys.exit()
      else:
        print("not coprime")
        sys.exit()
print("pairwise coprime")

        












### FIXED CODE ###

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

import sys
import math
def setwise_coprime(a):
  ans=a[0]
  for i in range(1,n):
    ans=math.gcd(ans,a[i])
  return ans

#エラストテネスのふるい
def create_sieve(n):
  sieve=[0]*(n+1)
  for i in range(2,n+1):
    if sieve[i]==0:
      for j in range(i*i,n+1,i):
        sieve[j]=i
  return sieve

#高速素因数分解
def fast_factorization(n, sieve):
  prime={}
  while n>1:
    p=sieve[n]
    #nが素数の場合
    if p==0:
      prime[n]=prime.get(n,0)+1
      break
    #nが素数ではない場合
    else:
      prime[p]=prime.get(p,0)+1
      n=n//p
  return prime

check=set()
if setwise_coprime(a)==1:
  #素因数のダブリをcheck
  sieve=create_sieve(10**6)
  for i in range(n):
    if a[i]!=1:
      s=fast_factorization(a[i], sieve)
      for i in s:
        if i in check:
          print("setwise coprime")
          sys.exit()
        else:
          check.add(i)
  print("pairwise coprime")    
else:
  print("not coprime")
### BUGGY CODE ###

import sys

for line in sys.stdin:
    n = int(line)
    l = range(2,n+1)
    i = 2
    while i * i <= n: 
        l = filter(lambda x: x == i or x % i != 0, l)
        i = i + 1

    print len(l)

### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys

def prime_list(n):
    l = range(2,n+1)
    i = 2
    while i * i <= n: 
        l = filter(lambda x: x == i or x % i != 0, l)
        i = i + 1
    return l

def mark(s, x):
    for i in xrange(x + x, len(s), x):
        s[i] = False

def sieve(n):
    s = [True] * n
    for x in xrange(2, int(n**0.5) + 1):
        if s[x]: mark(s, x)
    return [i for i in xrange(0,n) if s[i] and i > 1]

if __name__ == '__main__':
    l = sieve(999999)
    for line in sys.stdin:
        n = int(line)
        print len([x for x in l if x <= n])
### BUGGY CODE ###

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

broken_step = []
for _ in range(M):
    broken_step.append(int(input()))
    
import sys
sys.setrecursionlimit(10000000)

mod = 1000000007

memo = [-1] * (N+1)

if 0 not in broken_step:
    memo[0] = 1
elif N == 0 and N in broken_step:
    memo[0] = 0

if 1 not in broken_step:
    memo[1] = 1
elif 1 in broken_step:
    memo[1] = 0

def step_memo(N):
    
    try:
        broken_step.remove(N)
        memo[N] = 0
        return 0
    except ValueError:
        pass
        
    #if N in broken_step:
    #    broken_step.remove(N)
    #    memo[N] = 0
    #    return 0
        
    if memo[N] != -1:
        return memo[N]
    
    memo[N] =  (step_memo(N-1) + step_memo(N-2)) % mod
    return (step_memo(N-1) + step_memo(N-2)) % mod
  
print(step_memo(N))


### FIXED CODE ###

N, M = map(int, input().split())
import sys
sys.setrecursionlimit(10000000)

mod = 1000000007

memo = [-1] * (N+1)

for _ in range(M):
    broken_step = int(input())
    memo[broken_step] = 0
    
memo[0] = 1
if memo[1] == -1:
    memo[1] = 1

def step_memo(N):
    
    if memo[N] != -1:
        return memo[N]
    
    memo[N] =  (step_memo(N-1) + step_memo(N-2)) % mod
    return (step_memo(N-1) + step_memo(N-2)) % mod
  
print(step_memo(N))
### BUGGY CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
d = [0] * n
for i in a:
  d[i-1] += 1
d.sort()
ans = 0
for i in range(n):
  if len(d[i:n]) == k:
    print(ans)
    break
  if d[i] == 0: continue
  ans += d[i]

### FIXED CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
d = [0] * n
for i in a: d[i-1] += 1
d.sort(reverse=True)
print(n-sum(d[0:k]))
### BUGGY CODE ###

mod = 10 **9 + 7



n = int(input())
match_list = []
for i in range(n):
    match_list.append(list(map(int, input().split())))
    
    
c = [0]
for i in range(n):
    c += [j+1 for j in c]


dp = [0] * (1 << n)
dp[0] = 1
for i in range((1 << n)-1):
    for j in range(n):
        if match_list[c[i]][j]:
            dp[(1<<j)^i] = (dp[(1<<j)^i] + dp[i])%mod


print(dp[-1])

### FIXED CODE ###

mod = 10 ** 9 + 7

n = int(input())

A = []
for i in range(n):
    A.append(list(map(int, input().split())))


memo = [-1] * (1<<n)
memo[0] = 1


def dfs(state, c):
    if memo[state] != -1:
        return memo[state]
    r = 0
    for i in range(n):
        if state & (1<<i) and A[c][i]:
            r += dfs(state ^ (1<<i), c+1)
            r %= mod
    memo[state] = r
    return r


print(dfs((1<<n)-1, 0))