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

import copy
import math
n, a, b = map(int, input().split())
h = [int(input()) for _ in range(n)]

def is_ok(x):
    t = copy.deepcopy(h)
    y = x
    for i in range(n):
        t[i] -= b * x
        if t[i] > 0:
            y -= math.ceil(t[i] / (a - b))
    return y >= 0

ng = 0
ok = 10 ** 32
while abs(ok - ng) > 1:
    mi = (ok + ng) // 2
    if is_ok(mi):
        ok = mi
    else:
        ng = mi

print(ok)


### FIXED CODE ###

import math

n, a, b = map(int, input().split())
h = [int(input()) for _ in range(n)]

def is_ok(x):
    c = 0
    for i in range(n):
        t = h[i] - b * x
        if t <= 0:
            continue
        c += math.ceil(t / (a - b))
    return c <= x

ng = 0
ok = 10 ** 9
while abs(ok - ng) > 1:
    mi = (ok + ng) // 2
    if is_ok(mi):
        ok = mi
    else:
        ng = mi

print(ok)
### BUGGY CODE ###

n = int(input())
dam = list(map(int,input().split()))
yama =[0]*n
sum_dam = sum(dam)
dam2 = dam[0]*2 +2
for yama[0] in range(0,dam2,2):
  for i in range(1,n):
    yama[i] = dam[i-1]*2 - yama[i-1] 
    if yama[i] < 0:
      break
  if sum(yama) == sum_dam:
    joined = " ".join(map(str, yama))
    print(joined)
    break

### FIXED CODE ###

n = int(input())
dam = list(map(int,input().split()))
mountain =[0]*n
all_water = sum(dam)
def dam_water(num):
  sum_dam = 0
  for i in range(num,n,2):
    sum_dam += dam[i]
  return sum_dam

mountain[0] = all_water - 2 * (dam_water(1))

for i in range(1,n):
  mountain[i] = 2*dam[i-1] - mountain[i-1]

print(" ".join(map(str,mountain)))
### BUGGY CODE ###

h,w = map(int,input().split())
maps = [ input() for _ in range(h)]
ans = 0

U = [[0 for _ in range(w)] for _  in range(h)]
D = [[0 for _ in range(w)] for _  in range(h)]
L = [[0 for _ in range(w)] for _  in range(h)]
R = [[0 for _ in range(w)] for _  in range(h)]

for y in range(h):
    for x in range(w):
        if maps[y][x] == "#":
            U[y][x],L[y][x] = 0,0
        else:
            if y == 0 and x >= 1:
                U[0][x] = 1
                L[y][x] += 1 + L[y][x-1]
            elif x == 0 and y >= 1: 
                U[y][x] += 1 + U[y-1][x]
                L[y][0] = 1
            elif x == 0 and y == 0:
                U[y][x] = 1
                L[y][x] = 1
            else:
                U[y][x] += 1 + U[y-1][x]
                L[y][x] += 1 + L[y][x-1]

for y in range(h-1,-1,-1):
    for x in range(w-1,-1,-1):
        if maps[y][x] == "#":
            D[y][x],R[y][x] = 0,0
        else:
            if y == h-1 and x < w-1:
                D[y][x] = 1
                R[y][x] += 1 + R[y][x+1]
            elif x == w-1 and y < h-1:
                D[y][x] += 1 + D[y+1][x]
                R[y][x] = 1
            elif  x == w-1 and y == h-1:
                D[y][x] = 1
                R[y][x] = 1
            else:
                D[y][x] += 1 + D[y+1][x]
                R[y][x] += 1 + R[y][x+1]

ans = 0
#AnsMap = [[0 for _ in range(w)] for _  in range(h)]
for i in range(h):
    for j in range(w):
        #AnsMap[i][j] = L[i][j]+R[i][j]+U[i][j]+D[i][j] - 3
        ans = max(ans,L[i][j]+R[i][j]+U[i][j]+D[i][j] - 3)
print(ans)

### FIXED CODE ###

