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

#!/usr/bin/env python3
import math

primes = [-1 for i in range(100000)]

def is_prime(x):
    global primes

    if primes[x] != -1:
        return primes[x] == 1

    if x < 2:
        primes[x] = 0
        return False
    if x == 2 or x == 3 or x == 5:
        primes[x] = 1
        return True
    if x % 2 == 0 or x % 3 == 0 or x % 5 == 0:
        primes[x] = 0
        return False

    sx = math.sqrt(x)
    prime = 7
    step = 4
    while prime <= sx:
        if x % prime == 0:
            primes[x] = 0
            return False

        prime += step
        step = 6 - step

    primes[x] = 1
    return True

def main():
    Q = int(input())
    l = []
    r = []
    for i in range(Q):
        sa = input().split(' ')
        l.append(int(sa[0]))
        r.append(int(sa[1]))

#    r_max = 100000
#    primes = [True for i in range(r_max)]
#    primes[0] = False
#    primes[1] = False
#    i = 2
#    max_i = int(math.sqrt(r_max))
#    while i <= max_i:
#        for j in range(i * i, r_max, i):
#            primes[j] = False
#        while i <= max_i:
#            i += 1
#            if primes[i]:
#                break

    for i in range(Q):
        c = 0
        for j in range(l[i], r[i] + 1, 2):
            if is_prime(j) and is_prime(int((j + 1) / 2)):
                c += 1
        print(c)


if __name__ == '__main__':
    main()



### FIXED CODE ###

#!/usr/bin/env python3
import math

def main():
    Q = int(input())
    l = []
    r = []
    for i in range(Q):
        na = list(map(int, input().split()))
        l.append(na[0])
        r.append(na[1])

    r_max = 100000
    primes = [True for i in range(r_max)]
    like_numbers = [0 for i in range(r_max)]

    primes[0] = primes[1] = False
    max_i = int(math.sqrt(r_max))
    i = 2
    while i <= max_i:
        primes[i] = True
        for j in range(i * i, r_max, i):
            primes[j] = False
        while i <= max_i:
            i += 1
            if primes[i]:
                break

    for i in range(3, r_max, 2):
        if primes[i] and primes[int((i + 1) / 2)]:
            like_numbers[i] = 1

    c = 0
    for i in range(3, r_max, 2):
        if like_numbers[i]:
            c += 1
        like_numbers[i] = c


    for i in range(Q):
        if l[i] == 1:
            print(like_numbers[r[i]])
        else:
            print(like_numbers[r[i]] - like_numbers[l[i] - 2])

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

K = input()
K_int = int(K)
digit = len(K)
D = int(input())
MOD = 10**9 + 7

# dp[d][r][i] : (d+1)桁目の数がiで、それまでの桁の数の和をDで割ったときの余りがrとなる組合せ
dp = [[[0]*10 for r in range(D)] for d in range(digit)]

for i in range(10):
  dp[0][i%D][i] += 1

for d in range(1, digit):
  for r in range(D):
    s = sum(dp[d-1][r])
    for i in range(10):
      dp[d][(r+i)%D][i] += s
      dp[d][(r+i)%D][i] %= MOD

ans = 0
r = 0
for _d, k in enumerate(K, 1):
  d = digit - _d
  k = int(k)
  if _d == 1:
    for i in range(1, k):
      ans += dp[d][0][i]
      ans %= MOD
  else:
    for i in range(1, 10):
      ans += dp[d][0][i]
      ans %= MOD
    
    for i in range(k):
      ans += dp[d][r][i]
      ans %= MOD
  
  r = (r-k)%D

e = 0
for i in K:
  e += int(i)
  e %= D

if e % D == 0:
  ans += 1
  ans %= MOD

print(ans)

### FIXED CODE ###

K = input()
K_int = int(K)
digit = len(K)
D = int(input())
MOD = 10**9 + 7

# dp[d][r][i] : (d+1)桁目の数がiで、それまでの桁の数の和をDで割ったときの余りがrとなる組合せ
dp = [[[0]*10 for r in range(D)] for d in range(digit)]

for i in range(10):
  dp[0][i%D][i] += 1

for d in range(1, digit):
  for r in range(D):
    s = sum(dp[d-1][r])
    for i in range(10):
      dp[d][(r+i)%D][i] += s
      dp[d][(r+i)%D][i] %= MOD

