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

N,W = map(int, input().split())
wv = [list(map(int, input().split())) for i in range(N)]

dp= [[0]*(W+1) for i in range(N+1)] 

for i in range(1,N+1):
    for j in range(1,W+1):
        if j >= wv[i-1][0]:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j - wv[i-1][0]] + wv[i-1][1])
        else:
            dp[i][j] = dp[i-1][j]
print(dp[N][W])

### FIXED CODE ###

N,W = map(int, input().split())
wv = [list(map(int, input().split())) for i in range(N)]

dp= [[0]*(W+1) for i in range(N+1)] 

for i in range(1,N+1):
    for j in range(1,W+1):
        if j >= wv[i-1][0]:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j - wv[i-1][0]] + wv[i-1][1])
        else:
            dp[i][j] = dp[i-1][j]
print(dp[N][W])
### BUGGY CODE ###


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

RD = []

for i in range(N):

    RD.append([])


for i in range(M):

    L,R,D = map(int,input().split())
    RD[L-1].append([R-1,D])
    RD[R-1].append([L-1,-1 * D])

end = [0] * N
endp = 0
endnum = 0
Q = []

cor = ["x"] * N
ans = "Yes"


for endp in range(N):

    if end[endp] == 0:
        Q.append(endp)
    else:
        continue

    while len(Q) > 0:

        q = Q.pop(0)

        if cor[q] == "x":
            cor[q] = 0

        for rd in RD[q]:

            r = rd[0]
            d = rd[1]

            if cor[r] == "x":
                cor[r] = cor[q] + d
                Q.append(r)

            elif cor[r] != cor[q] + d:
                ans = "No"
                break

        endnum += 1
        end[q] = 1

print (ans)


### FIXED CODE ###

from collections import deque

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

RD = [deque() for i in range(N)]
end = [False] * N

for i in range(M):

    L,R,D = map(int,input().split())
    RD[L-1].append([R-1,D])
    RD[R-1].append([L-1,-1 * D])
    end[L-1] = True
    end[R-1] = True
    
"""
    lp = wantp(L-1)
    rp = wantp(R-1)

    if lp != rp:

        if rank[lp] 
"""
    


endnum = 0
Q = deque()

cor = ["x"] * N
ans = "Yes"


for endp in range(N):

    if end[endp]:
        Q.append(endp)


        while len(Q) > 0:

            q = Q.pop()
            end[q] = False

            if cor[q] == "x":
                cor[q] = 0

            for r,d in RD[q]:

                if cor[r] == "x":
                    cor[r] = cor[q] + d
                    Q.append(r)

                elif cor[r] != cor[q] + d:
                    print ("No")
                    exit()


print ("Yes")
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def dp_fn():
  N, W = map(int, input().split())
  WV = (map(int, input().split()) for _ in range(N))
  
  DP = {0:0}
  
  for w, v in WV:
    keys = sorted(list(DP.keys()), reverse=True)
    for i in keys:
      if i + w <= W:
        if i+w in DP:
          DP[i+w] = max(DP[i] + v, DP[i+w])
        else:
          DP[i+w] = DP[i] + v
  return max(DP.values())
  
print(dp_fn())


### FIXED CODE ###

import sys
input = sys.stdin.readline

def dp_fn():
  N, W = map(int, input().split())
  WV = (map(int, input().split()) for _ in range(N))
  
  DP = {0:0}
  
  for w, v in WV:
    keys = sorted(DP.keys(), reverse=True)
    for i in keys:
      j = DP[i]
      if j+w <= W:
        if i+v in DP:
          DP[i+v] = min(DP[i+v], j+w)
        else:
          DP[i+v] = j+w
  return max(DP.keys())
  
print(dp_fn())
### BUGGY CODE ###

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

abs = [list(map(int, input().split())) for i in range(M)]

ans = 0

for ab in abs:
    a = ab[0] - 1
    b = ab[1] - 1
    _abs = abs[::]
    _abs.remove(ab)

    dist_map = [[i == j for j in range(N)] for i in range(N)]

    for _ab in _abs:
        _a = _ab[0] - 1
        _b = _ab[1] - 1
        if not dist_map[_a][_b]:
            dist_map[_a][_b] = True
            dist_map[_b][_a] = True

    for i in range(N):
        for j in range(N):
            for k in range(N):
                dist_map[j][k] = dist_map[j][k] or (dist_map[j][i] and dist_map[i][k])
                dist_map[k][j] = dist_map[j][k]

    if not dist_map[a][b]:
        ans += 1

