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

N = int(input())

counts = [0 for i in range(N+1)]

for i in range(1,150):
    for j in range(1,150):
        for k in range(1,150):
            now = i**2 + j**2 + k**2 + i*j + j*k + k*i
            try:
                counts[now] += 1
            except:
                pass
for i in range(1,N+1):
    print(counts[i])

### FIXED CODE ###

N = int(input())

counts = [0 for i in range(N+1)]

for i in range(1,150):
    for j in range(1,150):
        for k in range(1,150):
            now = i**2 + j**2 + k**2 + i*j + j*k + k*i
            try:
                counts[now] += 1
            except:
                pass
for i in range(1,N+1):
    print(counts[i])
### BUGGY CODE ###

import sys
from fractions import gcd
import bisect

stdin = sys.stdin

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



n, m = na()
a = na()

for i in range(m):
    b, c = na()
    for j in range(b):
        a.append(c)

a.sort(reverse=True)
print(sum(a[:n]))

### FIXED CODE ###

import sys
import math
import numpy as np
import bisect
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)]

n, m = na()
a = na()
bc = []

for _ in range(m):
    bci = na()
    bc.append(bci)

bc.sort(key=lambda x:x[1], reverse=True)
#print(bc)

bi, ci = bc[0][0], bc[0][1]
i = 0
for _ in range(n):
    if bi != 0:
        bi -= 1
        a.append(ci)
    else:
        i += 1
        if i > (m - 1):
            break
        else:
            bi, ci = bc[i][0], bc[i][1]
            bi -= 1
            a.append(ci)

a.sort(reverse=True)
print(sum(a[:n]))
### BUGGY CODE ###

from fractions import gcd
N=int(input())
A=list(map(int,input().split(' ')))
L = 1
def lcm(x,y):
    return x//gcd(x,y)*y
for a in A:
    L = lcm(L,a)