ans = 0
r = 0
for _d, k in enumerate(K, 1):
  d = digit - _d
  k = int(k)
  if _d == 1:
    for i in range(1, k):
      ans += dp[d][0][i]
      ans %= MOD
  else:
    for i in range(1, 10):
      ans += dp[d][0][i]
      ans %= MOD
    
    for i in range(k):
      ans += dp[d][r][i]
      ans %= MOD
  
  r = (r-k)%D

e = 0
for i in K:
  e += int(i)
  e %= D

if e % D == 0:
  ans += 1
  ans %= MOD

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

m,n = list(map(int, input().split()))
MOD=10**9+7
if abs(m-n) > 1:
    print(0)
    exit()

def fact(x):
    ans=1
    for i in range(2, x+1):
        ans*=i%MOD
    return ans

if m>n:
    n,m = m,n
    
f = fact(m)
if m==n:
    print(f * f * 2 % MOD)
else:
    print(f * f * n % MOD)

### FIXED CODE ###

m,n = list(map(int, input().split()))
MOD=10**9+7
if abs(m-n) > 1:
    print(0)
    exit()

def fact(x):
    ans=1
    for i in range(2, x+1):
        ans=ans%MOD*i
    return ans

if m>n:
    n,m = m,n
    
f = fact(m)
if m==n:
    print(f * f * 2 % MOD)
else:
    print(f * f * n % MOD)
### BUGGY CODE ###

N, K = map(int, input().split())
X = list(map(int, input().split()))
right, left = [], []
	
for i in range(N):
	if X[i] >= 0:
		right.append(X[i])
	else:
		left.insert(0, -X[i])
		
right.append(0)
left.append(0)
ans = float("inf")
		
for i in range(K + 1):
	if len(right) < K - i + 1 or len(left) < i + 1: continue
	tmp = min(2 * left[i - 1] + right[(K - i) - 1], left[i - 1] + 2 * right[(K - i) - 1])
	ans = min(ans, tmp)
	
print(ans)

### FIXED CODE ###

N, K = map(int, input().split())
X = list(map(int, input().split()))
ans = float("inf")

for i in range(0, N - K + 1):
	ans = min(ans, min(abs(X[i]) + abs(X[i] - X[i + K - 1]), abs(X[i + K - 1]) + abs(X[i] - X[i + K - 1])))
	
print(ans)
### BUGGY CODE ###

from math import sqrt
from itertools import product
import numpy as np
import sys

n = int(input())
p = []
def factorization(arg):
    while arg % 2 == 0:
        p.append(2)
        arg //= 2
    for i in range(3, int(sqrt(arg)) + 1, 2):
        while arg % i == 0:
            p.append(i)
            arg //= i
    if arg > 1:
        p.append(arg)
if n == 1:
    print(1)
else:
    factorization(n)
    q = np.array(p)
    r = q - 1
    min = sys.maxsize
    for bit in product(range(2), repeat=len(p)):
        c = r * bit
        a = np.prod(c + 1)
        b = np.prod(q - c)
        if len(str(a)) >= len(str(b)):
            if min > len(str(a)):
                min = len(str(a))
        else:
            if min > len(str(b)):
                min = len(str(b))
    print(min)

### FIXED CODE ###

from math import sqrt
from itertools import product
import sys

n = int(input())
p = []
def factorization(arg):
    while arg % 2 == 0:
        p.append(2)
        arg //= 2
    for i in range(3, int(sqrt(arg)) + 1, 2):
        while arg % i == 0:
            p.append(i)
            arg //= i
    if arg > 1:
        p.append(arg)
if n == 1:
    print(1)
else:
    factorization(n)
    min = sys.maxsize
    for bit in range(2 ** len(p)):
        a = 1
        b = 1
        for i in range(len(p)):
            if ((bit >> i) & 1):
                a *= p[i]
            else:
                b *= p[i]
        if min > len(str(a)) if len(str(a)) >= len(str(b)) else len(str(b)):
            min = len(str(a)) if len(str(a)) >= len(str(b)) else len(str(b))
    print(min)
### BUGGY CODE ###

n,m = map(int,input().split())
money = sorted([list(map(int,input().split())) for _ in range(n)], key = lambda x: x[1], reverse = True)

dic = {}
ans = 0
for s in money:
    if s[0] <= m:
        if s[0] not in dic:
            dic[s[0]] = s[1]
            ans += s[1]
        else:
            for i in range(1,m-s[0]+1):
                if s[0]+i not in dic:
                    dic[s[0]+i] = s[1]
                    ans += s[1]
                    break
    if len(dic) == m:
        break
print(ans)

### FIXED CODE ###