print(ans)

### FIXED CODE ###

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

abs = [list(map(int, input().split())) for i in range(M)]

ans = 0

for ab in abs:
    a = ab[0] - 1
    b = ab[1] - 1
    _abs = abs[::]
    _abs.remove(ab)

    dist_map = [[i == j for j in range(N)] for i in range(N)]

    for _ab in _abs:
        _a = _ab[0] - 1
        _b = _ab[1] - 1
        if not dist_map[_a][_b]:
            dist_map[_a][_b] = True
            dist_map[_b][_a] = True

    for i in range(N):
        for j in range(N):
            for k in range(N):
                dist_map[j][k] = dist_map[j][k] or (dist_map[j][i] and dist_map[i][k])
                dist_map[k][j] = dist_map[j][k]

    if not dist_map[a][b]:
        ans += 1

print(ans)
### BUGGY CODE ###

def fib(n):
    if n <= 1:
        return 1
    else:
        return fib(n - 1) + fib(n - 2)

print fib(int(input()))

### FIXED CODE ###

def fib(n):
    if ft[n] != 0:
        return ft[n]
    else:
        ft[n] = fib(n - 1) + fib(n - 2)
        return ft[n]

ft = [0] * 45
ft[0] = ft[1] = 1
print fib(int(input()))
### BUGGY CODE ###

n = int(input())
m_list = []
for i in range(n):
  X, L = map(int, input().split())
  m_list.append([X-L,X+L])
 
m_list = sorted(m_list, key=lambda x:x[1])
  
def MachineArrangementCheck():
  length = len(m_list)
  # 配列の上限エラー対策
  for i in range(length):
    if i != length - 1:      
      # m1の上限とm２の下限が接するかを確認
      if (m_list[i+1][0] - m_list[i][1]) < 0:
        del m_list[i+1]
        return False
  return True
 
while MachineArrangementCheck() == False:
  continue
  
print(len(m_list))

### FIXED CODE ###

n = int(input())
m_list = []
for i in range(n):
    x,l = map(int, input().split())
    m_list.append([x-l, x+l])

m_list = sorted(m_list,key= lambda x:x[1])

result = 0
cur_pos = -1000000000

for min,max in m_list:
    if cur_pos <= min:
        result += 1
        cur_pos = max
print(result)
### BUGGY CODE ###

n,k = map(int,input().split())
x = [int(x) for x in input().split()]

mini = 10**9
for i in range(n-k+1):
    ls = x[i:i+k]
    flg1 = abs(ls[0])+abs(ls[0]-ls[k-1])
    flg2 = abs(ls[k-1])+abs(ls[0]-ls[k-1])
    flg = min(flg1,flg2)
    mini = min(flg,mini)
print(mini)

### FIXED CODE ###

n,k = map(int,input().split())
ls = [int(x) for x in input().split()]

mini = 10**9
for i in range(n-k+1):
    flg1 = abs(ls[i])+abs(ls[i]-ls[i+k-1])
    flg2 = abs(ls[i+k-1])+abs(ls[i]-ls[i+k-1])
    mini = min(flg1,flg2,mini)
print(mini)
### BUGGY CODE ###

mod =1000000007
n = int(input())
a = list(map(int, input().split()))
a.sort()
b = [0]*n
for i in range(n):
    b[i] = a[i]%mod
sumpro = 0

for i in range(n-1):
    for j in range(i+1, n):
            sumpro += (b[i]*b[j])%mod
            
print(sumpro%mod)

### FIXED CODE ###

MOD = 10 ** 9 + 7  # MODは変数に入れてしまったほうが打ち間違えなくていいです

N = int(input())
A = list(map(int, input().split()))

S = sum(A) % MOD
ans = 0

