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

#input
N, W = map(int, input().split())
w = [0] * N
v = [0] * N
for i in range(N):
    w[i], v[i] = map(int, input().split())

#output
import numpy as np
V = max(v)
INF = 10**10
dp = np.full((N+1, N*V+1), INF)
dp[0, 0] = 0

for i in range(N):
    for j in range(N*V+1):
        if j < v[i]:
            dp[i+1, j] = dp[i, j]
        else:
            dp[i+1, j] = min(dp[i, j], dp[i, j-v[i]]+w[i])
        
answer = 0
for i in range(N*V+1):
    if dp[N, i] <= W:
        answer = i

print(answer)

### FIXED CODE ###

#input
N, W = map(int, input().split())
w = [0] * N
v = [0] * N
for i in range(N):
    w[i], v[i] = map(int, input().split())

#output
import numpy as np
V = max(v)
INF = 10**10
dp = np.full((N+1, N*V+1), INF)
dp[0, 0] = 0

for i in range(N):
    dp[i+1, v[i]:] = np.minimum(dp[i, v[i]:], dp[i, :-v[i]]+w[i])
    dp[i+1, :v[i]] = dp[i, :v[i]]

answer = 0
for i in range(N*V+1):
    if dp[N, i] <= W:
        answer = i

print(answer)
### BUGGY CODE ###

from collections import defaultdict
import sys
room_num,root_num = map(int,input().split())
room_dis_dic = dict(zip(range(1,room_num+1),[0]+[sys.maxsize]*(room_num-1)))
connect_dic = defaultdict(list)
connected_list = [1]
next_connect_dic = {}
for _ in range(root_num):
    a,b = map(int,input().split())
    connect_dic[a].append(b)
    connect_dic[b].append(a)
    
for room_i in connected_list:
    #print(room_i)
    next_room_set = set(connect_dic[room_i])-set(connected_list)
    connected_list.extend(list(next_room_set))
    for next_room_i in next_room_set:
        if room_dis_dic[next_room_i] > room_dis_dic[room_i]+1:
            room_dis_dic[next_room_i] = room_dis_dic[room_i]+1
            next_connect_dic[next_room_i] = room_i

if sys.maxsize in room_dis_dic.values():
    print("No")
else:
    print("Yes")
    for i in range(2,room_num+1):
        print(next_connect_dic[i])

### FIXED CODE ###

from collections import defaultdict
import sys
room_num,root_num = map(int,input().split())
#room_dis_dic = dict(zip(range(1,room_num+1),[0]+[sys.maxsize]*(room_num-1)))
connect_dic = defaultdict(set)
connected_list = [1]
next_connect_dic = {}
for _ in range(root_num):
    a,b = map(int,input().split())
    connect_dic[a].add(b)
    connect_dic[b].add(a)
    
for room_i in connected_list:
    #print(room_i)
    next_room_set = {connect_to for connect_to in connect_dic[room_i] if connect_to not in next_connect_dic.keys()}
    connected_list.extend(list(next_room_set))
    for next_room_i in next_room_set:
        next_connect_dic[next_room_i] = room_i

if len(set(range(2,room_num+1))-next_connect_dic.keys())!=0:
    print("No")
else:
    print("Yes")
    for i in range(2,room_num+1):
        print(next_connect_dic[i])
### BUGGY CODE ###

r,g,b,n = map(int,input().split())
count = 0
rr = n // r
gg = n // g
for i in range(rr+1):
  for j in range(gg+1):
    if n >= i*r + j*g and (n - (i*r + j*g)) %  b == 0:
        count += 1
print(count)

### FIXED CODE ###