import heapq
from collections import defaultdict
n,m = map(int,input().split())
dct = defaultdict(list)

for i in range(n):
    a,b = map(int,input().split())
    dct[a].append(-b)

h = []
ans = 0

for i in range(1,m+1):
    if dct[i]:
        for item in dct[i]:
            heapq.heappush(h, item)
    if h:
        ans += heapq.heappop(h)
print(-ans)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
INF = float("inf")


def solve(N: int, K: int, x: "List[int]", y: "List[int]"):
    sx = sorted(x)
    sy = sorted(y)

    m = INF
    for i, x1 in enumerate(sx):
        for j, y1 in enumerate(sy):
            # 始点を固定
            for x2 in sx[i:]:
                for y2 in sy[j:]:
                    # 終点を固定
                    counter = 0
                    for xx, yy in zip(x, y):
                        if (x1 <= xx <= x2) and (y1 <= yy <= y2):
                            counter += 1
                    if counter >= K:
                        area = abs((y2-y1)*(x2-x1))
                        if area < m:
                            m = area
    print(m)
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    x = [int()] * (N)  # type: "List[int]"
    y = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        x[i] = int(next(tokens))
        y[i] = int(next(tokens))
    solve(N, K, x, y)


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
INF = float("inf")


def solve(N: int, K: int, x: "List[int]", y: "List[int]"):
    sx = sorted(x)
    sy = sorted(y)
    acc = [[0]*N for _ in range(N)]

    for i, x1 in enumerate(sx):
        for j, y1 in enumerate(sy):
            acc[i][j] = sum([True for xx, yy in zip(x, y)
                             if xx <= x1 and yy <= y1])

    m = INF

    for i, x1 in enumerate(sx[:-K+1]):
        for j, y1 in enumerate(sy[:-K+1]):
            # 始点を固定
            for x2 in sx[i+1:]:
                for y2 in sy[j+1:]:
                    # 終点を固定
                    counter = 0
                    for xx, yy in zip(x, y):
                        if (x1 <= xx <= x2) and (y1 <= yy <= y2):
                            counter += 1
                    if counter >= K:
                        flag = True
                        area = abs((y2-y1)*(x2-x1))
                        if area < m:
                            m = area
                        break   # これ以上yをあげたところで面積は増える一方なので抜ける
    print(m)
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    x = [int()] * (N)  # type: "List[int]"
    y = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        x[i] = int(next(tokens))
        y[i] = int(next(tokens))
    solve(N, K, x, y)


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



import numpy as np

n=int(input())
for i in range(10**9):
    if(i*i>n):
        print((i-1)**2)

### FIXED CODE ###



import numpy as np

n=int(input())
for i in range(10**9):
    if(i*i>n):
        print((i-1)**2)
        exit(0)
### BUGGY CODE ###

N,M = map(int,input().split())
A = list(map(int,input().split()))
for i in range(M):
    B,C = map(int,input().split())
    A += [C] * B
A.sort()
A.reverse()
ans = 0
for i in range(N):
    ans += A[i]
print(ans)

### FIXED CODE ###

N,M = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
A.reverse()
counter = 0
ans = 0
B = []
for i in range(M):
    BN,CN = map(int,input().split())
    B.append([CN,BN])
B.sort()
for i in A:
    for j in range(len(B)):
        if B[-1][0] > i:
            if counter <= N - B[-1][1]:
                ans += B[-1][0] * B[-1][1]
                counter += B[-1][1]
                B.pop(-1)
            else:
                ans += B[-1][0] * (N - counter)
                counter = N
        else:
            break
    if counter == N:
        break
    else:
        counter += 1
        ans += i
print(ans)
### BUGGY CODE ###

