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

N=int(input())
S=[]
for i in range(N):
    S.append(input())
S.sort()
S.reverse()
ans=[]
while len(S):
    if len(S)==1:
        x = [S.pop(0), 1]
        ans.append(x)
        break
    x = [S.pop(0), 1]
    for i in S[:]:
        if x[0] == i:
            S.remove(i)
            x[1]+=1
    ans.append(x)

ans.sort(key=lambda x:x[1])
ans.reverse()
for i in range(len(ans)):
    t=ans[0][1]
    if ans[i][1]==t:
        print(ans[i][0])


### FIXED CODE ###

#
N=int(input())
S={}
for i in range(N):
    x=input()
    if x in S:
        S[x]+=1
    else:
        S[x]=1
t=max(S.values())
ans=[k for (k,v) in S.items() if v==t]
ans.sort()

for i in ans:
    print(i)
""""
#
while len(S):
    if len(S)==1:
        x = [S.pop(), 1]
        ans.append(x)
        break
    x = [S.pop(), 1]
    for i in S[:]:
        if x[0] == i:
            S.remove(i)
            x[1]+=1
    ans.append(x)
ans.sort()
ans.sort(key=lambda x:x[1],reverse=True)

for i in range(len(ans)):
    t=ans[0][1]
    if ans[i][1]==t:
        print(ans[i][0])



import queue

q=queue.Queue()
for i in S:
    q.put(i)

while not q.empty():
    x = [q.get(), 1]
    if len(ans)==0:
        ans.append(x)
        continue
    t=0
    for i in range(len(ans)):
        if x[0] == ans[i][0]:
            ans[i][1]+=1
            t+=1
            break
    if t==0:
        ans.append(x)
ans.sort()
ans.sort(key=lambda x:x[1],reverse=True)

for i in range(len(ans)):
    t=ans[0][1]
    if ans[i][1]==t:
        print(ans[i][0])

"""
### BUGGY CODE ###

def main():
    N, K = map(int, input().split())
    *A, = map(int, input().split())

    for _ in range(K):
        B = [0] * (N + 1)
        for i, x in enumerate(A):
            B[max(0, i - x)] += 1
            B[min(N - 1, i + x) + 1] -= 1
        for i in range(N):
            B[i + 1] += B[i]
        B.pop()
        if A == B: break
        A = B
    print(*A)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    N, K = map(int, input().split())
    *A, = map(int, input().split())

    for _ in range(min(K, 50)):
        B = [0] * (N + 1)
        for j in range(N):
            d = A[j]
            B[max(j - d, 0)] += 1
            B[min(j + d, N - 1) + 1] -= 1
        for i in range(N):
            B[i + 1] += B[i]
        A = B
    print(*A[:-1])


if __name__ == '__main__':
    main()

# import sys
# input = sys.stdin.readline
#
# sys.setrecursionlimit(10 ** 7)
#
# (int(x)-1 for x in input().split())
# rstrip()
#
# def binary_search(*, ok, ng, func):
#     while abs(ok - ng) > 1:
#         mid = (ok + ng) // 2
#         if func(mid):
#             ok = mid
#         else:
#             ng = mid
#     return ok
### BUGGY CODE ###

# encoding: utf-8
import math
N, M = map(int, input().split())

def distribute(pos, full, tmp):
    return memo[tmp][pos]

# define search range
p_max = int(M / 2) # M is prime if M has a factor p (> p_max)
ip_max = int(math.log2(M))

# create memo
memo = [[None] * N for i in range(ip_max + 1)] # max ip
for j in range(N): memo[0][j] = 1
for i in range(1, ip_max + 1): memo[i][N - 1] = 1