# A_Nも含まれてしまいますが、そのときはs=0なので問題ありません
for x in A:
    S -= x  # 自分と自分自身を掛けないように、先に引く必要があります
    S %= MOD  # MODはいちいち取っておくといいです
    ans += S * x
    ans %= MOD

ans %= MOD  # この行は完全に不要ですが、最後だけMODを取り忘れてWAになるミスは非常によくあるので、必要以上に取っておくと安心できます
print(ans)
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
cnt = 0
for i in range(1,n+1):
    for j in range(n-i+1):
        if sum(a[j:j+i]) == 0:
            cnt += 1
print(cnt)

### FIXED CODE ###

import math
from collections import Counter
from itertools import accumulate

def P(n,r):
    return math.factorial(n)//math.factorial(n-r)

def C(n,r):
    return P(n,r)//math.factorial(r)

n = int(input())
a = list(map(int,input().split()))
ac = [0] + list(accumulate(a))
c = Counter(ac)

cnt = 0
for v in c.values():
    if v >= 2:
        cnt += C(v,2)
print(cnt)
### BUGGY CODE ###

# import sys
# import collections
# import numpy as np

# N:県, M:市
N, M = list(map(int, input().split()))
# od = collections.OrderedDict()
L = [tuple(map(int, input().split())) for _ in range(M)]
A = {}
B = {}

for i in range(M):
  x = L[i]
  k = x[0]
  if k in A.keys():
    # print(A[k])
    # print(x)
    A[k].append(x[1])
  else:
    A[k] = [x[1]]

#print(A)
# A: {県番号: {市1の年:市1のindex, 市2の年:市2のindex}}

#c = collections.OrderedDict([('Kuroda', 18), ('Ichiroh', 51), ('Matsui', 55)])
#print(c['Kuroda'])

# 県番号でソート
for k in A.keys():
  # keyでソート
  B[k] = (sorted(A[k]))

#print(B)

for x in L:
  # print(B[x[0]])
  # print(x[1])
  num = (B[x[0]].index(x[1])) + 1
  print("{:0>6}{:0>6}".format(x[0], num))




### FIXED CODE ###

# import sys
 
# N:県, M:市
N, M = list(map(int, input().split()))

A = {}
# {ken: [(city_no, city_year)],...}

res = [None] * M

for i in range(M):
  k, y = list(map(int, input().split()))
  if k in A.keys():
    A[k].append((i, y))
  else:
    A[k] = [(i, y)]

# print(A)
# A: {県番号: {市1の年:市1のindex, 市2の年:市2のindex}}

for k, v in A.items():
  # sort by year
  c_list = sorted(v, key=lambda x: x[1])
  counter = 1
  for c in c_list:
    res[c[0]] = (k, counter)
    counter += 1

for x in res:
  print("{:0>6}{:0>6}".format(x[0], x[1]))
### BUGGY CODE ###

import itertools

n = int(input())

in_ar = [0 for _ in range(n)]
in_ar = [int(s) for s in input().split()]

al_tr = list(itertools.combinations(in_ar,3))
cnt = 0

for ar in al_tr:
    a,b,c = ar[0],ar[1],ar[2]
    if(a+b > c and a+c > b and c+b > a):
        cnt += 1

print(cnt)

### FIXED CODE ###

import bisect

n = int(input())

in_ar = [0 for _ in range(n)]
in_ar = [int(s) for s in input().split()]
in_ar.sort()
res = 0
#print(in_ar)
for i in range(n):
    for j in range(i,n):
        if(i == j):
            continue

        a = in_ar[i]
        b = in_ar[j]
        st = bisect.bisect_left(in_ar, abs(a-b))
        en = bisect.bisect_left(in_ar, abs(a+b))
        #print(a,b,j,en)
        res += en - j - 1
        '''
        if(abs(a-b) < a):
            res -= 1
        if(abs(a-b) < b):
            res -= 1
        '''

print(res)
### BUGGY CODE ###


N = int(input())

dp = dict()
total = 0
for i in range(1, N+1):
    mae = str(i)[0]
    usiro = str(i)[-1]
    key = mae + usiro
    if key in dp.keys():
        total += dp[key]
    else:
        count = 0
        for j in range(1, N+1):
            mae = str(j)[0]
            usiro = str(j)[-1]
            if key == usiro + mae:
                count += 1
        dp[key] = count
        total += count
    