h,w = map(int,input().split())
maps = [ input() for _ in range(h)]
ans = 0

U = [[0 for _ in range(w)] for _  in range(h)]
D = [[0 for _ in range(w)] for _  in range(h)]
L = [[0 for _ in range(w)] for _  in range(h)]
R = [[0 for _ in range(w)] for _  in range(h)]

for y in range(h):
    for x in range(w):
        if maps[y][x] == "#":
            U[y][x],L[y][x] = 0,0
        else:
            if y == 0 and x >= 1:
                U[0][x] = 1
                L[y][x] += 1 + L[y][x-1]
            elif x == 0 and y >= 1: 
                U[y][x] += 1 + U[y-1][x]
                L[y][0] = 1
            elif x == 0 and y == 0:
                U[y][x] = 1
                L[y][x] = 1
            else:
                U[y][x] += 1 + U[y-1][x]
                L[y][x] += 1 + L[y][x-1]

for y in range(h-1,-1,-1):
    for x in range(w-1,-1,-1):
        if maps[y][x] == "#":
            D[y][x],R[y][x] = 0,0
        else:
            if y == h-1 and x < w-1:
                D[y][x] = 1
                R[y][x] += 1 + R[y][x+1]
            elif x == w-1 and y < h-1:
                D[y][x] += 1 + D[y+1][x]
                R[y][x] = 1
            elif  x == w-1 and y == h-1:
                D[y][x] = 1
                R[y][x] = 1
            else:
                D[y][x] += 1 + D[y+1][x]
                R[y][x] += 1 + R[y][x+1]

ans = 0
for i in range(h):
    for j in range(w):
        ans = max(ans,L[i][j]+R[i][j]+U[i][j]+D[i][j] - 3)
print(ans)
### BUGGY CODE ###

import fractions
from functools import reduce

def gcd(*numbers):
    return reduce(fractions.gcd, numbers)

k = int(input())

result = 0

for a in range(1, k+1):
  for b in range(1, k+1):
    for c in range(1, k+1):
      result += gcd(a, b, c)

print(result)

### FIXED CODE ###

import math
import itertools

k = int(input())
result = 0

for a in range(1, k+1):
  for b in range(a+1, k+1):
    for c in range(b+1, k+1):
      r = math.gcd(math.gcd(a, b), c)
      r *= 6
      result += r

for a in range(1, k+1):
  for b in range(a+1, k+1):
    r = math.gcd(a, b)
    r *= 6
    result += r
    
for a in range(1, k+1):
  result += a

print(result)
### BUGGY CODE ###

import itertools
N, K = map(int, input().split())

Ns = []
for n in range(N+1):
    Ns.append(n)

# print(Ns)

ans = set()
for k in range(K, N+2):
    nums = itertools.combinations(Ns, k)
    # print(list(nums))
    for num in nums:
        tmp = f'{str(sum(list(num)))} + {str(k)}'
        ans.add(tmp)
print((len(ans)))


### FIXED CODE ###

N, K = map(int, input().split())
mod = 10 ** 9 + 7

ans = 0
for k in range(K, N+2):
    upper = k * ((N-k+1)+N) // 2
    lower = k * (k-1) // 2
    ans += upper - lower + 1
    ans %= mod
print(ans)
### BUGGY CODE ###

n,q=map(int,input().split())
s=input()
for i in range(q):
    l,r=map(int,input().split())
    print(s[l-1:r].count('AC'))


### FIXED CODE ###

n,q=map(int,input().split())
s=input()
count=[0]*n
for i in range(1,n):
    count[i]+=count[i-1]
    if s[i-1:i+1]=="AC":count[i]+=1
for i in range(q):
    l,r=map(int,input().split())
    print(count[r-1]-count[l-1])
### BUGGY CODE ###

N,A,B=map(int,input().split())
M=0
ans=0
for i in range(10**18):
    if M+A+B<=N:
        M=M+A+B
        ans+=A
    elif M+A<=N:
        ans+=A
        break
    else:
        A=N-M
        ans+=A
        break