M_tmp = M
ans = 1
ip_tmp = 0 # temporary size of memo
for p in range(2, p_max + 1):
    # how many times M_tmp can be divided
    p_tmp = p
    for i_p in range(ip_max + 1):
        if M_tmp % p_tmp > 0: break
        p_tmp = p_tmp * p
    # escape if M_tmp cannot be divided
    if i_p < 1: continue
    # ans update (dp)
    ## expand memo if necessary
    if i_p > ip_tmp:
        for i in range(ip_tmp + 1, i_p + 1):
            memo_tmp = [0] * N
            sum_tmp = 0 # memo[i - 1][N - 1]
            vals = list(memo[i - 1])[::-1]
            for j, val in enumerate(vals):
                sum_tmp += val
                memo_tmp[N - 1 - j] = sum_tmp
            memo[i] = list(memo_tmp)
    ## search and count
    ans_tmp = distribute(0, i_p, i_p)
    ## add
    ans = (ans * ans_tmp) % (10 ** 9 + 7)
    # next
    M_tmp = M_tmp // (p_tmp // p)
    if M_tmp == 1: break

print(ans)

### FIXED CODE ###

# encoding: utf-8
import math
N, M = map(int, input().split())

ips = []
M_tmp = M
for p in range(2, int(math.sqrt(M)) + 1):
    if M_tmp % p > 0: continue
    for i_p in range(1, 33):
        if M_tmp % (p ** (i_p + 1)) > 0: break
    ips.append(i_p)
    M_tmp = M_tmp // (p ** i_p)
    if M_tmp == 1: break
else:
    ips.append(1)

#### O(NlogM) below ?
# create memo
## init
if len(ips) > 0: ip_max = max(ips)
else: ip_max = 0
memo = [[None] * N for i in range(ip_max + 1)] # max ip
for j in range(N): memo[0][j] = 1
for i in range(1, ip_max + 1): memo[i][N - 1] = 1
## fill
for i in range(1, ip_max + 1):
    sum_tmp = 0
    vals = list(memo[i - 1])[::-1]
    ptr_memo = memo[i]
    for j, val in enumerate(vals):
        sum_tmp += val
        ptr_memo[N - 1 - j] = sum_tmp
#### O(NlogM) above ?
        
# calculate ans
ans = 1
for i_p in ips:
    ans = (ans * memo[i_p][0]) % (10 ** 9 + 7)

if M == 1: print(1)
elif ip_max < 1: print(N)
else: print(ans)
### BUGGY CODE ###

num = int(input())

k = input().split()

mul = 1

for i in range(num):
    mul *= int(k[i])

if mul > 10**18:
    print(-1)

else:
    print(mul)


### FIXED CODE ###

num = int(input())

k = input().split()

for i in range(len(k)):
    k[i] = int(k[i])

k.sort()

mul = 1

for i in range(num):
    mul *= int(k[i])
    if mul > 10**18:
        break

if mul > 10**18:
    print(-1)

else:
    print(mul)
### BUGGY CODE ###

#素因数分解（10**6まで）
def soinsu_bunkai(m):
    pf=set()
    mm =m
    for i in pri_num:
        while mm %i==0:
            pf.add(i)
            mm //=i
    if mm !=1:
        pf.add(mm)
    return pf

    # 初期入力
import math
import sys
from bisect import bisect_left
from functools import reduce
input = sys.stdin.readline  #文字列では使わない
N = int(input())
A = list(map(int, input().split()))
intersect =set()
pair_w =set()

# 10**6までの素因数分解するために、「10**6のルート」までの素数を列挙
pri =10**6 +10
sq_pri =int(math.sqrt(pri))
#pri_num =prime_numbers(sq_pri +10 )
pri_num =[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1009]

#not coprimeの判定
gcd_a =reduce(math.gcd,A)
if gcd_a !=1:
    ans ="not coprime"

#pairwise coprimeの判定
else:
    A.sort()
    x =bisect_left(A,2)
    if N -x >= 78498 +1:
        #10**6以下の素数は78498個、鳩ノ巣原理により必ず素因数が重複、または素数以外の数が出ている
        ans ="setwise coprime"
        
    else:
        for a in A:
            aa =soinsu_bunkai(a)
            if intersect & aa:
                print("setwise coprime")
                sys.exit() #共通要素があったらpair_wではない→set_w
            intersect |=aa

        ans ="pairwise coprime"
