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

import sys
sys.setrecursionlimit(4100000)
input = sys.stdin.readline
from collections import deque

n,m = map(int,input().split())
g = [[] * n for i in range(n)]
for i in range(m):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    g[u].append(v)
    g[v].append(u)
    
ans = [-1]*n
cnt = [n]*n
def dfs(now, prev,c):
    for next in g[now]:
        if next != prev and next!=0:
          if cnt[next] > c:
            ans[next] = now+1
            cnt[next] = c
            dfs(next, now,c+1)
            
from collections import deque

que = deque()
que.append((0,1))
chk = [False]*n
chk[0] =True
while que:
    now,p = que.popleft()
    if all(chk):
      break
    for i in g[now]:
        if not chk[i]:
          ans[i] = p
          chk[i] = True
          que.append((i,i+1))


for i in ans[1:]:
  if i == -1:
    print('No')
    exit()
print('Yes')
for i in ans[1:]:
  print(i)

### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from collections import deque

n,m = map(int,readline().split())
g = [[] * n for i in range(n)]
for i in range(m):
    u, v = map(int,readline().split())
    u -= 1
    v -= 1
    g[u].append(v)
    g[v].append(u)
    
ans = [-1]*n
from collections import deque

que = deque()
que.append((0,1))
chk = [False]*n
chk[0] =True
cnt = 1
while que:
    now,p = que.popleft()
    if cnt == n:
      break
    for i in g[now]:
        if not chk[i]:
          ans[i] = p
          chk[i] = True
          cnt += 1
          que.append((i,i+1))

if cnt!=n:
  print('No')
  exit()
  
print('Yes')
for i in ans[1:]:
  print(i)
### BUGGY CODE ###

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

def check(si,xi):
    X = [-1] * N
    X[si] = xi
    for i in range(N-1):
        ci = (si+i+1)%N-1
        X[ci+1] = 2*A[ci] - X[ci]
    if X[si] == 2*A[si-1] - X[si-1]:
        return X
    return []

mm = 10**10
mi = -1
for i,a in enumerate(A):
    if a < mm:
        mm = a
        mi = i

for xi in range(2*mm+1):
    X = check(mi, xi)
    if X:
        print(*X)
        exit()

### FIXED CODE ###

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

S=sum(A)
X1=S-2*sum([A[i] for i in range(N) if i&1])