print(ans)

### FIXED CODE ###

N,A,B=map(int,input().split())
M=0
ans=0
C=A+B
c=N//C
ans=A*c
if N-C*c<A:
    ans+=N-C*c
else:
    ans+=A
print(ans)
### BUGGY CODE ###

# ABC 065 B

N = int(input())
A = [int(input()) for _ in range(N)]

i = 1
q = []
while i != 2:
    q.append(i)
    if A[i-1] in q:
        print(-1)
        break
    i = A[i-1]
else:
    print(len(q))

### FIXED CODE ###

# ABC 065 B

N = int(input())
A = [int(input()) for _ in range(N)]

i = 1
s = 0
while i != 2:
    s += 1
    A[i-1], i = 1, A[i-1]
    if i == 1:
        print(-1)
        break
else:
    print(s)
### BUGGY CODE ###

[n, k] = [int(s) for s in input().split()]
a = [int(s) for s in input().split()]

l = []
c = 1
for _ in range(n):
    c = a[c - 1]
    if len(l) + 1 == k:
        print(c)
        break
    elif c in l:
        i = l.index(c)
        l2 = l[i:]
        print(l2[(k - i) % len(l2) - 1])
        break
    else:
        l.append(c)

### FIXED CODE ###

[n, k] = [int(s) for s in input().split()]
a = [int(s) for s in input().split()]

l = []
c = 1
l2 = [0 for _ in range(n)]
for _ in range(n):
    c = a[c - 1]
    if len(l) + 1 == k:
        print(c)
        break
    elif l2[c - 1] == 1:
        i = l.index(c)
        l2 = l[i:]
        print(l2[(k - i) % len(l2) - 1])
        break
    else:
        l.append(c)
        l2[c - 1] = 1
### BUGGY CODE ###

import sys
readline = sys.stdin.readline

def main():

	#s = tuple(input())
	s = input()
	length = len(s)

	dp = [[0]*13 for _ in range(length)]
	MOD = 10**9+7
	if s[-1] == '?':
		for i in range(10):
			dp[0][i] = 1
	else:
		dp[0][int(s[-1])] = 1

	for i in range(1,length):
		if s[-i-1] != '?':
			num = (int(s[-i-1]) * (10**i)) % 13
			for j in range(13):
				dp[i][(num+j)%13] = dp[i-1][j] % MOD
		else:
			num = (10**i) % 13
			for j in range(10):
				for k in range(13):
					dp[i][(num*j+k)%13] += dp[i-1][k] % MOD

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

if __name__ == '__main__':
	main()


### FIXED CODE ###

INF = 10 ** 9 + 7

S = input()
# dp[i][j]はうしろからi桁を13で割った余りがjであるものの個数
dp = [[0] * 13 for _ in range(len(S) + 1)]
dp[0][0] = 1
mul = 1

for i in range(len(S)):
    x = S[-(i + 1)]
    if x == "?":
        for k in range(10):
            for j in range(13):
                dp[i + 1][(mul * k + j) % 13] += dp[i][j]
                dp[i + 1][(mul * k + j) % 13] %= INF
    else:
        k = int(x)
        for j in range(13):
            dp[i + 1][(mul * k + j) % 13] += dp[i][j]
            dp[i + 1][(mul * k + j) % 13] %= INF
    mul = mul * 10 % 13  # 計算量削減のためここで13で割っている

print(dp[len(S)][5])
### BUGGY CODE ###

N = int(input())
S = []
ans = 0
for i in range(N):
    s = [v for v in input()]
    s.sort()

    for t in S:
        if s == t:
            ans += 1

    S.append(s)

print(ans)

### FIXED CODE ###

N = int(input())
dic = {}
ans = 0
for i in range(N):
    s = [v for v in input()]
    s.sort()
    word = ''.join(s)    

    if word in dic:
        dic[word] += 1
    else:
        dic[word] = 1

for word in dic:
    num = dic[word]
    ans += (num * (num - 1)) // 2

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