print(ans)

### FIXED CODE ###

#高速素因数分解  osa_k法 
def osa_k(a):
    tmp = set()
    while a > 1:
        tmp.add(sieve[a])
        a //= sieve[a]
    return tmp

    # 初期入力
import math
import sys
from bisect import bisect_left
from functools import reduce
input = sys.stdin.readline  #文字列では使わない
N = int(input())
A = list(map(int, input().split()))
used =set()

#not coprimeの判定
gcd_a =reduce(math.gcd,A)
if gcd_a !=1:
    ans ="not coprime"

#pairwise coprimeの判定
else:
    MAXN =10**6 +10
    #osa_k法
    sieve = [i for i in range(MAXN+1)]
    p = 2
    while p*p <= MAXN:
        if sieve[p] == p:
            for q in range(2*p,MAXN+1,p):
                if sieve[q] == q:
                    sieve[q] = p
        p += 1
    
    ans ="pairwise coprime"
    for a in A:
        aa =osa_k(a)
        if used & aa:
            ans ="setwise coprime"
            break #共通要素があったらpair_wではない→set_w
        used |=aa
    
print(ans)
### BUGGY CODE ###

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


def read():
    N, M = map(int, input().strip().split())
    E_out = [list() for i in range(N)]
    E_in = [list() for i in range(N)]
    for i in range(M):
        x, y = map(int, input().strip().split())
        E_out[x-1].append(y-1)  # x -> E_out[x]
        E_in[y-1].append(x-1)   # E_in[x] -> x
    return N, M, E_in, E_out


def solve(N, M, E_in, E_out):
    dp = [-1 for i in range(N)]
    q = deque()
    for x in range(N):
        if len(E_out[x]) == 0:
            q.append(x)
            dp[x] = 0
    while q:
        x = q.pop()
        for y in E_in[x]:
            q.append(y)
            dp[y] = max(dp[y], dp[x] + 1)
    return max(dp)


if __name__ == '__main__':
    inputs = read()
    print("%s" % solve(*inputs))


### FIXED CODE ###

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


def read():
    N, M = map(int, input().strip().split())
    parents = [list() for i in range(N)]
    n_children = [0 for i in range(N)]
    for i in range(M):
        x, y = map(int, input().strip().split())
        n_children[x-1] += 1  # x -> E_out[x]
        parents[y-1].append(x-1)   # E_in[x] -> x
    return N, M, n_children, parents


def solve(N, M, n_children, parents):
    dp = [0 for i in range(N)]
    q = deque()
    r = deque()
    for x in range(N):
        if n_children[x] == 0:
            q.append(x)
    while q:
        x = q.pop()
        r.append(x)
        for parent in parents[x]:
            n_children[parent] -= 1
            if n_children[parent] == 0:
                q.append(parent)
    
    while r:
        x = r.pop()
        for y in parents[x]:
            dp[x] = max(dp[x], dp[y]+1)
    return max(dp)


if __name__ == '__main__':
    inputs = read()
    print("%s" % solve(*inputs))
### BUGGY CODE ###

def main():
    n=int(input())
    a=list(map(int,input().split()))
    ans=0
    temp=0
    MOD=10**9+7
    cnt1=[0]*60
    for num in a:
        for i in range(60):
            cnt1[i] += (num >> i) & 1
    for i in range(60):
        ans += cnt1[i] * (n - cnt1[i]) * pow(2,i,MOD)
    print(ans % MOD)


if __name__=='__main__':
    main()


### FIXED CODE ###

def main():
    n=int(input())
    a=list(map(int,input().split()))
    ans=0
    temp=0
    MOD=10**9+7
    cnt1=[0]*60
    for num in a:
        for i in range(60):
            cnt1[i] += (num >> i) & 1
    for i in range(60):
        ans += cnt1[i] * (n - cnt1[i]) * pow(2,i,MOD)
    print(ans % MOD)


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

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