N = int(input())
X = list(map(int,input().split()))
for i in range(1,N+1):
    tmp1 = X[0:i-1]
    tmp2 = X[i:]
    tmp3 = tmp1+tmp2
    tmp3.sort()
    print(tmp3[N//2-1])

### FIXED CODE ###

N = int(input())
X = list(map(int,input().split()))
a = sorted(X)
b = a[N//2]
c = a[(N//2)-1]
for i in X:
    print(b if i<b else c)
### BUGGY CODE ###

from collections import Counter

mod = 1000000007


def inverse(a):
    return pow(a, mod - 2, mod)


def usearch(x, a):
    lft = 0
    rgt = len(a) + 1
    while rgt - lft > 1:
        mid = (rgt + lft) // 2
        if a[mid] <= x:
            lft = mid
        else:
            rgt = mid
    return lft

memo = [
    [0, 1, 1],
    [1,10,9],
    [2,11,9],
    [3,4,3],
    [4,13,9],
    [5,14,9],
    [6,5,3],
    [7,16,9],
    [8,17,9],
    [9,2,1],
]


def main():
    m = int(input())
    dc = [[int(i) for i in input().split()] for _ in range(m)]
    s = []
    ans = 0
    for i in range(m):
        d = dc[i][0]
        c = dc[i][1]
        ans += c // memo[d][2] * memo[d][1]
        if d == 9:
            ans -= 2
            s.append([d, 1])
        else:
            s.append([d, (c % memo[d][2])])
    if not s:
        print(ans)
        return

    t = s[0][0]
    s[0][1] -= 1
    for i in range(len(s)):
        while s[i][1]:
            s[i][1] -= 1
            ans += 1
            t += s[i][0]
            if t > 9:
                ans += 1
                t = t % 10 + t // 10

    print(ans)

main()


### FIXED CODE ###

from collections import Counter

mod = 1000000007


def inverse(a):
    return pow(a, mod - 2, mod)


def usearch(x, a):
    lft = 0
    rgt = len(a) + 1
    while rgt - lft > 1:
        mid = (rgt + lft) // 2
        if a[mid] <= x:
            lft = mid
        else:
            rgt = mid
    return lft

def main():
    m = int(input())
    ans = 0
    a = 0
    for i in range(m):
        d, c = map(int, input().split())
        ans += c
        a += d * c
    print(ans + (a - 1) // 9 - 1)

main()
### BUGGY CODE ###

from collections import Counter
n = int(input())
lis = list(map(int,input().split()))
if n % 2 == 0:key = 1
else:key = 2
for i in range(n//2):
    if lis.count(i*2+key) != 2:
        print("0")
        exit()
if n % 2 == 1:
    if lis.count(0) != 1:
        print("0")
        exit()
print(2 ** (n//2))

### FIXED CODE ###

import math
n = int(input())
lis = list(map(int,input().split()))
li = [0 for _ in range(math.ceil(n / 2))]

for i in range(n):
  li[math.floor(lis[i] / 2)] += 1
for i in range(len(li)):
  if n % 2 == 1 and i == 0:
    if li[i] != 1:
      print("0")
      exit()
  else:
    if li[i] != 2:
      print("0")
      exit()
cou = 1
for i in range(math.floor(n/2)):
  cou *= 2
  cou %= (10 ** 9 + 7)
print(cou)
### BUGGY CODE ###

N=int(input())
A=[]
I=[]
for n in range(N):
    a=int(input())
    A.append(a)
I.append(1)
def t(I):
    while 2 not in I:
        a=A[I[-1]-1]
        if a in I:
            return print(-1)
        I.append(a)
    return print(len(I)-1)
t(I)


### FIXED CODE ###

N=int(input())
A=[int(input()) for n in range(N)]
def t(N,A):
    i=1
    for n in range(1,N+1):
        a=A[i-1]
        if a==2:
            return print(n)
        i=a
    return print(-1)
t(N,A)
### BUGGY CODE ###

n = int(input())
ans = 1
mod = 10**9+7
for i in range(1,n+1):
    ans *= i
    #ans %= mod

print(ans%mod)

### FIXED CODE ###

n = int(input())
ans = 1
mod = 10**9+7
for i in range(1,n+1):
    ans *= i
    ans %= mod

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

class Combination:
    """
    SIZEが10^6程度以下の二項係数を何回も呼び出したいときに使う
    使い方:
    comb = Combination(SIZE, MOD)
    comb(10, 3) => 120
    """

    def __init__(self, N, MOD=10 ** 9 + 7):
        self.MOD = MOD
        self.fact, self.inv = self._make_factorial_list(N)

    def __call__(self, n, k):
        if k < 0 or k > n:
            return 0
        res = self.fact[n] * self.inv[k] % self.MOD
        res = res * self.inv[n - k] % self.MOD
        return res

    def _make_factorial_list(self, N):
        fact = [1] * (N + 1)
        inv = [1] * (N + 1)
        MOD = self.MOD
        for i in range(1, N + 1):
            fact[i] = (fact[i - 1] * i) % MOD
        inv[N] = pow(fact[N], MOD - 2, MOD)
        for i in range(N, 0, -1):
            inv[i - 1] = (inv[i] * i) % MOD
        return fact, inv


K = int(input())
S = input()
N = len(S)

mod = 10 ** 9 + 7
comb = Combination(3 * 10 ** 6, mod)
pow25 = [1] * (K + 1)
pow26 = [1] * (K + 1)
for i in range(K):
    pow25[i + 1] = pow25[i] * 25 % mod
    pow26[i + 1] = pow26[i] * 26 % mod


ans = 0
for i in range(K + 1):
    cnt = 1
    L = pow25[i] * comb(i + N - 1, i) % mod
    R = pow26[K-i]
    ans += L * R % mod
    ans %= mod

print(ans)

### FIXED CODE ###

class Combination:
    """
    SIZEが10^6程度以下の二項係数を何回も呼び出したいときに使う
    使い方:
    comb = Combination(SIZE, MOD)
    comb(10, 3) => 120
    """

    def __init__(self, N, MOD=10 ** 9 + 7):
        self.MOD = MOD
        self.fact, self.inv = self._make_factorial_list(N)

    def __call__(self, n, k):
        if k < 0 or k > n:
            return 0
        res = self.fact[n] * self.inv[k] % self.MOD
        res = res * self.inv[n - k] % self.MOD
        return res

    def _make_factorial_list(self, N):
        fact = [1] * (N + 1)
        inv = [1] * (N + 1)
        MOD = self.MOD
        for i in range(1, N + 1):
            fact[i] = (fact[i - 1] * i) % MOD
        inv[N] = pow(fact[N], MOD - 2, MOD)
        for i in range(N, 0, -1):
            inv[i - 1] = (inv[i] * i) % MOD
        return fact, inv


mod = 10 ** 9 + 7
comb = Combination(2 * 10 ** 6 + 10, mod)

K = int(input())
S = input()
N = len(S)

ans = 0
for i in range(K + 1):
    res = K - i
    right = pow(26, res, mod)
    pos = comb(N - 1 + i, i)
    cnt = pow(25, i, mod)
    tmp = right * pos % mod * cnt % mod
    ans = (ans + tmp) % mod
print(ans)
### BUGGY CODE ###

n,k=map(int,input().split())
l=list(map(int,input().split()))
dp=[0 for t in range(n)]
if k+1>=n:
  print(abs(l[-1]-l[0]))
  exit()
for i in range(n)[1:]:
  dp[i]=min([dp[i-d]+abs(l[i]-l[i-d]) for d in range(min(i,k)+1)[1:]])
print(dp[-1])

### FIXED CODE ###

n,k=map(int,input().split())
dp=[10**10]*n
h=list(map(int,input().split()))
dp[0]=0
for i in range(1,n):
    dp[i]=min(dp[i-j]+abs(h[i-j]-h[i]) for j in range(1,1+min(k,i)))

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

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

ans = 1
for i in range(n) :
  ans *= a[i]
    
if ans > 10**18 :
    ans = -1
    
print(ans)

### FIXED CODE ###

import sys

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

if 0 in a :
  print(0)
  sys.exit()

ans = 1
for i in range(n) :
  ans *= a[i]
  if ans > 10**18 :
    ans = -1
    break
    
print(ans)
### BUGGY CODE ###

X,Y,Z,K = map(int, input().split())


A = sorted(list(map(int, input().split())))[:K]
B = sorted(list(map(int, input().split())))[:K]
C = sorted(list(map(int, input().split())))[:K]
D = []
E2 = []
F = []

# A + Bの全列挙 からのソート 

for i in A : 
    for j in B : 
        D.append(i+j)
        
E = sorted(D, reverse = True)[:K]

####

for i in E : 
    for j in C : 
        F.append(i+j)
        
G = sorted(F, reverse = True)[:K]

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

### FIXED CODE ###

X,Y,Z,K = map(int, input().split())

A = sorted(list(map(int, input().split()))[:K])
B = sorted(list(map(int, input().split()))[:K])
C = sorted(list(map(int, input().split()))[:K])

ab = sorted(list(a+b for a in A for b in B), reverse = True)[:K]
abc = sorted(list(ab+c for ab in ab for c in C), reverse = True)[:K]

for i in abc : 
    print(i)
### BUGGY CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))
imos = [0]*(N+1)

# 全体でO(NlogN) ≒ 10^6
for k in range(K): # 下のifによってO(logN)で抑えられる.
    if min(A) == N:
        break

    imos = [0]*(N+1)
    for i,a in enumerate(A): # O(N)
        imos[max(0, i-a)] += 1
        imos[min(N, i + a + 1)] -= 1
        
    A = [imos[0]]
    for i in range(1,len(imos)-1): # O(N)
        A.append(A[i - 1] + imos[i])
        
print(*A, sep=" ")

### FIXED CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))
imos = [0]*(N+1)

# 全体でO(NlogN) ≒ 10^6
for k in range(K): # 下のifによってO(logN)で抑えられる.
    if min(A) == N:
        break

    imos = [0]*(N+1)
    for i,a in enumerate(A): # O(N)
        imos[max(0, i-a)] += 1
        imos[min(N, i + a + 1)] -= 1
        
    A = [imos[0]]
    for i in range(1,len(imos)-1): # O(N)
        A.append(A[i - 1] + imos[i])
        
print(*A, sep=" ")
### BUGGY CODE ###

S=list(input())
N=len(S)
mod=[0 for i in range(2019)]
s=0
for i in range(N-1,-1,-1): 
  s+=int(S[i])*(10**(N-1-i))
  mod2=s%2019
  mod[mod2]+=1
ans=0
for i in range(2019):
  k=mod[i]
  if i==0:
    if k>=2:
      ans+=k*(k-1)//2+k
    else:
      ans+=k
  else:
    if k>=2:
      ans+=k*(k-1)//2
print(ans) 

### FIXED CODE ###

import numpy as np
S=input()
N=len(S)
mod=[0 for i in range(2019)]
mod2=0
ten=1
for i in range(N-1,-1,-1): 
  s=int(S[i])*ten
  mod2+=np.mod(s,2019)
  mod2=np.mod(mod2,2019)
  mod[mod2]+=1
  ten=(ten*10)%2019
ans=0
for i in range(2019):
  k=mod[i]
  if i==0:
    if k>=2:
      ans+=k*(k-1)//2+k
    else:
      ans+=k
  else:
    if k>=2:
      ans+=k*(k-1)//2
print(ans)
### BUGGY CODE ###

n = int(input())
s = ""
for _ in range(n):
    s += input()+" "
ls = s.split()
counter = 0
res = []
counter = ls.count(max(ls,key=ls.count))
for x in set(ls):
    if ls.count(x) == counter:
        res.append(x)
r = sorted(res)
print("\n".join(r))

### FIXED CODE ###

from collections import Counter
n = int(input())
ls = []
for _ in range(n):
    ls.append(input())
res = []
counter = Counter(ls).most_common()
for x in counter:
    if x[1] == counter[0][1]:
        res.append(x[0])
print("\n".join(sorted(res)))
### BUGGY CODE ###

N = int(input())
S = input()
dir_change = [0] * N
for i in range(N):
	for j in range(N):
		if i < j and S[j] == "E":
			dir_change[i] += 1
		if i > j and S[j] == "W":
			dir_change[i] += 1
print(min(dir_change))

### FIXED CODE ###

N = int(input())
S = input()

left = 0
right = S[1:].count('E')
result = left + right

for i in range(1, N):
	if S[i - 1] == "W":
		left += 1
	if S[i] == "E":
		right -= 1
	result = min(result, left + right)
print(result)
### BUGGY CODE ###

n=int(input())
s=input()
ans=10**9
for i in range(n):
    b=0
    b+=s[:i].count("W")
    b+=s[i+1:].count("E")
    ans=min(b,ans)
print(ans)

### FIXED CODE ###

n=int(input())
s=input()
e=s.count("E")
w=0
ans=e+w
for si in s:
    if si=="E":
        e-=1
    else:
        w+=1
    ans=min(ans,w+e)
print(ans)
### BUGGY CODE ###

import collections

def int_cards(cards, operations):
    col_cards = collections.deque(sorted(cards))
    operations.sort(reverse=True)
    for c, b in operations:
        for _ in range(b):
            if col_cards[0] > c:
                break
            col_cards.popleft()
            col_cards.append(c)
            
    print(sum(col_cards))
    
N, M = map(int, input().split())
A = list(map(int,input().split()))
operations = []
for i in range(M):
    B, C = map(int, input().split())
    operations.append([C, B])
    
int_cards(A, operations)

### FIXED CODE ###

import collections

def int_cards(N, cards, operations):
    col_cards = collections.deque(sorted(cards), N)
    operations.sort(reverse=True)
    for c, b in operations:
        for _ in range(b):
            if col_cards[0] >= c:
                break
            col_cards.popleft()
            col_cards.append(c)
            
    print(sum(col_cards))
    
N, M = map(int, input().split())
A = list(map(int,input().split()))
operations = []
for i in range(M):
    B, C = map(int, input().split())
    operations.append([C, B])
    
int_cards(N, A, operations)