n = int(input())
a = list(map(int,input().split()))
a2 = sorted(a) 
a3 = list(set(a2))

z = []
for i in range(len(a3)):
     u = a.count(a3[i])
     z.append(u)


for j in range(n):
    count = 1
    for i in z:
        count += i*(i-1)/2
    count -= z[a3.index(a[j])]
    print(int(count))

### FIXED CODE ###

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

u = collections.Counter(a)

sume = 0
for i in u.values():
    sume += int(i*(i-1)/2)

for k in range(n):
    s = u[a[k]]
    print(sume-s+1)
### BUGGY CODE ###

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

while (len(a)>1):
    b=fractions.gcd(a[0],a[1])
    if b==1:
        print(1)
        exit()
    del a[1]
    del a[0]
    a.append(b)
    a=list(set(a))
print(a[0])

### FIXED CODE ###

import fractions
n=int(input())
a=list(map(int,input().split()))
tmp=a[0]
for i in range(1,n):
    tmp=fractions.gcd(a[i],tmp)
print(tmp)
### BUGGY CODE ###

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

dp = [None for _ in range(N)]
# initiate
dp[0] = 0

for i in range(1, N):
    min_ = min(dp[k] + abs(H[k]-H[i]) for k in range(max(0, i-K), i))
    dp[i] = min_

print(dp[-1])
pass

### FIXED CODE ###

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

dp = [None for _ in range(N)]
# initiate
dp[0] = 0

for i in range(1, N):
    min_ = min(dp[k] + abs(H[k]-H[i]) for k in range(max(0, i-K), i))
    dp[i] = min_

print(dp[-1])
pass
### BUGGY CODE ###

N,M,K=list(map(int,input().split()))
AB=[list(map(int,input().split())) for i in range(M)]
CD=[list(map(int,input().split())) for i in range(K)]

user=[0 for i in range(N+1)]
graph_ab=[[] for i in range(N+1)]
graph_cd=[[] for i in range(N+1)]
for i in range(M):
    a,b=AB[i]
    graph_ab[a].append(b)
    graph_ab[b].append(a)
for i in range(K):
    c,d=CD[i]
    graph_cd[c].append(d)
    graph_cd[d].append(c)
for j in range(1,N+1):
    stack=[j]
    visited=[-1 for i in range(N+1)]
    visited[j]=0
    while stack:
        x=stack.pop(0)
        for i in graph_ab[x]:
            if visited[i]<0:
                visited[i]=1
                stack.append(i)
                
    for i in range(1,N+1):
        if visited[i]==1 and (i not in graph_ab[j]) and (i not in graph_cd[j]):
            user[j]+=1
del user[0]
print(*user)

### FIXED CODE ###

from  collections import deque,Counter
N,M,K=list(map(int,input().split()))
AB=[list(map(int,input().split())) for i in range(M)]
CD=[list(map(int,input().split())) for i in range(K)]

user=[0 for i in range(N+1)]
graph_ab=[[] for i in range(N+1)]
graph_cd=[[] for i in range(N+1)]
visited=[0 for i in range(N+1)]
for i in range(M):
    a,b=AB[i]
    graph_ab[a].append(b)
    graph_ab[b].append(a)
time=0
for j in range(1,N+1):
    if visited[j]==0:
        stack=deque([j])
        time+=1
        visited[j]=time
        while stack:
            x=stack.popleft()
            for i in graph_ab[x]:
                if visited[i]==0:
                    visited[i]=time
                    stack.append(i)
#     visit_list[j]=visited
counter=Counter(visited) 
for i in range(K):
    c,d=CD[i]
    if visited[c]==visited[d]:
        graph_cd[c].append(d)
        graph_cd[d].append(c)

for i in range(1,N+1):
    user[i]=counter[visited[i]]-len(graph_ab[i])-len(graph_cd[i])-1

del user[0]
print(*user)
### BUGGY CODE ###

n = int(input())
s = list(input())
q = int(input())
for i in range(q):
  que = input().split()
  if que[0] == '1':
    s[int(que[1])-1] = que[2]
  else:
    c = set(s[int(que[1])-1:int(que[2])])
    print(len(c))