### FIXED CODE ###

from operator import itemgetter
n = int(input())
a = list(map(int,input().split()))
ans = []
for i in range(0,n):
  ans.append([a[i],i+1])
ans= sorted(ans,key = itemgetter(0))
for j in range(n):
  print(ans[j][1],end = " ")
### BUGGY CODE ###

#coding: utf-8

sunuke_pow = 1
N = int(input())
for i in range(N):
    sunuke_pow  *= i+1
ans = sunuke_pow % (10**9 + 7)
print(ans)

### FIXED CODE ###

#coding: utf-8

sunuke_pow = 1
N = int(input())
for i in range(N):
    sunuke_pow *= i+1
    sunuke_pow = sunuke_pow % (10**9 + 7)
print(sunuke_pow)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


def send_query(n):
    print(n)
    resp = int(input())
    return resp


N = int(input())
l = 0
r = N-1
l_cur = send_query(0)
if l_cur == "Vacant":
    print(0)
    exit()
r_cur = send_query(N-1)
if r_cur == "Vacant":
    print(N-1)
    exit()

l = 0
cur = l_cur
r = N-1
while True:
    mid = (l+r)//2
    resp = send_query(mid)
    if resp == "Vacant":
        print("ans->", mid)
        break
    elif resp == cur:
        if (mid-l+1) % 2 == 1:
            r = mid-1
        else:
            l = mid+1
    else:
        if (mid-l+1) % 2 == 1:
            l = mid-1
        else:
            r = mid+1
    cur = resp


### FIXED CODE ###

n = int(input())
s = [0]*(n+1)

print(0)
a = input()
if a == "Vacant":
    exit()
s[0] = a
s[n] = a

l = 0
r = n
while True:
    m = (r+l)//2
    print(m)
    a = input()
    if a == "Vacant":
        exit()

    s[m] = a
    if s[l] == s[r]:
        if s[l] == s[m]:
            if (m-l) % 2 == 1:
                r = m
            else:
                l = m
        else:
            if (m-l) % 2 == 1:
                l = m
            else:
                r = m
    else:
        if s[l] == s[m]:
            if(m-l) % 2 == 1:
                r = m
            else:
                l = m
        else:
            if(m-l) % 2 == 1:
                l = m
            else:
                r = m
### BUGGY CODE ###

import itertools

n,m = [int(i) for i in input().split()]
a = [[int(i) for i in input().split()] for j in range(n)]

ans = 0
for i in itertools.combinations(range(n),m):
    v = 0
    for l in range(3):
        u = 0
        for j in i:
            u += a[j][l]
        v += abs(u)
    ans = max(ans,v)

print(ans)

### FIXED CODE ###

import itertools
n,m = [int(i) for i in input().split()]
a = [[int(i) for i in input().split()] for j in range(n)]

c = [0,1]
ans = 0
for l,j,k in itertools.product(c,repeat=3):
    ans = max(ans,sum(sorted([a[i][0]*(-1)**l+a[i][1]*(-1)**j+a[i][2]*(-1)**k for i in range(n)])[n-m:]))

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

N,M=map(int,input().split())
ab=[]
for i in range(M):
    a,b=map(int,input().split())
    ab.append([a,b])
ab.sort(key=lambda x :x[1])
num=0
while(ab):
    p=ab.pop(0)
    num+=1
    e=p[1]
    for i in reversed(range(len(ab))):
        if ab[i][0]<e:
            ab.pop(i)
print(num)

### FIXED CODE ###

from collections import deque
N,M=map(int,input().split())
ab=[]
for i in range(M):
    a,b=map(int,input().split())
    ab.append([a,b])

ab.sort(key=lambda x :x[1])
ans=deque()
for i in ab:
    if len(ans)>0:
        if i[0]<ans[-1] :
            continue
    ans.append(i[1])
print(len(ans))
### BUGGY CODE ###