r,g,b,n = map(int,input().split())
count = 0
rr = n // r
for i in range(rr+1):
  for j in range((n-i*r)//g+1):
    tmp = n - (i*r + j*g)
    if tmp >= 0 and tmp %  b == 0:
        count += 1
print(count)
### BUGGY CODE ###

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

MOD=10**9+7
def comb(n,k):
    if n<k:
        return 0
    if n<0 or k<0:
        return 0
    k=min(n-k,k)
    ans=1
    inv=[1]*(k+1)
    if k>=1:
        ans*=(n-k+1)%MOD
    for i in range(2,k+1):
        inv[i]=MOD-inv[MOD%i]*(MOD//i)%MOD
        ans=ans*(n-k+i)*inv[i]%MOD
    return ans
cnt=[]
v=set()
yut=True
for i in range(n-1):
    if a[i]!=a[i+1]:
        yut=False
if yut:
    for i in range(n):
        print(comb(n-1,2))
    exit()
for i in range(n):
    g=a.count(a[i])
    v.add(a[i])
    cnt.append([a[i],comb(g,2)])
fg=0
cvg=[]
vsd=list(v)
for i in range(n):
    tt=vsd[fg]
    if cnt[i][0]==tt:
        cvg.append(cnt[i][1])
        if  fg<len(vsd)-1:
            fg+=1

sy=sum(cvg)-cvg[-1]
for i in range(n):
    h=a.count(a[i])
    tmp=sy-(h-1)
    ans.append(tmp)

for i in range(n):
    print(ans[i])

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
from collections import Counter
MOD=10**9+7

d=Counter(a)
tni=0
dv=d.values()
dv=list(dv)
for i in range(len(dv)):
    tni+=dv[i]*(dv[i]-1)//2

for i in range(n):
    r=d[a[i]]
    print(tni-(r-1))
### BUGGY CODE ###

#from functools import lru_cache
import sys
from itertools import product,combinations
from functools import reduce,lru_cache
def vfunc(f): return lambda *lst, **kwargs: list(map(lambda *x:f(*x,**kwargs),*lst))

def list_t(l): return vfunc(lambda *args:args)(*l)

def rvfunc(f): return lambda *lst, **kwargs: list(map(lambda *x:rvfunc(f)(*x,**kwargs) if all(vfunc(lambda y:isinstance(y,list))(x)) else f(*x,**kwargs),*lst))

def reader():return vfunc(lambda l:l.split())(sys.stdin.readlines())

n=int(reader()[0][0])
a=[]
while n!=0:
    a.append(n%10)
    n//=10
print('Yes' if sum(a)%9==0 else 'No')

### FIXED CODE ###

#from functools import lru_cache
import sys
def vfunc(f): return lambda *lst, **kwargs: list(map(lambda *x:f(*x,**kwargs),*lst))

def reader():return vfunc(lambda l:l.split())(sys.stdin.readlines())

n=reader()[0][0]
i=vfunc(lambda n:int(n))(n)
print('Yes' if sum(i)%9==0 else 'No')
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
l=[]
for i in range(n):
  l.append(a.count(a[i]-1)+a.count(a[i])+a.count(a[i]+1))
print(max(l))

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
l=[]
for i in range(max(a)+3):
  l.append(0)
for j in range(n):
  l[a[j]+1]+=1
m=[]
for i in range(1,max(a)+2):
  m.append(l[i-1]+l[i]+l[i+1])
print(max(m))
### BUGGY CODE ###

s=list(input())
s.reverse()

MOD=10**9+7
dp = [[0 for _ in range(13)] for _ in range(len(s)+1)]
dp[0][0]=1
for i in range(len(s)):
    nd=s[i]
    for mod in range(13):
        dp[i][mod] %=MOD
        for d in range(10):
            if nd != "?" and str(d)!=nd:
                continue
            nmod=(d*(pow(10,i,13)) + mod) % 13
            dp[i+1][nmod] += dp[i][mod]

print(dp[-1][5]%MOD)

### FIXED CODE ###

s=list(input())
s.reverse()

MOD=10**9+7
dp = [[0 for _ in range(13)] for _ in range(len(s)+1)]
dp[0][0]=1
keta=1
for i in range(len(s)):
    nd=s[i]
    for mod in range(13):
        dp[i][mod] %=MOD
        if dp[i][mod]==0:
            continue

        for d in range(10):
            if nd != "?" and str(d)!=nd:
                continue
            nmod=(d*keta + mod) % 13
            dp[i+1][nmod] += dp[i][mod]
    keta*=10
    keta%=13

print(dp[-1][5]%MOD)
### BUGGY CODE ###

n=int(input())
ans=[]
for i in range(n):
    qw=input()
    ans.append([0,0,0,0,0,0,0,0,0,0])
    for j in range(10):
        ans[i][j]=qw[j]
    ans[i].sort()

ans.sort()
a=0
for i in range(n-1):
    for j in range(n-1-i):
        if ans[i]==ans[n-1-j]:
            a+=n-i-j-1
            break

print(int(a))


### FIXED CODE ###

n=int(input())
ans=[]
for i in range(n):
    qw=input()
    ans.append([0,0,0,0,0,0,0,0,0,0])
    for j in range(10):
        ans[i][j]=qw[j]
    ans[i].sort()

lis=[]
for i in range(n):
    lis.append(ans[i][0])
    for j in range(9):
        lis[i]+=ans[i][j+1]

a=0
#print(lis)

dic={lis[0]:1}
for i in range(n-1):
    if lis[i+1] in dic.keys():
        a+=dic[lis[i+1]]
        dic[lis[i+1]]+=1
    else:
        dic[lis[i+1]]=1

print(int(a))
### BUGGY CODE ###

# -*- coding: utf-8 -*-

n = int(input())
a = ["" for _ in range(n)]

for i in range(n):
    a[i] = int(input())


ans = ["" for _ in range(n)]
for i in range(n):
    a_test = a[:]
    del a_test[i]
    ans[i] = max(a_test)


for i in range(n):
    print(ans[i])


### FIXED CODE ###

# -*- coding: utf-8 -*-

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

max_a = max(a)
b = a[:]
b.remove(max_a)
max_b = max(b)

if max_a == max_b:
    for i in range(n):
        print(max_a)
else:
    idx = a.index(max_a)
    for i in range(n):
        if idx == i:
            print(max_b)
        else:
            print(max_a)
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
ans = 1
for i in range(n):
    ans *= a[i]
if ans > 10**18:
    print(-1)
else:
    print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
ans = 1
m = 10 ** 18

if 0 in a:
    print(0)
    exit()
for i in a:
    ans *= i
    if ans>m:
        print(-1)
        exit()
    
print(ans)
### BUGGY CODE ###

# N! 通りの総和は期待値で考えたほうがわかりやすくなることが多そう

import sys
from functools import lru_cache
sys.setrecursionlimit(500000)

def make_modinv_list(n, mod=10**9+7):
    # 0 から n までの mod 逆元のリストを返す O(n)
    modinv = [0, 1]
    for i in range(2, n+1):
        modinv.append(mod - mod//i * modinv[mod%i] % mod)
    return modinv

def main():
    modinv = make_modinv_list(200)

    @lru_cache(maxsize=None)
    def solve(idx, X):
        # 降順ソートした S の idx 個目以降を使ったときの操作後の X の期待値
        if idx == N:
            return X
        # idx 個目を idx 個目以降で最初に使うかで場合分け
        res = 0
        # 最初に使う場合（確率 (1/(N-idx))）
        res += modinv[N-idx] * solve(idx+1, X % S[idx]) % mod
        # 最初に使わない場合（確率 ((N-idx-1)/(N-idx))）
        res += (N-idx-1) * modinv[N-idx] * solve(idx+1, X) % mod
        return res % mod

    mod = 10**9+7
    N, X = map(int, input().split())
    S = sorted(map(int, input().split()), reverse=True)
    ans = solve(0, X)
    for i in range(2, N+1):
        ans = ans * i % mod
    print(ans)

main()


### FIXED CODE ###

# N! 通りの総和は期待値で考えたほうがわかりやすくなることが多そう

import sys
from functools import lru_cache
sys.setrecursionlimit(500000)

def make_modinv_list(n, mod=10**9+7):
    # 0 から n までの mod 逆元のリストを返す O(n)
    modinv = [0, 1]
    for i in range(2, n+1):
        modinv.append(mod - mod//i * modinv[mod%i] % mod)
    return modinv

def main():
    modinv = make_modinv_list(200)

    @lru_cache(maxsize=None)
    def solve(idx, X):
        # 降順ソートした S の idx 個目以降を使ったときの操作後の X の期待値
        if idx == N:
            return X
        # idx 個目を idx 個目以降で最初に使うかで場合分け
        res = 0
        # 最初に使う場合（確率 (1/(N-idx))）
        res += modinv[N-idx] * solve(idx+1, X % S[idx]) % mod
        # 最初に使わない場合（確率 ((N-idx-1)/(N-idx))）
        res += (N-idx-1) * modinv[N-idx] * solve(idx+1, X) % mod
        return res % mod

    mod = 10**9+7
    N, X = map(int, input().split())
    S = sorted(map(int, input().split()), reverse=True)
    ans = solve(0, X)
    for i in range(2, N+1):
        ans = ans * i % mod
    print(ans)

main()
### BUGGY CODE ###

N = input()
A = list(map(int, input().split()))
num = 1
for i in A:
  if 0 in A:
    num = 0
    break
  elif num > 1000000000000000000:
    break
  num = num*int(i)
if num > 1000000000000000000:
  print(-1)
else:
  print(num)

### FIXED CODE ###

N = input()
A = list(map(int, input().split()))
newA = sorted(A,reverse=True)
num = 1
if 0 in A:
  num = 0
else:
  for i in newA:
    if num > 1000000000000000000:
      break
    num = num*int(i)
if num > 1000000000000000000:
  print(-1)
else:
  print(num)
### BUGGY CODE ###

def knapsack_123(values,weights,capacity):
    work = [0 for i in range(capacity+1)]
    for c in range(1, capacity+1):
        candidates = [val + work[c-weight]
                      for val,weight in zip(values,weights) if weight <= c]
        work[c] = max(candidates) if candidates != [] else 0
    usedcap=min([c for c,w in enumerate(work) if w==work[-1]])
    return work[-1],usedcap
def sol(inp=input):
    n=int(inp())
    prices_a=list(map(int,inp().split()))
    prices_b=list(map(int,inp().split()))
    
    valA,usedcapA=knapsack_123(values=[xb for xa,xb in zip(prices_a,prices_b) if xa<xb],
                               weights=[xa for xa,xb in zip(prices_a,prices_b) if xa<xb],
                               capacity=n)
    capB=valA+n-usedcapA
    valB,usedcapB=knapsack_123(values=[xa for xa,xb in zip(prices_a,prices_b) if xa>xb],
                               weights=[xb for xa,xb in zip(prices_a,prices_b) if xa>xb],
                               capacity=capB)
    return '{}'.format(valB+capB-usedcapB)
  
print(sol())

### FIXED CODE ###

def knapsack_123(values,weights,capacity):
    work = [0 for i in range(capacity+1)]
    for v,w in zip(values,weights):
        for c in range(w, capacity+1):
            work[c]=max(work[c],work[c-w]+v)
    return work[-1]
def sol(inp=input):
    n=int(inp())
    prices_a=list(map(int,inp().split()))+[1]
    prices_b=list(map(int,inp().split()))+[1]
    
    valA=knapsack_123(values=prices_b,weights=prices_a,capacity=n)
    valB=knapsack_123(values=prices_a,weights=prices_b,capacity=valA)
    return '{}'.format(valB)
print(sol())
### BUGGY CODE ###

import re
S = input()
count=0
num=1
while num!=0:
    num=S.count("BW")
    S=re.sub("BW", "WB", S, num)
    count+=num
print(count)



### FIXED CODE ###

S =list(input())
count=0
w_count=0
for i in range(len(S)):
    if S[i]=="W":
        count+=i
        w_count+=1
print(int(count-w_count*(w_count-1)/2))
### BUGGY CODE ###

S=input()
count2019 = [0]*2019
count2019[0]=1
mod2019 = 0
d = 1
for i in S[::-1]:
    mod2019 =mod2019+int(i)*d
    mod2019%=2019
    count2019[mod2019] +=1
    d *= 10
    d%2019
ans =0
for i in count2019:
   ans+= i*(i-1)//2
print(ans)

### FIXED CODE ###

s = list(input())
# s = list(str(10**200000))
n = len(s)
ans = 0
s.reverse()
# print(s)
x = 1
tot = 0
count = [0]*2019
for i in range(n):
    count[tot]+=1
    tot += int(s[i])*x
    # print(tot)
    tot %= 2019
    ans += count[tot]
    x = x*10%2019
print(ans)
### BUGGY CODE ###

import sys
inf=10**10

def dijkstra(s,n,cost):
    #始点sから各頂点への最短距離
    #n:頂点数,　w:辺の数, cost[u][v] : 辺uvのコスト(存在しないときはinf)
    d = [float("inf")] * n
    used = [False] * n
    for i in range(H):
        for j in range(W):
            if x[i][j]==inf: used[i*W+j]=True
    d[s] = 0
    
    while True:
        v = -1
        #まだ使われてない頂点の中から最小の距離のものを探す
        for i in range(n):
            if (not used[i]) and (v == -1):
               v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
               break
        used[v] = True

        p=[]    
        if v>W-1: p.append(v-W)
        if v+W<H*W: p.append(v+W)
        if v%W>0: p.append(v-1)
        if v%W<W-1: p.append(v+1)
        for j in range(n):
               d[j] = min(d[j],d[v]+cost[v][j])
    return d


def f(s):
    r=[]
    for j in range(W):
        if s[j]=="#": r.append(inf)
        elif s[j]==".": r.append(0)
    return r

H,W=map(int,input().split())
x=[f(input()) for i in range(H)]

cost = [[float("inf") for i in range(H*W)] for i in range(H*W)] 
for i in range(H*W):
    for j in range(H*W):
        if x[i//W][i%W]==inf or x[j//W][j%W]==inf: continue
        if abs(i-j)==W: cost[i][j],cost[j][i]=1,1
        elif i-j==1 and i%W!=0: cost[i][j],cost[j][i]=1,1
        elif j-i==1 and j%W!=0: cost[i][j],cost[j][i]=1,1

ans=0
for i in range(H):
    for j in range(W):
        if x[i][j]==0: ans+=1

ans-=dijkstra(0,H*W,cost)[H*W-1]+1
print(ans if ans>=0 else -1)

### FIXED CODE ###

import sys
from collections import deque

def bfs(maze, visited):
    try:
        sy,sx=0,0
        gy,gx=H-1,W-1
        queue = deque([[sy, sx]])
        visited[sy][sx] = 0
        while queue:
            y, x = queue.popleft()
            if [y, x] == [gy, gx]:
                return visited[y][x]

            p=[]
            if x>0 : p.append([0,-1])
            if x<W-1: p.append([0,1])
            if y>0: p.append([-1,0])
            if y<H-1: p.append([1,0])
            for j, k in p:
                new_y, new_x = y+j, x+k
                if maze[new_y][new_x] == "." and \
                    visited[new_y][new_x] == -1:
                    visited[new_y][new_x] = visited[y][x] + 1
                    queue.append([new_y, new_x])
        return -1

    except RuntimeError:
        print(-1)
        sys.exit()


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

ans=0
for i in range(H):
    for j in range(W):
        if m[i][j]==".": ans+=1

visited=[[-1]*W for i in range(H)]
p=bfs(m,visited)
print( p if p==-1 else ans-p-1)
### BUGGY CODE ###

N = int(input())
from collections import defaultdict

G = defaultdict(list)
EdaNum = defaultdict(int)

for i in range(N-1):
    a,b = map(int,input().split())
    G[a].append(b)
    G[b].append(a)
    EdaNum[(a,b)] = i
    
ans = [-1]*(N-1)

que = [[1,-1]]
K = 0
visited = [False]*(N+1)

for i in range(1,N+1):
    K = max(K,len(G[i]))

while que != []:
    #print(que)
    now,parent = que.pop()
    visited[now]=True
    used = [False]*(K+1)
    if parent != -1:
        used[ans[EdaNum[(min(now,parent),max(now,parent))]]] = True
    nowcolor = 1
    for i in G[now]:
        #print(i,parent)
        if i != parent:
            while used[nowcolor] == True:
                nowcolor += 1
            ans[EdaNum[(min(now,i),max(now,i))]] = nowcolor
            nowcolor += 1
            que.append([i,now])
    #print(que)

print(K)
for i in ans:
    print(i)

### FIXED CODE ###

N = int(input())
from collections import defaultdict

G = defaultdict(list)
EdaNum = defaultdict(int)

for i in range(N-1):
    a,b = map(int,input().split())
    G[a].append(b)
    G[b].append(a)
    EdaNum[(a,b)] = i
    
ans = [-1]*(N-1)

que = [[1,-1,-1]]
K = 0
visited = [False]*(N+1)

for i in range(1,N+1):
    K = max(K,len(G[i]))

while que != []:
    #print(que)
    now,parent,parentcolor = que.pop()
    visited[now]=True
    nowcolor = 1
    for i in G[now]:
        #print(i,parent)
        if i != parent:
            if nowcolor == parentcolor:
                nowcolor += 1
            ans[EdaNum[(min(now,i),max(now,i))]] = nowcolor
            nowcolor += 1
            if len(G[i])!=1:
                que.append([i,now, nowcolor-1])
    #print(que)

print(K)
for i in ans:
    print(i)
### BUGGY CODE ###

N=int(input())
TA=[list(map(int,input().split())) for i in range(N)]
Taka=1
Aoki=1

def UP(V1,V2,R1,R2):
    r1,r2=R1,R2
    while V1>R1 or V2>R2:
        R1+=r1
        R2+=r2
    return [R1,R2]

for i in range(N):
    up=UP(Taka,Aoki,TA[i][0],TA[i][1])
    Taka=up[0]
    Aoki=up[1]

print(Taka+Aoki)

### FIXED CODE ###

N=int(input())
TA=[list(map(int,input().split())) for i in range(N)]
Taka=1
Aoki=1

def UP(V1,V2,R1,R2):
    n=max(-(-V1//R1),-(-V2//R2))
    return(n*R1,n*R2)

for i in range(N):
    up=UP(Taka,Aoki,TA[i][0],TA[i][1])
#    print(up)
    Taka=up[0]
    Aoki=up[1]

print(Taka+Aoki)
### BUGGY CODE ###

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

place = [[0, 0] for _ in range(H * W)]
for h in range(H):
	for w in range(W):
		place[a[h][w] - 1] = [h, w]

cost = [abs(place[i][0] - place[i + d][0]) + abs(place[i][1] - place[i + d][1]) for i in range(H * W - d)]

Q = int(input())

for q in range(Q):
	l, r = map(int, input().split())
	ans = 0
	for i in range(l - 1, r - 1, d):
		ans += cost[i]
	print(ans)

### FIXED CODE ###

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

place = [[0, 0] for _ in range(H * W)]
for h in range(H):
	for w in range(W):
		place[a[h][w] - 1] = [h, w]

cost = [abs(place[i][0] - place[i + d][0]) + abs(place[i][1] - place[i + d][1]) for i in range(H * W - d)]

ans = [0 for _ in range(H * W)]

for i in range(d, H * W):
	ans[i] = ans[i - d] + cost[i - d]

Q = int(input())

for q in range(Q):
	l, r = map(int, input().split())
	print(ans[r - 1] - ans[l - 1])
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
A.insert(0, 0)
for i in range(N-1):
    tmp = 0
    for j in range(i+1, N):
        if(i+1 == A[j]):
            tmp += 1
    print(tmp)
print(0)

### FIXED CODE ###


N = int(input())
A = list(map(int, input().split()))
dp = [0]*N
for i in range(len(A)):
    dp[A[i]-1] += 1
for i in range(N):
    print(dp[i])
### BUGGY CODE ###

n=int(input())
name=[]
num=[]
for i in range(n):
    s=input()
    if s in name:
        num[name.index(s)]+=1
    else:
        name.append(s)
        num.append(1)
x=max(num)
res=[]
for i in range(len(num)):
    if num[i]==x:
        res.append(name[i])
res.sort()
print(*res)

### FIXED CODE ###

n=int(input())
d={}
m=1
for i in range(n):
    s=input()
    if s in d:
        d[s]+=1
        m=max(m,d[s])
    else:
        d[s]=1
se=set()
for i in d:
    if d[i]==m:
        se.add(i)
se=list(se)
se.sort()
print(*se)
### BUGGY CODE ###

n = int(input())
a = 1
b = 1
mx = 10 ** 10
while (a <= b and a <= n):
    if n % a == 0:
        b = int(n / a)
        mx = min(mx, max(a, b))
    a += 1
print(len(str(mx)))


### FIXED CODE ###

n = int(input())
a = 1
b = 1
mx = 10 ** 10
while (a <= b and a <= 10**5):
    if n % a == 0:
        b = int(n / a)
        mx = min(mx, max(a, b))
    a += 1
print(len(str(mx)))
### BUGGY CODE ###

h,w,k =map(int,input().split())
ma = []
for i in range(h):
    ma.append(list(map(int,list(input()))))
ans = [0]*2**(h-1)
for i in range(2**(h-1)):
    idx = [0]*h #縦の何枚目か
    group = 0
    for j in range(h):
        idx[j] = group
        if (i>>j & 1):
            group +=1
    ans[i] += idx[-1]#h方向の分割
    n = idx[-1]+1#縦に何枚あるか
    cnt = [0]*n ##各ブロックの白チョコの数
    div_w = 0 #w方向の分割
    for e in range(w):
        temp = [0]*n #一時的な列を保存
        for j in range(h):
            p = idx[j]
            cnt[p] += ma[j][e]
            temp[p] += ma[j][e]
        if max(cnt) >k:
            div_w +=1
            cnt = temp
        if max(temp) >k:#この時h方向の分割そのものがだめ
            div_w = 10**9
            break
    ans[i] += div_w
print(min(ans))


### FIXED CODE ###

h,w,k =map(int,input().split())
ma = []
for i in range(h):
    ma.append(list(map(int,list(input()))))
ans = [0]*2**(h-1)
for i in range(2**(h-1)):
    idx = [0]*h #縦の何枚目か
    group = 0
    for j in range(h):
        idx[j] = group
        if (i>>j & 1):
            group +=1
    ans[i] += idx[-1]#h方向の分割
    n = idx[-1]+1#縦に何枚あるか
    cnt = [0]*n ##各ブロックの白チョコの数
    div_w = 0 #w方向の分割
    for e in range(w):
        temp = [0]*n #一時的な列を保存
        for j in range(h):
            p = idx[j]
            cnt[p] += ma[j][e]
            temp[p] += ma[j][e]
        if max(cnt) >k:
            div_w +=1
            cnt = temp
        if max(temp) >k:#この時h方向の分割そのものがだめ
            div_w = 10**9
            break
    ans[i] += div_w
print(min(ans))
### BUGGY CODE ###

def typical_stairs(n, m, ali):

    mod = 10**9+7

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

    for i in range(1, n+1):
        if i in ali:
            continue
        dp[i] = dp[i-2] + dp[i-1]
        dp[i] %= mod

    return dp[i]

def main():
    n, m = map(int, input().split())
    ali = [int(input())for i in range(m)]
    print(typical_stairs(n, m, ali))

if __name__ == '__main__':
    main()

### FIXED CODE ###

def typical_stairs(n, m, ali):

    mod = 10**9+7
    flag = [True]*(n+1)
    for i in ali:
        flag[i] = False

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

    for i in range(1, n+1):
        if not flag[i]:
            continue
        dp[i] = dp[i-2] + dp[i-1]
        dp[i] %= mod

    return dp[i]

def main():
    n, m = map(int, input().split())
    ali = [int(input())for i in range(m)]
    print(typical_stairs(n, m, ali))

if __name__ == '__main__':
    main()