### FIXED CODE ###

import sys
readline = sys.stdin.readline

from bisect import bisect_left, insort_left

def main():
    n = int(readline())
    s = list(readline().rstrip())
    q = int(readline())
    
    chk_abc = [[] for i in range(26)]
    for i, si in enumerate(s):
        ci = ord(si) - 97
        chk_abc[ci].append(i)
        
    ans = []
    for _ in range(q):
        cmd, i, j = readline().rstrip().split()
        i = int(i) - 1
        
        if cmd == "1":
            if s[i] == j:
                continue
            c1 = ord(s[i]) - 97
            prev = chk_abc[c1]
            c2 = ord(j) - 97
            prev.pop(bisect_left(prev, i))
            s[i] = j
            insort_left(chk_abc[c2], i)
            
        else:
            j = int(j) - 1
            num = 0
            for chk in chk_abc:
                le = len(chk)
                k = bisect_left(chk, i, 0, le)
                if k == le:
                    continue
                if i <= chk[k] <= j:
                    num += 1
            ans.append(num)

    print(*ans, sep="\n")

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

class BIT:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

mod = 998244353

N = int(input())
xy = [list(map(int,input().split())) for _ in range(N)]
xy.sort(key=lambda x:x[1])
for i in range(N):
    xy[i][1] = i+1
xy.sort()
for i in range(N):
    xy[i][0] = i

# x<xi,y<yi
l1 = [0]*N
# x<xi,y>yi
l2 = [0]*N
# x>xi,y<yi
r1 = [0]*N
# x>xi,y>yi
r2 = [0]*N

bit = BIT(N)
for i in range(N):
    l1[i] = bit.sum(xy[i][1])
    l2[i] = i-l1[i]
    r1[i] = xy[i][1]-l1[i]-1
    r2[i] = N-xy[i][1]-l2[i]
    bit.add(xy[i][1],1)
    


pow2 = [1]*(N+1)
for i in range(N):
    pow2[i+1] = 2*pow2[i]%mod

ans = pow2[N-1]*N%mod
for i in range(N):
    ans += pow2[l1[i]+l2[i]+r1[i]+r2[i]]
    ans -= pow2[l1[i]+r1[i]]
    ans -= pow2[l2[i]+r2[i]]
    ans -= pow2[l1[i]+l2[i]]
    ans -= pow2[r1[i]+r2[i]]
    ans += pow2[l1[i]]
    ans += pow2[l2[i]]
    ans += pow2[r1[i]]
    ans += pow2[r2[i]]
    ans -= 1
    ans %= mod

print(ans)

### FIXED CODE ###

from operator import itemgetter

class BIT:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

mod = 998244353

N = int(input())
xy = [list(map(int,input().split())) for _ in range(N)]
xy.sort(key=itemgetter(1))
for i in range(N):
    xy[i][1] = i+1
xy.sort(key=itemgetter(0))

pow2 = [1]*(N+1)
for i in range(N):
    pow2[i+1] = 2*pow2[i]%mod

ans = pow2[N-1]*N%mod

bit = BIT(N)
for i in range(N):
    l1 = bit.sum(xy[i][1])
    l2 = i-l1
    r1 = xy[i][1]-l1-1
    r2 = N-xy[i][1]-l2
    bit.add(xy[i][1],1)
    ans += (pow2[l2]-1)*(pow2[r1]-1)*pow2[r2]*pow2[l1]
    ans += (pow2[r2]-1)*(pow2[l1]-1)*(pow2[l2]+pow2[r1]-1)
    ans %= mod

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

from itertools import combinations
n,k=map(int,input().split())
*A,=sorted(map(int,input().split()))
mod=10**9+7

mi,ma=0,0
for i in list(combinations(A,k)):
    mi+=i[0]
    ma+=i[-1]
print((ma-mi)%mod)


### FIXED CODE ###