N, M = map(int, input().split())
AB = [list(map(int, input().split())) for i in range(M)]
P = [0] * N
n = N - 1
q = [1]
j = 0
while n > 0:
    for i in range(M):
        if AB[i][0] == q[j]:
            if P[AB[i][1] - 1] == 0:
                P[AB[i][1] - 1] = q[j]
                q.append(AB[i][1])               
                AB[i] = [0, 0]
                n -= 1
        elif AB[i][1] == q[j]:
            if P[AB[i][0] - 1] == 0:
                P[AB[i][0] - 1] = q[j]
                q.append(AB[i][0])
                AB[i] = [0, 0]               
                n -= 1
    j += 1
print('Yes')
for i in range(1, N):
    print(P[i])

### FIXED CODE ###

from collections import deque
N, M = map(int, input().split())
R = [[] for i in range(N + 1)]
for i in range(M):
    A, B = map(int, input().split())
    R[A].append(B)
    R[B].append(A)
P = [-1] * (N + 1)
P[1] = 0
Q = deque()
Q.append(1)

while Q:
    v = Q.popleft()
    for r in R[v]:
        if P[r] == -1:
            P[r] = v
            Q.append(r)
print('Yes')
for p in P[2:]:
    print(p)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(2000000001)

def solve(n,k,ar,dp,x):
	ab = abs; mn = min
	if x>=n-2: return dp[x]
	if dp[x] != -1: return dp[x]
	m = 1e9
	for i in range(x+1,mn(n,x+k+1)):
		t = ab(ar[x]-ar[i])+solve(n,k,ar,dp,i)
		m = t if t<m else m
	dp[x] = m
	# pr(f'{x} => {dp[x]}')
	return dp[x]

def main():
	I = lambda:map(int,sys.stdin.readline().split())
	pr = lambda x:sys.stdout.write(f'{x}\n')
	n,k, ar = *I(), [*I()]
	dp = [-1]*(n-2) + [abs(ar[-2]-ar[-1]),0]
	# pr((n,k,ar,dp))
	pr(solve(n,k,ar,dp,0))

main()

### FIXED CODE ###

import sys
from functools import reduce
sys.setrecursionlimit(2000000001)

def solve(n,k,ar,dp,x):
	ab = abs; mn = min
	if x>=n-2: return dp[x]
	if not dp[x] is -1: return dp[x]
	# t = [ for i in range(x+1,mn(n,x+k+1))]
	t = map(lambda i:ab(ar[x]-ar[i])+solve(n,k,ar,dp,i), range(x+1,mn(n,x+k+1)))
	dp[x] = reduce(lambda a,b : a if a < b else b,t)
	return dp[x]

def main():
	I = lambda:map(int,sys.stdin.readline().split())
	pr = lambda x:sys.stdout.write(f'{x}\n')
	n,k, ar = *I(), [*I()]
	dp = [-1]*(n-2) + [abs(ar[-2]-ar[-1]),0]
	pr(solve(n,k,ar,dp,0))

main()
### BUGGY CODE ###

# import numpy as np
INF = 10 **18
N= int(input())
ans =1
A= list(map(int,input().split()))
for a  in A:
    ans *= a
ans = -1 if ans > INF else ans
print(ans)

### FIXED CODE ###

import numpy as np
INF = 10 **18
N= int(input())
# ans =1
A= list(map(int,input().split()))
# if 0 in A:
#     print(0)
# else:
def calc(A):
    if 0 in A:
        return 0
    ans = A.pop()
    for a in A:


        ans *= a
        if ans > INF:
            # print(-1)
            return -1
    return ans

# ans = np.prod(A)
# ans = -1 if ans > INF else ans
# hoge =[1]*(10 **5)
# hoge.append(10**18 +1)
# print(calc(hoge))
print(calc(A))
### BUGGY CODE ###

from sys import stdin
import math
a, b = [int(x) for x in stdin.readline().rstrip().split()]
def gcd(a,b):
    if b == 0:
        return a
    else:
        return gcd(b,a%b)