print(total)

### FIXED CODE ###

import math

N = int(input())

dp = [[-1] * 10 for _ in range(10)]
temp = 0
total = 0

mae_usiro = [[-1] * 2 for _ in range(N+1)]
for i in range(1, N+1):
    mae = int(i / 10 ** int(math.log10(i)))
    usiro = i % 10
    mae_usiro[i] = [mae, usiro]

for i in range(1, N+1):
    mae, usiro = mae_usiro[i]
    if i > 100:
        total += dp[mae][usiro]
    elif dp[mae][usiro] != -1:
        total += dp[mae][usiro]
    else:
        count = 0
        for j in range(1, N+1):
            mae2, usiro2 = mae_usiro[j]
            if mae == usiro2 and usiro == mae2:
                count += 1
        dp[mae][usiro] = count
        total += count
    
print(total)
### BUGGY CODE ###

h,w=map(int,input().split())
field=[list(input()) for i in range(h)]
queue=[]
check=[[True for i in range(w)]for j in range(h)]
for i in range(h):
  for j in range(w):
    if field[i][j]=='#':
      check[i][j]=False
      queue.append([i,j])
p=[[0,1],[0,-1],[1,0],[-1,0]]
ans=0
while len(queue)>0:
  ans+=1
  manu=queue.copy()
  queue.clear()
  save=True
  for now in manu:
    for i in range(4):
      x=now[0]+p[i][0]
      y=now[1]+p[i][1]
      if x>-1 and x<h and y>-1 and y<w and check[x][y]:
        field[x][y]='#'
        queue.append([x,y])
        save=False
        check[x][y]=False
  if save:
    ans-=1
print(ans)

### FIXED CODE ###

import numpy as np
h,w=map(int,input().split())
field=[list(input()) for i in range(h)]
field=[[0 if field[j][i]=='#' else h+w for i in range(w)]for j in range(h)]
field=np.array(field)
for i in range(1,h):
  field[i,:]=np.minimum(field[i,:],field[i-1,:]+1)
for i in range(h-1,0,-1):
  field[i-1,:]=np.minimum(field[i,:]+1,field[i-1,:])
for i in range(1,w):
  field[:,i]=np.minimum(field[:,i],field[:,i-1]+1)
for i in range(w-1,0,-1):
  field[:,i-1]=np.minimum(field[:,i]+1,field[:,i-1])
print(np.max(field))
### BUGGY CODE ###


def main():
    n,k = map(int,input().split())
    dests =[0 for _ in range(n)]
    telepos = list(map(int,input().split()))
    for i,t in enumerate(telepos):
        dests[i] = t-1
    print(dfs(dests,k))




def dfs(dests,k,here = 0):
    here = 0
    telepo_times = 0
    cycle_start = -1
    cycle_end = -1
    cycle_length = -1
    visited = []
    ids = dict()


    #循環検出！同じ町にいつ戻ってくるのか
    while telepo_times < k:
        #print("現在地は",here)
        if here in visited:
            cycle_start = ids[here]
            #print(cycle_start,"でループが始まった")
            cycle_end = telepo_times - 1
            #print(cycle_end,"でループが終わった")
            cycle_length = cycle_end - cycle_start + 1
            #print("サイクルの長さは",cycle_length,"だ")
            break
        ids[here] = telepo_times

        visited.append(here)
        telepo_times += 1
        here = dests[here]
    if cycle_length == -1:
        return here + 1

    cycle_index = (k-cycle_start) % cycle_length
    return visited[cycle_start + cycle_index] + 1




    #telepo_times = 0
    #while telepo_times < (k - cycle_start)%cycle_length:
    #    telepo_times += 1
    #    here = dests[here]







if __name__ == '__main__':
    main()


### FIXED CODE ###


def main():
    n,k = map(int,input().split())
    dests =[0 for _ in range(n)]
    telepos = list(map(int,input().split()))
    for i,t in enumerate(telepos):
        dests[i] = t-1
    print(solve(dests,k))