M,K = map(int,input().split())
L = list(map(int,input().split()))
L.sort()
ANS = 0
 
def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod
 
mod = 10**9+7 #出力の制限
N = 10**5
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル
 
for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )
 
for j in range(M-K+1):
    ANS += (L[K-1+j] - L[M-K-j])*cmb(K-1+j,K-1,mod)
 
print(ANS % mod)
### BUGGY CODE ###

def LCS():
 x = raw_input()
 y = raw_input()
 i = len(x)
 j = len(y)

 dsp = [[0 for col in range(j+1)] for row in range(i+1)]
 for i in range(1,i+1):
  for j in range(1,j+1):
   if x[i-1] == y[j-1]:
    dsp[i][j] = dsp[i-1][j-1]+1
   else:
    dsp[i][j] = max(dsp[i-1][j],dsp[i][j-1])
 return dsp[i][j]

q = input()
for i in range(q):
 print LCS()

### FIXED CODE ###

def LCS():
 x = raw_input()
 y = raw_input()
 a, b = len(x), len(y)
 dsp1 = [0 for i in xrange(b+1)]
 for i in xrange(a):
  dsp2 = dsp1+[]
  for j in xrange(b):
   if x[i] == y[j]:
    dsp1[j+1] = dsp2[j] + 1
   elif dsp1[j+1] < dsp1[j]:
    dsp1[j+1] = dsp1[j]
 print max(dsp1)
  
n = input()
for a in xrange(n):
    LCS()
### BUGGY CODE ###

# #A
# a,b = map(int,input().split())

# print((a+b) if b%a==0 else (b-a))

#B
# n,m = map(int,input().split())
# aa = []
# kk=[]
# for i in range(n):
#     tmp = list(map(int,input().split()))
#     kk.append(tmp[0])
#     aa.append(tmp[1:])

# aaa = []
# for a in aa:
#     for ai in a:
#         aaa.append(ai)
# ans=0
# for i in range(m):
#     if aaa.count(i+1)==n:
#         ans+=1
# print(ans)

#C
n = int(input())
aa = list(map(int,input().split()))

# print(aa)
def mod(xx):
    bb=[]
    for i in range(len(xx)):
        b = xx[i] if (0<xx[i] and xx[i] <= min(xx)) else xx[i] % min(xx)
        if b>0:
            bb.append(b)
    return bb

while True:
    bb = mod(aa)
    # print(bb)
    if min(aa)==min(bb):
        break
    aa=bb
print(min(bb))

### FIXED CODE ###

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

def gcd(a, b):
	while b:
		a, b = b, a % b
	return a

ans=aa[0]
for i in range(1,n):
    ans = gcd(ans, aa[i])
print(ans)
### BUGGY CODE ###

N=int(input())
l=[]
for x in range(0,N):
    l.append(input())
for x in range(0,N):
    l[x]=sorted(list(l[x]))
ans=0
for i in range(0,N):
    for j in range(i+1,N):
        if l[i]==l[j]:
            ans=ans+1
print(ans)

### FIXED CODE ###

N=int(input())
l=[]
for x in range(0,N):
    l.append(input())
for x in range(N):
    k=list(l[x])
    k.sort()
    k=''.join(k)
    l[x]=k
l.sort()
k=1
ans=0
for i in range(N-1):
    if l[i]==l[i+1]:
        k+=1
    else:
        ans+=k*(k-1)//2
        k=1
ans+=k*(k-1)//2
print(ans)
### BUGGY CODE ###

def solve():
    N = int(input().strip())
    S = input().strip()
    low = 0
    high = (N >> 1) + 1
    while high - low > 1:
        mid = (high + low) >> 1
        is_match = False
        m = N-mid-mid+1
        for i in range(0, m):
            if S[i:i+mid] in S[i+mid:]:
                is_match = True
                break
        if is_match:
            low = mid
        else:
            high = mid
    return low


if __name__ == '__main__':
    outputs = solve()
    if outputs is not None:
        print("%s" % str(outputs))

### FIXED CODE ###