g = gcd(a,b)
h = []
answer = 0
for i in range(g):
    if g % (i+1) == 0:
        n = int(math.sqrt(i+1))
        t = 1
        for j in range(n):
            if j != 0:
                if (i+1) % (j+1) == 0:
                    t = 0
        if t == 1:
            answer += 1
print(answer)
            

### FIXED CODE ###

from sys import stdin
import math
a, b = [int(x) for x in stdin.readline().rstrip().split()]
def gcd(a,b):
    if b == 0:
        return a
    else:
        return gcd(b,a%b)
def factorize(n):
    b = 2
    fct = []
    while b * b <= n:
        while n % b == 0:
            n //= b
            fct.append(b)
        b = b + 1
    if n > 1:
        fct.append(n)
    return fct
g = gcd(a,b)
answer = factorize(g)
answer = list(set(answer))
print(len(answer) + 1)
### BUGGY CODE ###

S = input()
dp = [[0 for i in range(4)] for i in range(len(S)+1)]
MOD = 10**9+7
dp[0][3] = 1
for i in range(len(S)):
    x = S[i]
    if x == '?': k = 3
    else: k = 1
    for _ in range(k):
        dp[i+1][0] += dp[i][0] 
        dp[i+1][1] += dp[i][1] 
        dp[i+1][2] += dp[i][2] 
        dp[i+1][3] += dp[i][3] 
    if x == 'A':
        dp[i+1][0] +=  dp[i][3]
    elif x == 'B':
        dp[i+1][1] +=  dp[i][0]
    elif x == 'C':
        dp[i+1][2] += dp[i][1]
    else:
        dp[i+1][0] += dp[i][3]
        dp[i+1][1] += dp[i][0]
        dp[i+1][2] += dp[i][1]
    for j in range(3):
        if dp[1+i][j] > MOD: dp[i+1][j] %= MOD
print(dp[len(S)][2]%MOD)


### FIXED CODE ###

S = input()
dp = [[0 for i in range(4)] for i in range(len(S)+1)]
MOD = 10**9+7
dp[0][3] = 1
for i in range(len(S)):
    if S[i] == '?': k = 3
    else: k = 1
    for _ in range(k):
        dp[i+1][0] += dp[i][0] 
        dp[i+1][1] += dp[i][1] 
        dp[i+1][2] += dp[i][2] 
        dp[i+1][3] += dp[i][3] 
    if S[i] == 'A':
        dp[i+1][0] +=  dp[i][3]
    elif S[i] == 'B':
        dp[i+1][1] +=  dp[i][0]
    elif S[i] == 'C':
        dp[i+1][2] += dp[i][1]
    else:
        dp[i+1][0] += dp[i][3]
        dp[i+1][1] += dp[i][0]
        dp[i+1][2] += dp[i][1]
    for j in range(4):
        if dp[1+i][j] > MOD: dp[i+1][j] %= MOD
print(dp[len(S)][2]%MOD)
### BUGGY CODE ###

#### import ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)
def input():
  return sys.stdin.readline()[:-1]

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
  read_all = [tuple(map(int, input().split())) for _ in range(N)]
  return map(list,zip(*read_all))

#################

def Z_algo(S):
  n=len(S)
  A=[0]*n
  A[0]=n
  i=1
  j=0
  while i<n:
    while i+j<n and S[j]==S[i+j]: j+=1
    A[i]=j
    if j==0:
      i+=1
      continue
    k=1
    while i+k<n and k+A[k]<j:
      A[i+k]=A[k]
      k+=1
    i+=k
    j-=k
  return A

def dfs(pt,v,visited):
  n=len(pt)
  d=[-1]*n
  if visited[v]==True:
    return -1,visited
  check_visited = [False]*n
  check_visited[v] = True
  S = [v]
  d[v] = 0
  while S:
    v1 = S.pop()
    for i in pt[v1]:
      if check_visited[i] == False:
        check_visited[i] = True
        d[i] = d[v1] + 1
        S.append(i)
      else:
        print(-1)
        exit()
  return max(d),visited+check_visited