def solve(dests,k,here = 0):
    here = 0
    telepo_times = 0
    cycle_start = -1
    cycle_end = -1
    cycle_length = -1
    visited = dict()
    visited2 = []


    #循環検出！同じ町にいつ戻ってくるのか
    while telepo_times < k:
        #print("現在地は",here)
        if here in visited:
            cycle_start = visited[here]
            #print(cycle_start,"でループが始まった")
            cycle_end = telepo_times - 1
            #print(cycle_end,"でループが終わった")
            cycle_length = cycle_end - cycle_start + 1
            #print("サイクルの長さは",cycle_length,"だ")
            break
        #ids[here] = telepo_times

        visited[here] = telepo_times
        visited2.append(here)
        telepo_times += 1
        here = dests[here]
    if cycle_length == -1:
        return here + 1

    cycle_index = (k-cycle_start) % cycle_length
    return visited2[cycle_start + cycle_index] + 1




    #telepo_times = 0
    #while telepo_times < (k - cycle_start)%cycle_length:
    #    telepo_times += 1
    #    here = dests[here]







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

mini, maxi, K_ban = map(int, input().split())

num_list = [i for i in range(mini, maxi + 1)]

if (maxi - mini + 1 <= 2 * K_ban):
    ans = num_list
else:
    ans = num_list[:K_ban] + num_list[-K_ban:]

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

### FIXED CODE ###

mini, maxi, K_ban = map(int, input().split())

if (maxi - mini + 1 <= 2 * K_ban):
    ans = [i for i in range(mini, maxi + 1)]

else:
    left = [i for i in range(mini, mini + K_ban)]
    right = [i for i in range(maxi - K_ban + 1, maxi + 1)]
    
    ans = left + right
    

[print(n) for n in ans]
### BUGGY CODE ###

import sys
import itertools
input = sys.stdin.readline

N = int(input())
S = input()
vv = []
cc = [False] * 1000
for v in itertools.combinations(S[0:-1], 3):
	cc[int(v[0]+v[1]+v[2])]=True
print(cc.count(True))


### FIXED CODE ###

import sys
import itertools
input = sys.stdin.readline