print(sum([L//a for a in A])%(10**9+7))

### FIXED CODE ###

from fractions import gcd
n=int(input())
a=list(map(int,input().split()))
lcm = a[0]
for i in range(1,n):
  lcm = lcm*a[i] // gcd(lcm,a[i])
mod=pow(10,9)+7
lcm%=mod
ans=0
for x in a:
  ans+=pow(x,mod-2,mod)
  ans%=mod
print(ans*lcm%mod)
### BUGGY CODE ###

n=int(input())
arr=list(map(int,input().split()))
count=0
for i in range(len(arr)):
	for j in range(i+1,len(arr)):
		count+=(arr[i]*arr[j])
print(count%((10**9)+7))

### FIXED CODE ###

n=int(input())
arr=list(map(int,input().split()))
count=0
pre=[arr[0]]
for i in range(1,len(arr)):
	pre.append((pre[-1]+arr[i]))
ans=0
for i in range(len(arr)-1,0,-1):
	ans+=(pre[i-1]*arr[i])
print(ans%((10**9)+(7)))
### BUGGY CODE ###

import numpy as np
N=int(input())
PP=np.array(input().split(),dtype=np.int64)
#print(PP[3])
count=1
if (N==1):
    print(count)
else:
    for i in range(1,N):
 #       print(i)
        P1=PP[0:i+1]
        #P1=np.array(P0)
        MIN=np.min(P1)

        TAR=P1[i]
        if (MIN==TAR):
            count += 1

    print(count)


### FIXED CODE ###

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

n = int(readline())
p = list(map(int, readline().split()))
temp = p[0]
lis = p[1:]
ans = 1

for i in lis:
    if (i > temp):
        pass
    else:
        temp = i
        ans += 1

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

h,n = map(int,input().split())

a_li = [0]*n
b_li = [0]*n

for i in range(n):
    a_li[i],b_li[i] = map(int,input().split())
#配るdp
dp =[10**10]*(h+1)
dp[0]=0
for i in range(h):
    for j in range(n):
        next_index=min(h,i+a_li[j])
        dp[next_index]=min(dp[next_index],dp[i]+b_li[j])
print(dp[-1])


### FIXED CODE ###

h,n = map(int,input().split())

ab_input = [list(map(int,input().split())) for i in range(n)]
max_d = max(a for a,b in ab_input)
#配るdp
dp =[0]*(h+max_d)
for i in range(1,h+max_d):
    dp[i]=min(dp[i-a]+b for a,b in ab_input)
print(dp[h])
### BUGGY CODE ###

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

N = 100000
like_number = [3]
prime_number = [2]
for i in range(3, N, 2):
   flag = 0
#   for j in range(3, int(i**0.5)+1, 2):
   for j in prime_number:
      if j > int(i**0.5)+1:
         break
      elif i%j == 0:
         flag = 1
         break
   if flag == 0:
      prime_number.append(i)
      if ((i+1)/2)%2 == 1:
         if (i+1)/2 in prime_number:
            like_number.append(i)
         

for i in range(Q):
   count = 0
   for j in like_number:
      if lr[i][1] >= j:
         if lr[i][0] <= j:
            count = count + 1
      else:
         break
   print(count)


### FIXED CODE ###

def main():
    Q = int(input())
    L = [0 for _ in range(Q)]
    R = [0 for _ in range(Q)]
    for i in range(Q):
        L[i], R[i] = map(int, input().split())

    N = 100000
    sosu = [1 for _ in range(N)]
    sosu[0] = 0
    for i in range(1,int(N**0.5)):
        k = i+1
        if sosu[i] == 1:
            j = k + k
            while j <= N:
                sosu[j-1] = 0
                j = j+k
    like = [0 for _ in range(N)]
    for i in range(2, N, 2):
        if sosu[i]==1 and sosu[(i+2)//2-1]==1:
            like[i] = 1
    like_wa = [0 for _ in range(N+1)]
    for i in range(N):
        like_wa[i+1] = like_wa[i] + like[i]

    for i in range(Q):
        print(like_wa[R[i]] - like_wa[L[i]-1])

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

from collections import defaultdict


def dfs(graph, start):
    visited, stack = set(), [start]
    while stack:
        vertex = stack.pop()
        if vertex not in visited:
            visited.add(vertex)
            stack.extend(graph[vertex] - visited)
    return visited


if __name__ == "__main__":
    n, m, k = map(int, input().split())
    AB = [map(int, input().split()) for _ in range(m)]
    CD = [map(int, input().split()) for _ in range(k)]

    graph_f = defaultdict(set)
    graph_b = defaultdict(set)

    for a, b in AB:
        graph_f[a - 1].add(b - 1)
        graph_f[b - 1].add(a - 1)

    for c, d in CD:
        graph_b[c - 1].add(d - 1)
        graph_b[d - 1].add(c - 1)

    visited = set()
    conns = []
    for i in range(n):
        if i not in visited:
            conn = dfs(graph_f, i)
            visited |= conn
            conns.append(conn)

    res = []
    for i in range(n):
        suggestion_cnt = 0
        current_conn = list(filter(lambda x: i in x, conns))[0]
        res.append(len(current_conn - graph_f[i] - graph_b[i]) - 1)

    print(' '.join(map(str, res)))


### FIXED CODE ###

class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def size(self, x):
        return -self.parents[self.find(x)]


if __name__ == "__main__":
    n, m, k = map(int, input().split())

    u = UnionFind(n)
    f_cnt = [0] * n
    b_cnt = [0] * n

    for _ in range(m):
        a, b = map(int, input().split())
        u.union(a - 1, b - 1)
        f_cnt[a - 1] += 1
        f_cnt[b - 1] += 1

    for _ in range(k):
        c, d = map(int, input().split())
        if u.same(c - 1, d - 1):
            b_cnt[c - 1] += 1
            b_cnt[d - 1] += 1

    print(*[(u.size(i) - f_cnt[i] - b_cnt[i] - 1) for i in range(n)])
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import sys
N,K,C=map(int, sys.stdin.readline().split())
S=sys.stdin.readline().strip()

#左から
L=[]
over=-1
L_cnt=0
for i,x in enumerate(S):
    if x=="o" and over<i:
        L.append(i)
        L_cnt+=1
        if L_cnt==K: break
        over=i+C

#右から
R=[]
over=-1
R_cnt=0
for i,x in enumerate(S[::-1]):
    if x=="o" and over<i:
        R.append(N-1-i)
        R_cnt+=1
        if R_cnt==K: break
        over=i+C


for x in L:
    if x in R:
        print x+1

### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
from bisect import bisect_left, bisect_right
N,K,C=map(int, sys.stdin.readline().split())
S=sys.stdin.readline().strip()

#左から
L=[]
over=-1
L_cnt=0
for i,x in enumerate(S):
    if x=="o" and over<i:
        L.append(i)
        L_cnt+=1
        if L_cnt==K: break
        over=i+C

#右から
R=[]
over=-1
R_cnt=0
for i,x in enumerate(S[::-1]):
    if x=="o" and over<i:
        R.append(N-1-i)
        R_cnt+=1
        if R_cnt==K: break
        over=i+C

L.sort()
R.sort()

for x,y in zip(L,R):
    if x==y:
        print x+1
### BUGGY CODE ###

import bisect
N,M = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
BC = []
for _ in range(M):
  B,C = map(int,input().split())
  BC.append((B,C))
BC.sort(key=lambda x: x[1], reverse=True)
for i in BC:
  b,c = i[0],i[1]
  index = bisect.bisect_left(A,c)
  index = min(index,b)
  if index==0:
    continue
  A = [c for _ in range(index)] + A[index:]
  A.sort()
print(sum(A))

### FIXED CODE ###

import bisect
N,M = map(int,input().split())
A = list(map(int,input().split()))
D = []
for _ in range(M):
  D.append(list(map(int,input().split())))
D.sort(key=lambda x:x[1], reverse=True)
cnt = 0
ans = []
for d in D:
  b,c = d[0],d[1]
  ans += [c for _ in range(b)]
  cnt += b
  if cnt>=N:
    break
ans = ans[:min(cnt,N)] + A
ans.sort(reverse=True)
print(sum(ans[:N]))
### BUGGY CODE ###

import sys
input = sys.stdin.readline

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

end=[[] for i in range(N+2)]

for i in [0]*M:
    l,r,a=map(int,input().split())
    end[r+1].append((l,a))

#Starry Sky tree
seg_el=1<<18#Segment treeの台の要素数

SEG=[0]*(2*seg_el-1)#Segment tree.色々考えると0で初期化してOKそう
ADD=[0]*(2*seg_el-1)#加算用Segment tree,SEG[k]+ADD[k]がkにおける本当の最大値
seg_el_list=[524286, 262142, 131070, 65534, 32766, 16382, 8190, 4094, 2046, 1022, 510, 254, 126, 62, 30, 14, 6, 2, 0]
#seg_el_list=[14, 6, 2, 0]

def update(k):#SEGのkより上のノードを更新（反映）
    while k>=0:
        k=(k-1)//2
        SEG[k]=max(SEG[k*2+1]+ADD[k*2+1],SEG[k*2+2]+ADD[k*2+2])

def to_seg(a):#aが終点となる区間をSegment treeの座標へ変換  
    b=(a&(-a)).bit_length()
    return seg_el_list[b]+a//(1<<(b-1))

def add(a,b,x):#区間(a,b]にxを加算
    #print(a,b,x)
    while b!=0:
        ADD[to_seg(b)]+=x
        update(to_seg(b))
        b-=(b&(-b))

    while a!=0:
        ADD[to_seg(a)]+=-x
        update(to_seg(a))
        a-=(a&(-a))
    
for i in range(N+2):
    for b,k in end[i]:
        add(b,i,k)#点数がもらえる区間から出たときにその分を加算

    SEG[i+seg_el-1]=SEG[0]
    update(i+seg_el-1)

print(SEG[0])


### FIXED CODE ###

import sys
input = sys.stdin.readline

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

end=[[] for i in range(N+2)]

for i in [0]*M:
    l,r,a=map(int,input().split())
    end[r+1].append((l,a))

#Starry Sky tree
seg_el=1<<18#Segment treeの台の要素数

SEG=[0]*(2*seg_el-1)#Segment tree.色々考えると0で初期化してOKそう
ADD=[0]*(2*seg_el-1)#加算用Segment tree,SEG[k]+ADD[k]がkにおける本当の最大値
seg_el_list=[524286, 262142, 131070, 65534, 32766, 16382, 8190, 4094, 2046, 1022, 510, 254, 126, 62, 30, 14, 6, 2, 0]

def update(k):#SEGのkより上のノードを更新（反映）
    while k>=0:
        k=(k-1)//2
        if SEG[k]==max(SEG[k*2+1]+ADD[k*2+1],SEG[k*2+2]+ADD[k*2+2]):
            break
        SEG[k]=max(SEG[k*2+1]+ADD[k*2+1],SEG[k*2+2]+ADD[k*2+2])

def to_seg(a):#aが終点となる区間をSegment treeの座標へ変換  
    b=(a&(-a)).bit_length()
    return seg_el_list[b]+a//(1<<(b-1))

def add(a,b,x):#区間(a,b]にxを加算
    #print(a,b,x)
    while b!=0:
        ADD[to_seg(b)]+=x
        update(to_seg(b))
        b-=(b&(-b))

    while a!=0:
        ADD[to_seg(a)]+=-x
        update(to_seg(a))
        a-=(a&(-a))
    
for i in range(N+2):
    for b,k in end[i]:
        add(b,i,k)#点数がもらえる区間から出たときにその分を加算

    SEG[i+seg_el-1]=SEG[0]
    update(i+seg_el-1)

print(SEG[0])
### BUGGY CODE ###

n,m = map(int,input().split())
dp = [float("inf")]*(1<<n)
dp[0]=0
kagi = []
for i in range(m):
    a,b = map(int,input().split())
    c = list(map(int,input().split()))
    kagi.append([a,b,c])
for j in range(m):
    for i in range(1<<n):
        tmp = i+0
        for k in kagi[j][2]:
            tmp = tmp | 1<<(k-1)
        dp[tmp] = min(dp[tmp],dp[i]+kagi[j][0])
print(dp[(1<<n)-1] if dp[(1<<n)-1] != float("inf") else -1)



### FIXED CODE ###

n,m = map(int,input().split())
dp = [float("inf")]*(1<<n)
dp[0]=0
kagi = []
for i in range(m):
    a,b = map(int,input().split())
    c = list(map(int,input().split()))
    kagi.append([a,b,c])
for j in range(m):
    for i in range(1<<n):
        tmp = i+0
        for k in kagi[j][2]:
            tmp = tmp | 1<<(k-1)
        dp[tmp] = min(dp[tmp],dp[i]+kagi[j][0])
print(dp[(1<<n)-1] if dp[(1<<n)-1] != float("inf") else -1)
### BUGGY CODE ###

# -*- coding: utf-8 -*-

n = int(input())
d = list(map(int,input().split()))
m = int(input())
t = list(map(int,input().split()))

d.sort()
t.sort()

def array_count(arr):
    arr_target = [[]]
    cnt = 1
    for i in range(1,len(arr)):
        if arr[i] == arr[i-1]:
            cnt += 1
        else:
            arr_target.append([arr[i-1],cnt])
            cnt = 1
    arr_target.append([arr[len(arr)-1],cnt])
    del arr_target[0]
    return arr_target

d = array_count(d)
t = array_count(t)

flag = True
for i in range(len(t)):
    temp = -1
    for j in range(len(d)):
        if d[j][0] == t[i][0]:
            temp = j
    if temp == -1:
        flag = False
        break
    if d[temp][1] >= t[i][1]:
        pass
    else:
        flag = False
        break

if flag:
    print("YES")
else:
    print("NO")


### FIXED CODE ###

# -*- coding: utf-8 -*-

n = int(input())
d = list(map(int,input().split()))
m = int(input())
t = list(map(int,input().split()))

def array_count(arr):
    arr_target = [[]]
    cnt = 1
    for i in range(1,len(arr)):
        if arr[i] == arr[i-1]:
            cnt += 1
        else:
            arr_target.append([arr[i-1],cnt])
            cnt = 1
    arr_target.append([arr[len(arr)-1],cnt])
    del arr_target[0]
    return arr_target

d.sort()
t.sort()

d = array_count(d)
t = array_count(t)

for i in range(len(t)):
    t[i][1] = -1 * t[i][1]
    d.append(t[i])

d.sort()

for i in range(1,len(d)):
    if d[i-1][0] == d[i][0]:
        d[i-1][1] = d[i-1][1] + d[i][1]
        d[i][1] = 0

flag = True

for i in range(len(d)):
    if d[i][1] < 0:
        flag = False
        break

if flag:
    print("YES")
else:
    print("NO")
### BUGGY CODE ###

N = int(input())
S1 = input()
S = [(a, p) for p, a in enumerate(S1)]

count = 0
for i in range(N):
    for k in range(i+1,N):
        if S[i][0] != S[k][0]:
            RGB = ['R','G','B']
            RGB.remove(S[i][0])
            RGB.remove(S[k][0])
            count += S1.count(RGB[0],k+1,N)
            if 2*k-i < N:
                if S[2*k-i][0]!= S[i][0] and S[2*k-i][0]!=S[k][0]:
                    count -= 1 
print(count)      

### FIXED CODE ###

N = int(input())
S = list(input())
count = S.count("R")*S.count("B")*S.count("G")
for i in range(N):
    for j in range(i+1,N):
        if 2*j-i < N:
            if S[i]!=S[j] and S[2*j-i]!=S[i] and S[2*j-i]!=S[j]:
                count-=1
print(count)
### BUGGY CODE ###

N = int(input())

for h in range(1, 3501):
    for n in range(1, 3501):
        a = N * h * n
        b = 4 * h * n - N * (h + n)
        if a > 0 and b > 0 and a % b == 0:
            print("{0} {1} {2}".format(h, n, a//b))
            exit()

### FIXED CODE ###

N = int(input())

for h in range((N + 3) // 4, 3501):
    for n in range((N + 3) // 4, 3501):
        a = N * h * n
        b = 4 * h * n - N * (h + n)
        if a > 0 and b > 0 and a % b == 0:
            print("{0} {1} {2}".format(h, n, a//b))
            exit()
### BUGGY CODE ###

def main():
    import numpy as np
    h, w, K = map(int, input().split())
    grid = np.array([list(map(int, list(input())))
                     for _ in [0]*h], dtype=np.int16)
    m = 10**9
    for i in range(2**(h-1)):
        i = (("0"*h)+bin(i)[2:])[-h:]+"2"
        memo = [0]
        ma = memo.append
        [ma(j+1) for j in range(h) if i[j] != i[j+1]]
        ans = len(memo)-1
        ans2 = [0]
        aa = ans2.append
        memo2 = [0]*ans
        j = 0
        flag = False
        while j < w:
            if flag:
                break
            for k in range(ans):
                memo2[k] += np.sum(grid[memo[k]:memo[k+1], j])
                if memo2[k] > K:
                    aa(j)
                    memo2 = [0]*ans
                    if j == ans2[-2]:
                        flag = True
                    break
            else:
                j += 1
        if not flag:
            m = min(m, ans+(len(ans2)-2))
    print(m)


main()

### FIXED CODE ###

def main():
    from itertools import product
    h, w, K = map(int, input().split())
    grid = [list(input()) for _ in [0]*h]
    m = 10**9
    for i in range(2**h):
        i = (("0"*h)+bin(i)[2:])[-h:]+"2"
        memo = [0]
        for j in range(h):
            if i[j] == i[j+1]:
                pass
            else:
                memo.append(j+1)
        ans = len(memo)-1
        ans2 = [0]
        memo2 = [0]*ans
        j = 0
        flag = False
        while j < w:
            if flag:
                break
            for k in range(ans):
                memo2[k] += [grid[l][j]
                             for l in range(memo[k], memo[k+1])].count("1")
                if memo2[k] > K:
                    ans2.append(j)
                    memo2 = [0]*ans
                    if ans2[-1] == ans2[-2]:
                        flag = True
                    break
            else:
                j += 1
        if flag == False:
            m = min(m, ans+(len(ans2)-2))
    print(m)


main()
### BUGGY CODE ###

def fac(m):
  return(math.factorial(m)//(2*math.factorial((m-2))))
import collections
import math
N=int(input())
A=list(map(int, input().split()))
C=collections.Counter(A)
for k in range(N):
  C[A[k]]-=1
  L=list(C)
  cnt=0
  for s in L:
    if C[s]>1:
      cnt+=fac(C[s])
  C[A[k]]+=1
  print(cnt)

### FIXED CODE ###

from math import factorial
from collections import Counter


def combinations_count(n, r):
    if n >= r:
        return factorial(n) // (factorial(n - r) * factorial(r))
    else:
        return 0

c = Counter()
n = int(input())
A = list(map(int, input().split()))
for i in A:
    c[i] += 1
ans = 0
for k, v in c.items():
    ans += combinations_count(v, 2)

for i in A:
    print(ans-c[i]+1)
### BUGGY CODE ###

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

ans=A[0]
for i in range(1,K):
   ans*=A[i]


for i in range(K,N):
    preans=ans
    ans=ans//A[i-K]*A[i]
    if ans>preans:
        print('Yes')
    else:
        print('No')


### FIXED CODE ###

import numpy as np

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

for i in range(K,N):
    if A[i]/A[i-K]>1:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

import sys
import scipy.sparse as sparse
from collections import deque

n = int(input())

color_ls = {i: None for i in range(n)}
_map = sparse.lil_matrix((n, n))
already = set()
for i in range(n - 1):
    u, v, w = [int(i) for i in sys.stdin.readline().split()]
    u -= 1
    v -= 1
    if i == 0:
        root = u
    _map[u, v] = w
    _map[v, u] = w
    already.update({u, v})
color_ls[root] = 0
cur = root
already.clear()
que = deque()
while True:
    candidate = _map[cur].nonzero()[1]
    for cand in candidate:
        if cand in already:
            continue
        already.add(cand)
        que.append(cand)
        if _map[cur, cand] % 2 == 0:
            color_ls[cand] = 0 if color_ls[cur] == 0 else 1
        else:
            color_ls[cand] = 1 if color_ls[cur] == 0 else 0
    if len(que) == 0 or len(already) == n:
        break
    cur = que.popleft()

for i in range(n):
    print(color_ls[i])

### FIXED CODE ###

import sys
from collections import deque

n = int(input())

color_ls = {i: None for i in range(n)}
dict_map = {i : [] for i in range(n)}
already = set()
for i in range(n - 1):
    u, v, w = [int(i) for i in sys.stdin.readline().split()]
    u -= 1
    v -= 1
    if i == 0:
        root = u
    dict_map[u].append([v, w])
    dict_map[v].append([u, w])
    already.update({u, v})
color_ls[root] = 0
cur = root
already.clear()
que = deque()
while True:
    candidate = dict_map[cur]
    for cand, w in candidate:
        if cand in already:
            continue
        already.add(cand)
        que.append(cand)
        if w % 2 == 0:
            color_ls[cand] = 0 if color_ls[cur] == 0 else 1
        else:
            color_ls[cand] = 1 if color_ls[cur] == 0 else 0
    if len(que) == 0 or len(already) == n:
        break
    cur = que.popleft()

for i in range(n):
    print(color_ls[i])
### BUGGY CODE ###


from collections import defaultdict
d=defaultdict(int)
N=int(input())
L=[]
for _ in range(N):
 s=input()
 d[s]+=1
for k, v in d.items():
 if v == max(d.values()):
  L.append(k)
L.sort()
for i in L:
 print(i)

### FIXED CODE ###

n=int(input())
arr=[input() for _ in range(n)]
dic={}
for i in range(n): #各単語の出現回数を数える
 if arr[i] not in dic:
   dic[arr[i]]=1
 else:
   dic[arr[i]]+=1
largest=max(dic.values()) #最大の出現回数を求める
ans=[]
for keys in dic.keys():
 if dic[keys]==largest: #出現回数が最も多い単語を集計する
   ans.append(keys)
ans=sorted(ans) #単語を辞書順に並べ替えて出力する
for words in ans:
 print(words)
### BUGGY CODE ###

import sys
from heapq import heappop, heappush


def dijkstra(links, l):
    dists = []

    F9 = (1 << 9) - 1
    F30 = (1 << 30) - 1
    INF = 10 ** 18

    for s in range(n):

        q = [s]
        fixed = [-1] * n
        upper = [INF] * n
        while q:
            item = heappop(q)

            v = item & F9
            if fixed[v] != -1:
                continue

            count = item >> 39
            used = (item >> 9) & F30
            fixed[v] = count

            for u, c in links[v]:
                if l - used < c:
                    new_item = ((count + 1) << 39) | (c << 9) | u
                else:
                    new_item = (count << 39) | ((used + c) << 9) | u
                if new_item >= upper[u]:
                    continue
                heappush(q, new_item)

        dists.append(fixed)

    return dists


n, m, l = list(map(int, input().split()))
lines = sys.stdin.readlines()

links = [set() for _ in range(n)]

for line in lines[:m]:
    a, b, c = map(int, line.split())
    a -= 1
    b -= 1
    if l < c:
        continue
    links[a].add((b, c))
    links[b].add((a, c))

dists = dijkstra(links, l)
buf = []

for line in lines[m + 1:]:
    s, t = map(int, line.split())
    buf.append(dists[s - 1][t - 1])

print('\n'.join(map(str, buf)))


### FIXED CODE ###

import sys

n, m, l = list(map(int, input().split()))
lines = sys.stdin.readlines()
INF = 10 ** 18

dists = [[INF] * n for _ in range(n)]

for i in range(n):
    dists[i][i] = 0

for line in lines[:m]:
    a, b, c = map(int, line.split())
    a -= 1
    b -= 1
    if c > l:
        continue
    dists[a][b] = c
    dists[b][a] = c

for k in range(n):
    dk = dists[k]
    for i in range(n):
        di = dists[i]
        for j in range(n):
            new_dist = di[k] + dk[j]
            if new_dist > l:
                continue
            if di[j] > new_dist:
                di[j] = new_dist

refuels = [[1 if dist < INF else INF for dist in row] for row in dists]

for k in range(n):
    rk = refuels[k]
    for i in range(n):
        ri = refuels[i]
        for j in range(n):
            new_dist = ri[k] + rk[j]
            if ri[j] > new_dist:
                ri[j] = new_dist

buf = []

for line in lines[m + 1:]:
    s, t = map(int, line.split())
    refuel = refuels[s - 1][t - 1]
    buf.append(-1 if refuel == INF else refuel - 1)

print('\n'.join(map(str, buf)))