s = str(input())
t = str(input())

ls = len(s)
lt = len(t)

s2 = t + s*(lt//ls +2)
A = Z_algo(s2)

B = [False]*ls
for i in range(ls):
  if A[i+lt]>=lt:
    B[i]=True

pt = [[] for _ in range(ls)]
for i in range(ls):
  if B[i]==True:
    pt[i].append((i+lt)%ls)

visited = [False]*ls

ans = 0
for v in range(ls):
  if B[v]:
    tmp,visited = dfs(pt,v,visited)
    if tmp>ans:
      ans = tmp

print(ans)

### FIXED CODE ###

#### import ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)
def input():
  return sys.stdin.readline()[:-1]

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
  read_all = [tuple(map(int, input().split())) for _ in range(N)]
  return map(list,zip(*read_all))

#################

def Z_algo(S):
  n=len(S)
  A=[0]*n
  A[0]=n
  i=1
  j=0
  while i<n:
    while i+j<n and S[j]==S[i+j]: j+=1
    A[i]=j
    if j==0:
      i+=1
      continue
    k=1
    while i+k<n and k+A[k]<j:
      A[i+k]=A[k]
      k+=1
    i+=k
    j-=k
  return A

def dfs(pt,v,visited):
  if visited[v]==True:
    return -1,visited
  S = [v]
  now = 0
  while S:
    v1 = S.pop()
    for i in pt[v1]:
      if i != v:
        visited[i] = True
        now += 1
        S.append(i)
      else:
        print(-1)
        exit()
  return now,visited

s = str(input())
t = str(input())

ls = len(s)
lt = len(t)

s2 = t + s*(lt//ls +2)
A = Z_algo(s2)

B = [False]*ls
for i in range(ls):
  if A[i+lt]>=lt:
    B[i]=True

pt = [[] for _ in range(ls)]
for i in range(ls):
  if B[i]==True:
    pt[i].append((i+lt)%ls)

visited = [False]*ls

ans = 0
for v in range(ls):
  if B[v]:
    tmp,visited = dfs(pt,v,visited)
    if tmp>ans:
      ans = tmp

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

a, b, n = map(int, input().split())
if a == 0 or b == 0:
    print(0)
else:
    ans = 0
    prev = 0
    for x in range(n+1):
        tmp = (a*x)//b - a*(x//b)
        if prev > 0 and tmp == 0:
            ans = prev
            break
        prev = tmp
    else:
        ans = prev
    print(ans)

### FIXED CODE ###

a, b, n = map(int, input().split())
print((a*min(b-1,n))//b)
### BUGGY CODE ###

r,g,b,n=map(int,input().split())
ans=0
for i in range(3001):
    for j in range(3001):
        if (r*i+g*j)<=n:
            z=n-(r*i+g*j)
            if z%b==0:
                #print(i,j)
                ans+=1
        
print(ans)



### FIXED CODE ###

r,g,b,n=map(int,input().split())
ans=0
for i in range(3001):
    for j in range(3001):
        if (r*i+g*j)<=n:
            z=n-(r*i+g*j)
            if z%b==0:
                #print(i,j)
                ans+=1
        
print(ans)
### BUGGY CODE ###

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

sortedx = x[:]
sortedx.sort()

for i in range(n):
    ix = sortedx.index(x[i])
    #print(sortedx)
    #print(ix)
    if ix < n/2:
        print(sortedx[n//2])
    else:
        print(sortedx[n//2-1])

### FIXED CODE ###

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

sortedx = x[:]
sortedx.sort()

for i in range(n):
    #ix = sortedx.index(x[i])
    #print(sortedx)
    #print(ix)
    if x[i] <= sortedx[n//2-1]:
        print(sortedx[n//2])
    else:
        print(sortedx[n//2-1])