N = int(input())
S = input()
cc = [0]*1000
ans = [0]*1000
for j in range(len(S)-1):
	p = int(S[j])
	for i in range(1000):
		if(p==i%10 and cc[i]==2):
			cc[i]+=1
			ans[i]=1
		elif(p==(i//10)%10 and cc[i]==1):
			cc[i]+=1
		elif(p==i//100 and cc[i]==0):
			cc[i]+=1
print(sum(ans))
### BUGGY CODE ###

T1,T2 = map(int,input().split())
A1,A2 = map(int,input().split())
B1,B2 = map(int,input().split())

len1 = T1 * A1 + T2 * A2
len2 = T1 * B1 + T2 * B2
if len1 == len2:
  print("infinity")
  quit()

ans = 0
subs = 0  
sub1 = T1 * (A1 - B1)
sub2 = T2 * (A2 - B2)
X = [1, 1]
i = 0
while (X != [0, 0]):
  i += 1
  if subs != 0:
    if subs ** 2 + subs * sub1 <= 0:
      ans += 1
      X[0] = 1
    else:
      X[0] = 0
  subs = subs + sub1
  if subs != 0:
    if subs ** 2 + subs * sub2 <= 0:
      ans += 1
      X[1] = 1
    else:
      X[1] = 0
  subs = subs + sub2

print(ans)
   
    

### FIXED CODE ###

T1,T2 = map(int,input().split())
A1,A2 = map(int,input().split())
B1,B2 = map(int,input().split())

len1 = T1 * A1 + T2 * A2
len2 = T1 * B1 + T2 * B2
if len1 == len2:
  print("infinity")
  quit()

ans = 0
subs = 0  
sub1 = T1 * (A1 - B1)
sub2 = T2 * (A2 - B2)

if sub1 > 0:
  if len1 - len2 > 0:
    ans = 0
  else:
    S = (-1 * sub1) // (sub1 + sub2)
    T = (-1 * sub1) % (sub1 + sub2)
    if T == 0:
      ans = 2 * S
    else:
      ans = 2 * S + 1
else:
  if len1 - len2 < 0:
    ans = 0
  else:
    S = (-1 * sub1) // (sub1 + sub2)
    T = (-1 * sub1) % (sub1 + sub2)
    if T == 0:
      ans = 2 * S
    else:
      ans = 2 * S + 1
    
print(ans)
### BUGGY CODE ###

a,b,x = map(int,input().split())
Rb = range(0,b+1,x)
Mb = max(Rb)//x + 1

if not a == 0:
    Ra = range(0,a,x)
    Ma = max(Ra)//x + 1

    print(Mb - Ma)

if a == 0:
    print(Mb)

### FIXED CODE ###

a,b,x = map(int,input().split())
if a % x == 0:
    print(b//x - a//x + 1)
else:
    print(b//x - a//x)
### BUGGY CODE ###

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

count = 0
for i in range(0, n-2):
  for j in range(i+1, n-1):
    for k in range(j+1, n):
      if L[i] < (L[j] + L[k]):
        count += 1
      else:
        break
print(count)


### FIXED CODE ###

import bisect
n = int(input())
L = list(map(int, input().split()))
L.sort()

count = 0
for i in range(0, n-2):
  for j in range(i+1, n-1):
    t = L[i] + L[j]
    idx = bisect.bisect_left(L, t)
    count += idx - (j+1)

print(count)
### BUGGY CODE ###

n = int(input())
dif = [int(i) for i in input().split()]

max_dif = max(dif)

ans = 0
for i in range(max_dif+1):
	ARC = []
	ABC = []
	for j in range(n):
		if dif[j] >= i:
			ARC.append(dif[j])
		else:
			ABC.append(dif[j])
			
	if len(ARC) == len(ABC):
		ans += 1
		
print(ans)

### FIXED CODE ###

n = int(input())
dif = [int(i) for i in input().split()]

dif.sort()

print(dif[n//2] - dif[n//2 -1])
### BUGGY CODE ###

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

from functools import lru_cache
import sys

sys.setrecursionlimit(10*20)

def count(N):
    if N == 0:
        return 1
    else:
        return 3 + 2 * count(N-1)
    
def calc(N,X):
    if N == 0:
        return 1
    center = count(N-1) + 1
    if X == 0 :
        return 0
    elif X < center:
        return calc(N-1,X-1)
    elif X == center:
        return calc(N-1,center-2) + 1
    elif X > center:
        return calc(N-1,X-center-1) + calc(N,center)
print(calc(N,X-1))

### FIXED CODE ###

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

from functools import lru_cache
import sys

sys.setrecursionlimit(10*20)

@lru_cache(maxsize=None)
def count(N):
    if N == 0:
        return 1
    else:
        return 3 + 2 * count(N-1)
    
@lru_cache(maxsize=None)
def calc(N,X):
    if N == 0:
        return 1
    center = count(N-1) + 1
    if X == 0 :
        return 0
    elif X < center:
        return calc(N-1,X-1)
    elif X == center:
        return calc(N-1,center-2) + 1
    elif X > center:
        return calc(N-1,X-center-1) + calc(N,center)
print(calc(N,X-1))
### BUGGY CODE ###

n,m=map(int,input().split())
p=[]
pp=[1]
pp*=n
ans=[]
for i in range(n):
    p.append([])
for i in range(m):
    pi,yi=map(int,input().split())
    p[pi-1].append([yi,pp[pi-1]])
    ans.append([pi-1,pp[pi-1]])
    pp[pi-1]+=1
for i in range(n):
    p[i].sort()
for i in range(m):
    b=len(p[ans[i][0]])
    for j in range(b):
        if ans[i][1]==p[ans[i][0]][j][1]:
            print('{0:06d}{1:06d}'.format(ans[i][0]+1,j+1))
            break

### FIXED CODE ###

from operator import itemgetter
n,m=map(int,input().split())
a=[]
for i in range(m):
    pi,yi=map(int,input().split())
    a.append([i,pi,yi])
b=[]
c=[]
for i in range(n):
    b.append([])
    c.append([])
for i in range(m):
    x=a[i][0]
    y=a[i][2]
    b[a[i][1]-1].append([x,y])

for i in range(n):
    b[i].sort(key=itemgetter(1))
    l=len(b[i])
    for j in range(l):
        a[b[i][j][0]].append(j+1)
for i in range(m):
    xi=a[i][1]
    yi=a[i][3]
    print('{0:06d}{1:06d}'.format(xi,yi))
### BUGGY CODE ###

n = int(input())
lst = []
for i in range(n):
  lst.append(input())
  
count = {}
countLst = []
for i in lst:
  count[i] = lst.count(i)
  countLst.append(lst.count(i))
  
res = []
for i in count:
  if count[i] == max(countLst):
    res.append(i)
    
for i in sorted(res):
  print(i)


### FIXED CODE ###

from collections import defaultdict
from collections import OrderedDict
N = int(input())
ans = dict()
for _ in range(N):
    k = str(input())
    if k in ans:
        ans[k]+=1
    else:
        ans.update({k:1})
groupedByValue = defaultdict(list)
for key, value in sorted(ans.items()):
    groupedByValue[value].append(key)
l = groupedByValue[max(groupedByValue)]
for i in l:
    print(i)
### BUGGY CODE ###

def main():
    import sys
    input = sys.stdin.readline
    N = int(input())
    S = [input().strip() for i in range(N)]
    S.sort()
    set_S = set(S)
    cnt = 0
    ll = []
    for s in set_S:
        s_num = S.count(s)
        if cnt < s_num:
            cnt = s_num
            ll = [s]
        elif cnt == s_num:
            ll.append(s)

    ll.sort()
    print("\n".join(ll))

if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    import sys
    import collections
    input = sys.stdin.readline
    N = int(input())
    S = [input() for i in range(N)]
    c = collections.Counter(S)
    max_num = c.most_common(1)[0][1]
    ss = [cc[0] for cc in c.most_common() if cc[1] == max_num]
    ss.sort()
    for s in ss:
        print(s,end="")

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

N, M = map(int, input().split())
A = []
for m in range(M):
    A.append(int(input()))

dp = [0]*(N+2)

dp[N] = 1
dp[N+1] = 0

for i in range(N-1, -1, -1):
    if i in A:
        dp[i] = 0
    else:
        dp[i] = dp[i+1] + dp[i+2]
    
print(dp[0] % 1000000007)

### FIXED CODE ###

N, M = map(int, input().split())
A = []
for m in range(M):
    A.append(int(input()))


broken = [0]*(N+2)
for a in A:
    broken[a] = 1

dp = [0]*(N+2)

dp[N] = 1
dp[N+1] = 0

for i in range(N-1, -1, -1):
    if broken[i]:
        dp[i] = 0
    else:
        dp[i] = (dp[i+1] + dp[i+2]) % 1000000007
    
print(dp[0])
### BUGGY CODE ###

import sys
input = sys.stdin.readline

mod=1000000007
n,m=map(int,input().split())
a=[]
for i in range(m):
    a.append(int(input()))
al=len(a)
if al>0:
    a.sort()

f=0
for i in a:
    if i+1 in a:
        f=1
        break
if f==1:
    print(0)
else:
    dp=[0]*(n+1)
    dp[0]=1
    if 1 in a:
        dp[1]=0
        a.pop(0)
        al-=1
    else:
        dp[1]=1
    
    for i in range(2,n+1):
        if al>0 and i==a[0]:
            dp[i]=0
            a.pop(0)
            al-=1
        else:
            dp[i]=(dp[i-1]+dp[i-2])%mod
    print(dp[n]%mod)
  

### FIXED CODE ###

import sys
input = sys.stdin.readline

mod=1000000007
n,m=map(int,input().split())
a=[]
for i in range(m):
    a.append(int(input()))
al=len(a)


f=0
for i in range(al-1):
    if a[i+1]==a[i]+1:
        f=1
        break
if f==1:
    print(0)
else:
    dp=[0]*(n+1)
    dp[0]=1
    if 1 in a:
        dp[1]=0
        a.pop(0)
        al-=1
    else:
        dp[1]=1
    
    for i in range(2,n+1):
        if al>0 and i==a[0]:
            dp[i]=0
            a.pop(0)
            al-=1
        else:
            dp[i]=(dp[i-1]+dp[i-2])%mod
    print(dp[n]%mod)