import random
from collections import defaultdict


class RollingHash():

    def __init__(self, S, b=3491, m=999999937):
        """任意の基数と法でハッシュを生成する"""
        n = len(S)
        self.prefix = prefix = [0] * (n+1)
        self.power = power = [1] * (n+1)
        self.b = b
        self.m = m
        for i in range(n):
            c = ord(S[i])
            prefix[i+1] = (prefix[i] * b + c) % m
            power[i+1] = (power[i] * b) % m
    
    def get(self, l, r):
        """S[l, r) のハッシュを求める"""
        return (self.prefix[r] - self.power[r-l] * self.prefix[l]) % self.m
    
    def concat(self, h1, h2, l2):
        """S1+S2 のハッシュを、それぞれのハッシュから求める"""
        return (self.power[l2] * h1 + h2) % self.m
    
    def lcp(self, l1, r1, l2, r2):
        """S[l1, r1) とS[l2, r2) の最大共通接頭辞を求める"""
        low = 0
        high = min(r1-l1, r2-l2) + 1
        while high - low > 1:
            mid = (high + low) // 2
            if self.get(l1, l1 + mid) == self.get(l2, l2 + mid):
                low = mid
            else:
                high = mid
        return low


def read():
    N = int(input().strip())
    S = input().strip()
    return N, S


def solve(N, S):
    ans = []
    for m in [999999937, 10**9+7]:
        b = random.randint(10000, m-1)
        rh = RollingHash(S, b=b, m=m)
        low = 0
        high = (N+1) // 2 + 1
        dmax = defaultdict(int)
        dmin = defaultdict(int)
        while high - low > 1:
            dmax.clear()
            dmin.clear()
            mid = (high + low) // 2
            for i in range(0, N-mid+1):
                h = rh.get(i, i+mid)
                dmax[h] = max(dmax[h], i+1)
                dmin[h] = max(dmin[h], N+1-i)
            is_match = False
            for h in dmax.keys():
                if dmax[h] - (N+2 - dmin[h]) >= mid:
                    is_match = True
                    break
            if is_match:
                low = mid
            else:
                high = mid
        ans.append(low)
    return min(ans)


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))
### BUGGY CODE ###

import sys
import math
import functools
import numpy as np
stdin = sys.stdin
mod = 10**9 + 7

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
sa = lambda h: [list(map(int, stdin.readline().split())) for i in range(h)]

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a
def lcm(a, b):
    return a * b // gcd (a, b)
def lcm_n(nums):
    return functools.reduce(lcm, nums)

n = ni()
a = na()
a_lcm = lcm_n(a)
a = np.array(a)
# ans = 0
# for ai in a:
#     ans += a_lcm // ai
#     ans %= mod
# print(ans)
ans = np.sum(a_lcm // a) % mod
print(ans)

### FIXED CODE ###

import sys
import math
import functools
stdin = sys.stdin
mod = 10**9 + 7

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
sa = lambda h: [list(map(int, stdin.readline().split())) for i in range(h)]

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a
def lcm(a, b):
    return a * b // gcd (a, b)
def lcm_n(nums):
    return functools.reduce(lcm, nums)

n = ni()
a = na()
a_lcm = lcm_n(a)
ans = 0
for ai in a:
    ans += a_lcm // ai
ans %= mod
print(ans)
### BUGGY CODE ###

n = int(input())
l1 = list()
for i in range(n):
  l1.append(input())
l2 = set(l1)
M = 1
l3 = []
for s in l2:
  if l1.count(s) > M:
    M=l1.count(s)
    l3=[]
    l3.append(s)
  elif l1.count(s) == M:
    l3.append(s)
  else:
    continue
l4=sorted(l3)
for i in range(len(l4)):
  print(l4[i])

### FIXED CODE ###

import collections
n = int(input())
l1 = list()
for i in range(n):
  l1.append(input())
c = collections.Counter(l1)
m = max(c.values())
C = sorted(c.items())
for i in C:
  if i[1]==m:
    print(i[0])