rain=X1
for i in range(N):
    print(rain)
    rain=(A[i]-rain//2)*2
### BUGGY CODE ###

L,R = map(int,input().split())

D = []

it = L
while(it<=R):
    D.append(it%2019)
    if len(D)>=2019*2:break
    it += 1

ans = 2019
for i in range(len(D)):
    for j in range(i+1,len(D)):
        a = (D[i]*D[j]) % 2019
        if ans > a:
            ans = a
            
print(ans)

### FIXED CODE ###

L,R = map(int,input().split())

ans = 2019
it = L
while(it<=min(R,it+2019)):
    jt = it+1
    while(jt<=min(R,jt+2019)):
        a = (it*jt)%2019
        if a < ans:
            ans = a
            if ans==0:break
        jt += 1
    if ans==0:break
    it += 1
            
print(ans)
### BUGGY CODE ###

X,Y,Z,K = map(int,input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = list(map(int,input().split()))
A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)
AB = []
for b in B:
    for a in A:
        AB.append(a+b)
AB.sort(reverse=True)
AB = AB[0:min(3001,X*Y*Z+1)]

ABC = []
for c in C:
    for ab in AB:
        ABC.append(ab+c)
ABC.sort(reverse=True)

for i in range(K):
    print(ABC[i])

### FIXED CODE ###

# 通ってるコードをコピペ、ほぼ同じはずなんだけどこれは通る？
x,y,z,k = map(int,input().split())
lisa = list(map(int,input().split()))
lisb = list(map(int,input().split()))
lisc = list(map(int,input().split()))
lisa.sort(reverse=True)
lisb.sort(reverse=True)
lisc.sort(reverse=True)
an = []
ans = []
for num in lisb:
    for nu in lisa:
        an.append(num+nu)
an.sort(reverse=True)
an = an[:min(3001,x*y*z+1)]
for num in lisc:
    for nu in an:
        ans.append(num+nu)
ans.sort(reverse=True)
for i in range(k):
    print(ans[i])
### BUGGY CODE ###

S = input()
T = input()

def count_string(strInput):
    tmp = {}
    for s in strInput:
        cnt = strInput.count(s)
        tmp[s] = cnt
    
    re = [tmp[a] for a in tmp]
    re.sort()
    return re

S_count = count_string(S)
T_count = count_string(T)

if S_count == T_count:
    print('Yes')
else:
    print('No')

### FIXED CODE ###

S = input()
T = input()

def count_string(strInput):
    tmp = {}
    for s in strInput:
        if s in tmp:
            tmp[s] += 1
        else:
            tmp[s] = 1
    
    re = [tmp[a] for a in tmp]
    re = sorted(re)
    return re

S_count = count_string(S)
T_count = count_string(T)

if S_count == T_count:
    print('Yes')
else:
    print('No')
### BUGGY CODE ###

# https://atcoder.jp/contests/abc122/tasks/abc122_c

N, Q = [int(x) for x in input().split()]
S = input().strip()
idx = [S[i:i+2] == 'AC' for i in range(N - 1)]

for i in range(Q):
    l, r = [int(x) for x in input().split()]
    print(sum(idx[l - 1:r - 1]))


### FIXED CODE ###

# https://atcoder.jp/contests/abc122/tasks/abc122_c

N, Q = [int(x) for x in input().split()]
S = input().strip()
m = [0] * N
for i in range(1, N):
    if S[i-1:i+1] == 'AC':
        m[i] = m[i-1] + 1
    else:
        m[i] = m[i-1]

for i in range(Q):
    l, r = [int(x) for x in input().split()]
    print(m[r - 1] - m[l - 1])
### BUGGY CODE ###

import sys
input = sys.stdin.readline
h, w = map(int, input().split())
A = []
B = []
for i in range(h):
  row = list(map(int, input().split()))
  row.append(0)
  A.append(row)
A.append([0 for i in range(w+1)])

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

dp = [[set([]) for j in range(w+1)] for i in range(h+1)]
dp[0][0].add(abs(A[0][0] - B[0][0]))
for i in range(h):
  for j in range(w):
    for item in dp[i][j]:
      dif = abs(A[i][j+1] - B[i][j+1])
      dp[i][j+1].add(item+dif)
      dp[i][j+1].add(abs(item-dif))
      dif = abs(A[i+1][j] - B[i+1][j])
      dp[i+1][j].add(item+dif)
      dp[i+1][j].add(abs(item-dif))
print(min(dp[h-1][w-1]))


### FIXED CODE ###

import sys
def main():
  input = sys.stdin.readline
  h, w = map(int, input().split())
  A = []
  AB = []
  A_append = A.append
  AB_append = AB.append
  for i in range(h):
    row = list(map(int, input().split()))
    A_append(row)
  for i in range(h):
    row = [abs(A[i][j] - int(b)) for j, b in enumerate(input().split())]
    AB_append(row)
 
  dp_cur = [set([]) for _ in range(w)]
  dp_cur[0].add(AB[0][0])
  for i in range(h):
    dp_next = [set([]) for _ in range(w)]
    for j in range(w):
      if j < w - 1:
        add1 = dp_cur[j+1].add
        dif1 = AB[i][j+1]
      if i < h - 1:
        add2 = dp_next[j].add
        dif2 = AB[i+1][j]
      for item in dp_cur[j]:
        if j < w - 1:
          add1(item+dif1)
          add1(abs(item-dif1))
        if i < h - 1:
          add2(item+dif2)
          add2(abs(item-dif2))
    if i == h - 1:
      break
    dp_cur = dp_next
  print(min(dp_cur[w-1]))
if __name__ == '__main__':
  main()
### BUGGY CODE ###

N, K = map(int, input().split())
setlist = set()
tmp = N
ans = N
setlist.add(tmp)
while True:
  tmp = abs(tmp-K)
  ans = min(tmp,ans)
  if tmp in setlist:
    break
  setlist.add(tmp)
print(ans)



### FIXED CODE ###

def main():
  N, K = map(int,input().split())
  print(min(N%K, K-N%K))
  return 
main()
### BUGGY CODE ###

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

for i in range(n):
    _a = a.copy()
    _a.pop(i)
    print(max(_a))


### FIXED CODE ###

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

m = max(a)
idxs = [i for i, v in enumerate(a) if v == m]

if len(idxs) > 1:
    for i in range(n):
        print(m)

if len(idxs) == 1:
    idx = idxs[0]
    for i in range(n):
        if idx == i:
            _a = a.copy()
            _a.pop(i)
            print(max(_a))
        else:
            print(m)
### BUGGY CODE ###

import sys
from collections import deque

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


def bfs(N, v0, edge):

    d = [-1] * N
    d[v0] = 0
    q = deque()
    q.append(v0)

    while q:
        v = q.popleft()
        for nv in edge[v]:
            q.append(nv)
            d[nv] = max(d[nv], d[v] + 1)

    return max(d)


def v_sort(N, dag):

    degree = [0] * N
    for i in range(N):
        for v in dag[i]:
            degree[v] += 1

    ret = [v for v in range(N) if degree[v] == 0]

    return ret


def main():

    N, M = in_nn()

    edge = [[] for _ in range(N)]
    for i in range(M):
        x, y = in_nn()
        x, y = x - 1, y - 1
        edge[x].append(y)

    vs = v_sort(N, edge)
    ans = 0
    for v in vs:
        ans = max(ans, bfs(N, v, edge))

    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
from collections import deque

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


def topological_sort(N, dag):

    degree = [0] * N
    for i in range(N):
        for v in dag[i]:
            degree[v] += 1

    ret = [v for v in range(N) if degree[v] == 0]
    q = deque(ret)

    while q:
        v = q.popleft()
        for nv in dag[v]:
            degree[nv] -= 1
            if degree[nv] == 0:
                q.append(nv)
                ret.append(nv)

    return ret


def main():

    N, M = in_nn()

    edge = [[] for _ in range(N)]
    for i in range(M):
        x, y = in_nn()
        x, y = x - 1, y - 1
        edge[x].append(y)

    dp = [0] * N
    vs = topological_sort(N, edge)
    for v in vs:
        for nv in edge[v]:
            dp[nv] = max(dp[nv], dp[v] + 1)

    print(max(dp))


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

import numpy as np
N, M = map(int, input().split())
As = np.array( list( map(float, input().split()) ) )
As /=2.0

for _ in range(M):
    As[As.argmax()] /=  2.0
As *= 2.0
ans = np.sum(np.floor(As))
print(int(ans))

### FIXED CODE ###

import heapq
N, M = map(int, input().split())
a_list = [-float(i) for i in input().split()]
heapq.heapify(a_list)
for _ in range(M):
    _ = heapq.heapreplace(a_list, a_list[0]/2.0)
ans = sum([-int(i) for i in a_list])
print(ans)
### BUGGY CODE ###

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

N,M=map(int, sys.stdin.readline().split())
A=map(int, sys.stdin.readline().split())

match=[None,2,5,5,4,5,6,3,7,6]

#1桁の最小マッチ本数は2本（=1）なので、桁数の最大はN/2
keta=N/2	

dp=[ {} for i in range(keta+1) ] 
dp[0][0]=""

for i in range(keta):
	for j, num in dp[i].items():
		for a in A:
			match_cnt=match[a]
			if j+match_cnt  in dp[i+1]:
				dp[i+1][ j+match_cnt]= max ( dp[i+1][ j+match_cnt], dp[i][j]+str(a) )
			else:
				dp[i+1][ j+match_cnt]=dp[i][j]+str(a)		


for i in range(keta,-1,-1):
	if N in dp[i]:
		print dp[i][N]
		break


### FIXED CODE ###

T=[(1,2),(2,5),(3,5),(4,4),(5,5),(6,6),(7,3),(8,7),(9,6)]

N,M=map(int, raw_input().split())
A=map(int, raw_input().split())


P=[]
for i in A:
	P.append(T[i-1])


dp=[ None for i in range(N+1) ]
dp[0]=""


for i in range(N):
	#print "i :::: ",i,dp
	if dp[i] is not None:
		for num, match in P:
			if i+match<=N:

				if dp[i+match] is None:
					dp[i+match]=dp[i]+str(num)
				else:
					l1=len(dp[i+match])
					l2=len(dp[i]+str(num))
					if l1>l2:
						pass
					elif l1<l2:
						dp[i+match]=dp[i]+str(num)
					else:
						dp[i+match]=max( dp[i+match] , dp[i]+str(num) )


print dp[N]
### BUGGY CODE ###

#以上をまとめると
N=int(input())
A=list(map(int,input().split()))
Q=int(input())

trans=[[] for _ in range(Q)]
for i in range(Q):
    B,C=map(int,input().split())
    trans[i].append(B)
    trans[i].append(C)

S=sum(A)
#まずはじめの合計求める

for i in range(Q):
    B=trans[i][0]
    C=trans[i][1]
    cnt=A.count(B)
    A=[i if i != B else C for i in A]
    change=cnt*(C-B)
    S+=change
    print(S)

### FIXED CODE ###

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

num = [0]*(10**5+1)

S = []
 
#1 iterlation
S.append(sum(A))
for i in range(N):
    num[A[i]]+=1

    
for j in range(Q):
    if num[BC[j][0]] != 0:
        #Bに当たる交換するものがある時
        B = BC[j][0]
        C = BC[j][1]
        S.append(S[-1] + (C - B)*num[B] )
        #S[-1]で合計の一番最新のもの
        dammy = num[B]
        num[B] = 0
        num[C] += dammy
 
    else:
        B = BC[j][0]
        C = BC[j][1]
        S.append(S[-1])

        
for i in range(1,Q+1):
    print(S[i])
### BUGGY CODE ###

n, m = map(int, input().split())
l_lst = list()
for i in range(m):
    l_lst.append(input().split())

for i in range(0, len(l_lst)):
    for j in range(0, len(l_lst[i])):
        l_lst[i][j] = int(l_lst[i][j])

temp_cnt = 0
cnt = 0
for i in range(1, n+1):
    # print(i)
    for j in range(0, len(l_lst)):
        if l_lst[j][0] <= i and i <= l_lst[j][1]:
            temp_cnt += 1
        if temp_cnt == len(l_lst):
            cnt += 1
            # temp_cnt = 0
    temp_cnt = 0

print(cnt)

### FIXED CODE ###

n, m = map(int, input().split())
l_lst = list()
for i in range(m):
    l_lst.append(input().split())

for i in range(0, len(l_lst)):
    for j in range(0, len(l_lst[i])):
        l_lst[i][j] = int(l_lst[i][j])

max_lst = list()
min_lst = list()
for i in range(0, len(l_lst)):
    max_lst.append(l_lst[i][0])
    min_lst.append(l_lst[i][1])

max_int = max(max_lst)
min_int = min(min_lst)

cnt = 0
for i in range(1, n+1):
    if max_int <= i and i <= min_int:
        cnt += 1

print(cnt)
### BUGGY CODE ###

X=int(input())

count=1

while(count==1):
    for n in range(2,X):
        if (X%n==0):
            X+=1
            break
        if (n*n>X):
            count=0
            break
print(X)

### FIXED CODE ###

import math
X=int(input())

count=1

if X==2:
    count=0

while(count==1):
    for n in range(2,X):
        if (X%n==0):
            X+=1
            break
        if (n>math.sqrt(X)):
            count=0
            break
print(X)
### BUGGY CODE ###

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

flg = [True for _ in range(10 ** 6 + 1)]
for i in range(n-1):
    if a[i] == a[i+1]:
        flg[a[i]] = False
        
ans = 0
for i in range(n):
    if flg[a[i]]:
        ans += 1

    tmp = 1
    while tmp * a[i] <= 10 ** 6:
        flg[tmp * a[i]] = False
        tmp += 1

print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
a.sort()

flg = [True for _ in range(10 ** 6 + 1)]
for i in range(n-1):
    if a[i] == a[i+1]:
        flg[a[i]] = False

ans = 0
for x in set(a):
    if flg[x]:
        ans += 1

    tmp = 1
    while tmp * x <= 10 ** 6:
        flg[tmp * x] = False
        tmp += 1

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

s = list(input())
# s = list('ABCABC')
# s = list('ABCACCBABCBCAABCB')

# count = 0
#
# if len(s) < 3:
# 	print(0)
ccc = 0
# while :

i = 0
if len(s) >= 3:
    while i + 2 < len(s):
        if s[i] == 'A':
            if s[i + 1] == 'B' and s[i + 2] == 'C':
                s[i: i + 3] = ['B', 'C', 'A']
                ccc += 1
                if i - 2 >= 0:
                    i -= 2
                else:
                    i = 0
        i += 1
        # print(i)
        # print(s)
# print(s)
print(ccc)


### FIXED CODE ###

s = raw_input()

count = 0
a = 0
i = 0
l = len(s)
while i < len(s):
    if s[i] == 'A':
        a += 1
        i += 1
        continue

    if s[i] == 'B' and i < l - 1 and s[i + 1] == 'C':
        count += a
        i += 2
    else:
        a = 0
        i += 1

print count
### BUGGY CODE ###

2324
668
3648
182432
8168126


H, W = map(int, input().split())
S_list = [None] * H

for h in range(H):
    input_str = list(input())
    S_list[h] = [0 if char == '#' else 1 for char in input_str]


l_list = [[0] * W for _ in range(H)]
r_list = [[0] * W for _ in range(H)]
d_list = [[0] * W for _ in range(H)]
u_list = [[0] * W for _ in range(H)]
for h in range(H):
    for w in range(W):
        left_index = w
        right_index = W - w - 1
        up_index = h
        down_index = H - h - 1

        #left
        if left_index == 0:
            l_list[h][left_index] = S_list[h][left_index]
        else:
            l_list[h][left_index] = (l_list[h][left_index - 1] + 1) * S_list[h][left_index]

        #right
        if right_index == W - 1:
            r_list[h][right_index] = S_list[h][right_index]
        else:
            r_list[h][right_index] = (r_list[h][right_index + 1] + 1) * S_list[h][right_index]

        #up
        if up_index == 0:
            u_list[up_index][w] = S_list[up_index][w]
        else:
            u_list[up_index][w] = (u_list[up_index - 1][w] + 1) * S_list[up_index][w]

        #down
        if down_index == H - 1:
            d_list[down_index][w] = S_list[down_index][w]
        else:
            d_list[down_index][w] = (d_list[down_index + 1][w] + 1) * S_list[down_index][w]


max_light = 0
for h in range(H):
    for w in range(W):
        lights = l_list[h][w] + r_list[h][w] + u_list[h][w] + d_list[h][w] - 3
        max_light = max(max_light, lights)

print(max_light)


### FIXED CODE ###

#ref. https://atcoder.jp/contests/abc129/submissions/5906191
import numpy as np
import sys

def main():
    sin = sys.stdin.buffer
    H, W = map(int, sin.readline().split())
    grid = np.frombuffer(sin.read(H * (W + 1)), dtype="B") == ord(".")
    grid = grid.reshape((H, W + 1))[:, :-1]

    L = np.empty((H, W), dtype="i4")
    R = np.empty((H, W), dtype="i4")
    T = np.empty((H, W), dtype="i4")
    B = np.empty((H, W), dtype="i4")

    T[0] = grid[0]
    for i in range(1, H):
        T[i] = (T[i - 1] + 1) * grid[i]

    B[-1] = grid[-1]
    for i in range(H - 2, -1, -1):
        B[i] = (B[i + 1] + 1) * grid[i]

    L[:, 0] = grid[:, 0]
    for i in range(1, W):
        L[:, i] = (L[:, i - 1] + 1) * grid[:, i]

    R[:, -1] = grid[:, -1]
    for i in range(W - 2, -1, -1):
        R[:, i] = (R[:, i + 1] + 1) * grid[:, i]

    ans = (T + B + L + R - 3).max()
    print(ans)

main()
### BUGGY CODE ###

import sys

A = list(map(int, sys.stdin.read().rstrip().split("\n")))
n = A[0]
del A[0]

#shellSort
cnt = 0

G = []
tg = 1
while tg <= n:
    G.append(tg)
    tg = 3 * tg + 1
G.reverse()

m = len(G)

for i in range(m):
    g = G[i]
    # insertionSort
    for j in range(g, n):
        v = A[j]
        k = j - g
        while (k >= 0) and (A[k] > v):
            A[k + g] = A[k]
            k -= g
            cnt += 1
        A[k + g] = v

print(m)
print(*G)
print(cnt)
print("\n".join(map(str, A)))

### FIXED CODE ###

import sys

def insertionSort(A, n, g):
    global cnt
    for i in range(g, n):
        v = A[i]
        j = i - g
        while (j >= 0) and (A[j] > v):
            A[j + g] = A[j]
            j = j - g
            cnt += 1
        A[j + g] = v

def shellSort(A, n):
    G = [i for i in [262913, 65921, 16577, 4193, 1073, 281, 77, 23, 8, 1] if i <= n]
    m = len(G)
    for k in range(m):
        insertionSort(A, n, G[k])
    return m, G

A = list(map(int, sys.stdin))
n = A[0]
del A[0]

cnt = 0

m, G = shellSort(A, n)

print(m)
print(*G)
print(cnt)
print("\n".join(map(str, A)))
### BUGGY CODE ###

n = int(input())
a_list = list(map(int,input().split()))
for i in range(n):
    a_list[i] = [a_list[i],i+1]
a_list.sort()
ans = ""
for i in range(n):
    ans += str(a_list[i][1]) + " "
print(ans)

### FIXED CODE ###

n = int(input())
a_list = list(map(int,input().split()))
ans = [0]*n
for i in range(n):
    ans[a_list[i]-1] = i+1
print(" ".join(map(str,ans)))
### BUGGY CODE ###

"""
https://qiita.com/drken/items/03c7db44ccd27820ea0d


"""

S = input()
T = input()

"""
dp[i+1]][j+1]
Sのi番目とtのｊ番目まで見たときの共通する部分列の最大長さ
"""
dp = [[0 for _ in range(len(T)+1)] for _ in range(len(S)+1)]

next = {}
prev = {}
# 部分列の最大長さを求める
for i, s in enumerate(S):
    for j, t in enumerate(T):
        if s == t:
            #i番目とｊ番目が同じなら、dp[i+1][j+1]はそれまでの最大長さ＋１
            dp[i+1][j+1] = dp[i][j] + 1
            prev[(i+1, j+1)] = (i,j)
        else:
            #異なる場合はdp[i][j]かd[i+1][j]かdp[i][j+1]のどれかだけども、後者ふたつがi,jより小さいことはないから後ろ二つの大きいほうを採用
            if dp[i+1][j] >= dp[i][j+1]:
                dp[i+1][j+1] = dp[i+1][j]
                prev[(i+1, j+1)] = (i+1,j)
            else:
                dp[i+1][j+1] = dp[i][j+1]
                prev[(i+1, j+1)] = (i,j+1)

i, j = len(S), len(T)

substr = ""
while i != 0 and j != 0:
    if S[i-1] == T[j-1]:
        substr +=S[i-1] 
    i,j = prev[(i,j)]

print(substr[::-1])

### FIXED CODE ###

"""
https://qiita.com/drken/items/03c7db44ccd27820ea0d


"""
def main():
        
    S = input()
    T = input()

    """
    dp[i+1]][j+1]
    Sのi番目とtのｊ番目まで見たときの共通する部分列の最大長さ
    """
    dp = [[0 for _ in range(len(T)+1)] for _ in range(len(S)+1)]

    #prev = {}
    # 部分列の最大長さを求める
    for i, s in enumerate(S):
        for j, t in enumerate(T):
            if s == t:
                #i番目とｊ番目が同じなら、dp[i+1][j+1]はそれまでの最大長さ＋１
                dp[i+1][j+1] = dp[i][j] + 1
                #prev[(i+1, j+1)] = (i,j)
            else:
                #異なる場合はdp[i][j]かd[i+1][j]かdp[i][j+1]のどれかだけども、後者ふたつがi,jより小さいことはないから後ろ二つの大きいほうを採用
                dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1])
                #prev[(i+1, j+1)] = (i+1,j) if dp[i+1][j] >= dp[i][j+1] else (i,j+1)

    i, j = len(S), len(T)
    """
    なんかi+1,j+1がどのDPノードから更新されてできたのかをたどって、S[i],T[j]が同じであればそれを部分列に加えられるから～みたいな感じで部分列の後ろから作って最後にひっくり返すといいらしい
    
    """

    substr = ""
    while i != 0 and j != 0:
        # 同じ文字で＋１になっていた場合、その文字を部分列に加える
        if S[i-1] == T[j-1]:
            substr += S[i-1]
            i,j = i-1, j-1
        else:
            i,j = (i, j-1) if dp[i][j-1] >= dp[i-1][j] else (i-1, j)


    #TLEなのでやめた
    """
    while i != 0 and j != 0:
        if S[i-1] == T[j-1]:
            substr +=S[i-1] 
        i,j = prev[(i,j)]
    """
    print(substr[::-1])

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

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
s = 0
for b in B:
  s += (sum(c > b for c in C) * sum(a < b for a in A))
print(s)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
s = 0

A = sorted(A)
B = sorted(B)
C = sorted(C)

ia = -1
ic = -1

for b in B:
  while True:
    if ia == N-1 or A[ia+1]>=b: 
      break
    ia += 1
  while True:
    if ic == N-1 or C[ic+1]>b:
      break
    ic += 1
  s += (ia+1)*(N-ic-1)
    
print(s)
### BUGGY CODE ###

count = int(input())

ls = []

for i in range(count):
    ls.append(input())

max = 0
ans = []

for s in set(ls):
    i = ls.count(s)
    if i >= max:
        if i > max:
            ans = []

        ans.append(s)
        max = i

print('\n'.join(sorted(ans)))

### FIXED CODE ###

count = int(input())

ls = {}

for i in range(count):
    s = input()
    if s in ls:
        ls[s] += ls[s] + 1
    else:
        ls.setdefault(s, 1)

m = max(ls.values())

ans = [k for k, v in ls.items() if v == m]

print('\n'.join(sorted(ans)))