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

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

MAX = pow(10, 4) * N
costs = [MAX for _ in range(N)]
costs[0] = 0

for h_i in range(N - 1):
    next_step = h_i + 1
    back_max = min(next_step, K)
    for back_index in range(back_max):
        costs[next_step] = min(abs(h[next_step] - h[next_step - back_index -1]) + costs[next_step - back_index -1 ], costs[next_step])


print(costs[N - 1])


### FIXED CODE ###

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

MAX = pow(10, 4) * N
costs = [MAX for _ in range(N)]
costs[0] = 0

for h_i in range(N - 1):
    next_step = h_i + 1
    back_max = min(next_step, K)
    for back_index in range(back_max):
        costs[next_step] = min(abs(h[next_step] - h[next_step - back_index -1]) + costs[next_step - back_index -1 ], costs[next_step])


print(costs[N - 1])
### BUGGY CODE ###

import sys
import numpy as np
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix

input = sys.stdin.readline
int1 = lambda x: int(x) - 1

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

if M == 0:
    print(-1)
    exit()

UV = np.array([tuple(map(int1, input().split())) for _ in range(M)]) * 3
frm = UV[:, 0].repeat(3) + np.tile(np.arange(3), M)
to = UV[:, 1].repeat(3) + np.tile((np.arange(3) + 1) % 3, M)

S, T = map(int1, input().split())
matr = csr_matrix((np.ones(3 * M, dtype=int), (frm, to)), shape=(3 * N, 3 * N))
way = dijkstra(matr, indices=3 * S).astype(int)

res = way[3 * T]
print(res // 3 if res >= 0 else -1)


### FIXED CODE ###

import sys
from collections import deque

input = sys.stdin.buffer.readline
int1 = lambda x: int(x) - 1

N, M = map(int, input().split())
G = [[] for _ in range(3 * N)]
for _ in range(M):
    u, v = map(int1, input().split())
    G[u * 3].append(v * 3 + 1)
    G[u * 3 + 1].append(v * 3 + 2)
    G[u * 3 + 2].append(v * 3)

S, T = map(int1, input().split())
S *= 3
T *= 3

# bfs
d = deque([S])
distance = [0] * (3 * N)
while d:
    v = d.popleft()
    dist_v = distance[v]
    if v == T:
        print(dist_v // 3)
        exit()
    for x in G[v]:
        if not distance[x]:
            d.append(x)
            distance[x] = dist_v + 1
print(-1)
### BUGGY CODE ###

S = input()
ans = 0
if int(S) < 2019:
  print(ans)
else:
  for i in range(len(S)-3):
    for j in range(3, len(S)-i+1):
      T = S[i:i+j]
      N = int(T)
      if N % 2019 == 0:
        ans += 1
  print(ans)

### FIXED CODE ###

s = input()
a = 0
mods = [0]*2019
mods[a] += 1
r = 1
for i in s[::-1]:
  a = (a+int(i)*r)%2019
  r = r*10%2019
  mods[a] += 1
ans = 0
for i in mods:
  ans += i*(i-1)//2
print(ans)
### BUGGY CODE ###

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

res = "YES"
lt = []
for i in range(n):
    if a[i] in lt:
        res = "NO"
        break
    else:
        lt.append(a[i])
print(res)

### FIXED CODE ###

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

b = set(a)

if len(b) == len(a):
    print("YES")
else:
    print("NO")
### BUGGY CODE ###

k, s = list(map(int, input().split()))
ans = 0
for x in range(k+1):
    for y in range(x,k+1):
        for z in range(y,k+1):
            if x+y+z == s:
                if x != y != z :
                    ans += 6
                elif x == y != z or x != y == z:
                    ans += 3
                elif x == y == z:
                    ans += 1
print(ans)

### FIXED CODE ###

k, s = list(map(int, input().split()))
ans = 0
for x in range(k+1):
    for y in range(k+1):
            if 0 <= s-x-y <= k: 
                ans += 1
print(ans)
### BUGGY CODE ###

from collections import deque
n = int(input())
a = list(map(int, input().split()))
b = sorted(set(a), reverse=True)
c = deque([])
for i in b:
    if a.count(i) >= 4 and c == deque([]):
        print(i*i)
        exit(0)
    elif a.count(i) >= 2:
        c.append(i)
        if len(c)==2:
            print(c[0]*c[1])
            exit(0)
print(0)


### FIXED CODE ###

from collections import Counter, deque
n = int(input())
a = list(map(int, input().split()))
b = Counter(a)
c = deque([])
for k in b.keys():
    if b[k]>=4:
        c.append(k)
        c.append(k)
    elif b[k]>=2:
        c.append(k)
c = sorted(c, reverse = True)
print(c[0]*c[1] if c else 0)
### BUGGY CODE ###

# coding: utf-8

N , M = map(int,input().split())
list = [ list(map(int,input().split())) for i in range(M) ]
ans = "IMPOSSIBLE"
for i in range(M):
    if list[i][0] == 1:
        for j in range(M):
            if list[i][1] == list[j][0]:
                if list[j][1] == N:
                    ans = "POSSIBLE"
print(ans)

### FIXED CODE ###

# coding: utf-8
from sys import stdin
input = stdin.readline

N , M = map(int,input().split())
start_input = set()
goal_input = set()

for _ in range(M):
    x , y = map(int,input().split())
    if x == 1:
        start_input.add(y)
    elif y == N:
        goal_input.add(x)
    
if start_input & goal_input:
    print("POSSIBLE")
else :
    print("IMPOSSIBLE")
### BUGGY CODE ###

n=int(input())
a=[int(input()) for _ in range(n)]
for i in range(n):
    print(max(a[:i]+a[i+1:]))

### FIXED CODE ###

n=int(input())
a=[int(input()) for _ in range(n)]
a_copy=a[:]
first=max(a)
a_copy.remove(first)
second=max(a_copy)

for i in range(n):
    if a[i]!=first:
        print(first)
    else:
        print(second)
### BUGGY CODE ###

N = int(input())

a = [int(N) for N in input().split()]
b = len(a)

#count = 0

#for i in range(1,N+1):
#    for k in range(0,b):
#        if(i == a[k]):
#            count += 1
#    print(count)
#    count = 0

for i in range(1,N+1):
    print(a.count(i))

### FIXED CODE ###

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

def solve():
    N = int(raw_input())
    D = [int(raw_input()) for i in range(N)]
    if sum(D) % 2 > 0:
        print '-1'
        return
    Di = sorted([(di, i) for i, di in enumerate(D)], key = lambda x : x[0], reverse = True)
    d_to_i = {dd:i for dd, i in Di}
    # child = [[] for i in range(N)]
    ans = []
    n_child = [1] * N
    d_child = [0] * N
    for valD, node in Di:
        valD_par = valD - N + 2 * n_child[node]
        if valD_par in d_to_i.keys():
            node_par = d_to_i[valD_par]
            # child[node].append(node_par) ##
            # child[node_par].append(node)
            ans.append((node_par + 1, node + 1))
            n_child[node_par] += n_child[node]
            d_child[node_par] += n_child[node] + d_child[node]
            if n_child[node_par] == N:
                break
        else:
            print '-1'
            return
    # check if Di satisfied or not
    d_min, i_min = Di[-1]
    if d_child[i_min] != d_min:
        print '-1'
        return
    # for i in range(N):
    #     for j in child[i]:
    #         print str(i + 1) + ' ' + str(j + 1)
    for i,j in ans:
        print str(i) + ' ' + str(j)

if __name__ == '__main__':
    solve()


### FIXED CODE ###

n = int(input())
d = [int(input()) for i in range(n)]

if sum(d)%2 > 0:
    print(-1)
    exit()

d = sorted([(dd, i) for i, dd in enumerate(d)], reverse = True)
d_to_i = {dd:i for dd, i in d}
n_child = [1]*n
d_child = [0]*n
ans = []
for dd, i in d:
    d_i = dd+2*n_child[i]-n
    if d_i in d_to_i.keys():
        i_next = d_to_i[d_i]
        ans.append((i+1, i_next+1))
        n_child[i_next] += n_child[i]
        d_child[i_next] += d_child[i] + n_child[i]
        if n_child[i_next] == n:
            break
    else:
        print(-1)
        exit()

d_min, i_min = d[-1]
if d_min == d_child[i_min]:
    for a in ans:
        print(*a)
else:
     print(-1)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
ans = A[0]
for i in range(1, N):
  ans *= A[i]
if ans > 10**18:
  print(-1)
else:
  print(ans)

### FIXED CODE ###

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

def solve(N, A):
  ans = A[0]
  exist_zero = False
  if A[-1] == 0:
    exist_zero = True

  if exist_zero:
    print(0)
    return

  for i in range(1, N):
    ans *= A[i]
    if ans > 10**18 and not exist_zero:
      print(-1)
      return

  print(ans)

solve(N, A)
### BUGGY CODE ###

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

M = 10**6 + 1
cnt = [0]*M

for a in A:
    for i in range(M)[a::a]:
        cnt[i] += 1

ans = 0
for a in A:
    if cnt[a] == 1:
        ans += 1

print(ans)

### FIXED CODE ###

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

M = 10**6 + 1
cnt = [0]*M

for a in A:
    if cnt[a] != 0:
        cnt[a] += 1
        continue
    for i in range(M)[a::a]:
        cnt[i] += 1

ans = 0
for a in A:
    if cnt[a] == 1:
        ans += 1

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

import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    s = input()
    L = list(range(2019, 2 * (10 ** 5), 2019))
    n = len(s)

    cnt = 0
    for i in range(n):
        for j in range(i, n):
            for k in L:
                S = "".join(s[i:j + 1])
                if str(k) == S:
                    cnt += 1
    print(cnt)


if __name__ == '__main__':
    resolve()


### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 2019


def resolve():
    s = input()
    n = len(s)
    s = s[::-1]

    ruiseki = 0
    cnt = [0] * mod
    ans = 0
    for i in range(n):
        cnt[ruiseki] += 1
        ruiseki += int(s[i]) * pow(10, i, mod)
        ruiseki %= mod
        ans += cnt[ruiseki]

    print(ans)


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

R,G,B,N = map(int, input().split())
count = 0
for r in range(N//R+1):
    if R*r> N:
         break
    for g in range(N//G+1):
        if R*r + G*g > N:
            break
        if (N - (R*r + G*g)) %B == 0 :
            count += 1
print(count)

### FIXED CODE ###

R,G,B,N = map(int, input().split())
count = 0

for r in range(N//R+1):
    if R*r> N:
         break
    for g in range(N//G+1):
        aa = N-R*r- G*g
        if aa < 0:
            break
        if aa %B == 0 :
            count += 1
print(count)
### BUGGY CODE ###

n = int(input())
a = [int(input()) for _ in range(n)]
for i in range(n):
  l = a.copy()
  l[i] = 0
  print(max(l))




  

### FIXED CODE ###

n = int(input())
a = [int(input()) for _ in range(n)]
s = max(a)
if a.count(s) >= 2:
  for i in range(n):  
    print(s)
else:
  for i in range(n):
    if a[i] == s:
      l = a.copy()
      l.sort()
      print(l[-2])
    else:
      print(s)
### BUGGY CODE ###

n,x,y=map(int,input().split())
ans=[0]*n
for i in range(1,n+1):
    for j in range(i+1,n+1):
        a1=abs(i-j)
        a2=abs(x-i)+1+abs(y-j)
        a3=abs(y-i)+1+abs(x-j)    
        d=min(a1,a2,a3)
        ans[d]+=1
for i in range(1,n):
    print(ans[i])

### FIXED CODE ###

n,x,y=map(int,input().split())
ans=[0]*n #個数を数えるのにバケットを用意する
for i in range(1,n+1): #i<jなるすべての頂点の組について最短距離を求める
 for j in range(i+1,n+1):
   dist1=j-i
   dist2=abs(x-i)+abs(y-j)+1
   dist3=abs(y-i)+abs(x-j)+1
   d=min(dist1,dist2,dist3) #最短距離は上式により求められる
   ans[d]+=1 #最短距離がdとなる組の個数を1増やす
for i in range(1,n):
 print(ans[i])
### BUGGY CODE ###

from collections import deque

def main():
    A,B,N=map(int,input().split())
    d=deque()
    
    for x in range(N+1):
        #tmp=((A*x)//B)-A*(x//B)
        tmp1=((A*x)//B)
        tmp2=A*(x//B)
        tmp=tmp1-tmp2
        
        if x>=1:
            if d[-1]>tmp:
                break
        
        d.append(tmp)
        
    print(d[-1])
    exit()
    
if __name__=="__main__":
    main()

### FIXED CODE ###

from math import floor

def main():
    A,B,N=map(int,input().split())
    
    ans1=min(N,B-1)
    ans2=floor(A*ans1/B)-A*floor(ans1/B)
    print(ans2)
    
if __name__=="__main__":
    main()
### BUGGY CODE ###

import itertools

n, m, r = map(int, input().split())
R = list(map(int, input().split()))

DP = [[10**10 for _ in range(n+1)] for _ in range(n+1)]
for i in range(1,n+1):
    DP[i][i] = 0

for _ in range(m):
    a, b, c = map(int, input().split())
    DP[a][b] = c
    DP[b][a] = c

for k in range(1,n+1):
    for i in range(1,n+1):
        for j in range(1,n+1):
            DP[i][j] = min(DP[i][j], DP[i][k]+DP[k][j])

ans = 10**10
for permutation in itertools.permutations(R, r):
    dist = 0
    for i in range(r-1):
        dist += DP[permutation[i]][permutation[i+1]]
    ans = min(ans, dist)

print(ans)

### FIXED CODE ###

import itertools

n, m, r = map(int, input().split())
R = list(map(int, input().split()))

DP = [[10**10 for _ in range(n+1)] for _ in range(n+1)]
for i in range(1,n+1):
    DP[i][i] = 0

for _ in range(m):
    a, b, c = map(int, input().split())
    DP[a][b] = c
    DP[b][a] = c

for k in range(1,n+1):
    for i in range(1,n+1):
        for j in range(1,n+1):
            DP[i][j] = min(DP[i][j], DP[i][k]+DP[k][j])

ans = 10**10
for permutation in itertools.permutations(R, r):
    dist = 0
    for i in range(r-1):
        dist += DP[permutation[i]][permutation[i+1]]
    ans = min(ans, dist)

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

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

import sys
import heapq

def pickup_job(tmp_jobs):
    tmp_jobs = sorted(tmp_jobs,key=lambda x:x[1],reverse=True)
    worked_job=heapq.heappop(tmp_jobs)
    return worked_job

def main():
    N,M = map(int, input().split())
    job_datas = [list(map(int,input().split())) for _ in range(N)]
    job_datas=sorted(job_datas)
    day_counter=M
    tmp_jobs=[]
    ans=0
    while day_counter >= 0:
        for job_data in job_datas:
            if (M-day_counter)>=job_data[0]:
                tmp_jobs.append(job_data)
            else:
                break
        if len(tmp_jobs)!=0:
            worked_job=pickup_job(tmp_jobs)
            ans+=worked_job[1]
            job_datas.remove(worked_job)
            tmp_jobs=[]
        day_counter-=1
    print(ans)

if __name__ == "__main__":
    main()

### FIXED CODE ###

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

import heapq

def main2():
    n,m=map(int,input().split())
    jobs_list=[list(map(int,input().split())) for _ in range(n)]
    #breakするタイミングを作るため、Mより大きい値の仕事を作成
    banpei_list=[[i,0] for i in range(1,m+2)]
    #リストの統合
    jobs_list.extend(banpei_list)
    jobs_list=sorted(jobs_list)
    ans=0
    index=0
    que=[]
    while 1:
        day,pay=jobs_list[index]
        #dayがMを超えていればbreak
        if day>m:
            break
        #同じdayのデータが次にもあれば-1倍してheapにpush
        if day==jobs_list[index+1][0]: 
            heapq.heappush(que,-pay)
        #仕事の報酬の最大値を答えに加える
        #前の日のデータからも報酬が良い仕事は選べるようにqueにデータは貯めておく
        else:
            heapq.heappush(que,-pay)
            ans-=heapq.heappop(que)
        index+=1
    print(ans)

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

import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

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

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

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

def calc(i,j):
    ret = -float('inf')
    if j==0:
        return 0
    if (N-i+1)//2 < j:
        return ret
    else:
        if i <= N-1:
            ret = max(ret,A[i]+calc(i+2,j-1))
        if i+1 <= N-1:
            ret = max(ret,A[i+1]+calc(i+3,j-1))
        return ret


N = I()
A = LI()


if N%2 == 0:
    print(calc(0,N//2))
else:
    a1 = calc(0,N//2)
    n = 0
    for i in range(2,N,2):
        n += A[i]
    print(max(a1,n))

### FIXED CODE ###

import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

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

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

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

N = I()
A = LI()


if N%2 == 0:
    d = defaultdict(lambda:defaultdict(lambda:-float('inf')))
    d[0][1] = A[0]
    d[1][1] = max(A[0],A[1])
    for i in range(2,N):
        if i%2 == 0:
            for j in [i//2,i//2+1]:
                d[i][j] = max(d[i-2][j-1]+A[i],d[i-1][j])
        else:
            for j in [(i+1)//2]:
                d[i][j] = max(d[i-2][j-1]+A[i],d[i-1][j])
    print(d[N-1][N//2])
else:
    d = defaultdict(lambda:defaultdict(lambda:-float('inf')))
    d[0][1] = A[0]
    d[1][1] = max(A[0],A[1])
    for i in range(2,N):
        if i%2 == 0:
            for j in [i//2,i//2+1]:
                d[i][j] = max(d[i-2][j-1]+A[i],d[i-1][j])
        else:
            for j in [i//2,i//2+1]:
                d[i][j] = max(d[i-2][j-1]+A[i],d[i-1][j])
    a1 = d[N-1][N//2]
    n = 0
    for i in range(2,N,2):
        n += A[i]
    print(max(n,a1))
### BUGGY CODE ###

a, b, x = map(int, input().split())
count = 0

for i in range(a, b+1):
    if i % x == 0:
        count += 1

print(count)


### FIXED CODE ###

a, b, x = map(int, input().split())

nb = b // x + 1
na = (a-1) // x + 1 if a > 0 else 0

print(nb - na)
### BUGGY CODE ###

K , S = map(int, input().split())
ans = 0
for i in range(K + 1):
	for j in range(K + 1):
		for k in range(K + 1):
			if i + j + k == S:
				ans += 1
print(ans)

### FIXED CODE ###

K , S = map(int, input().split())
ans = 0
for i in range(K + 1):
	for j in range(K + 1):
			if 0 <= S - i - j <= K:
				ans += 1
print(ans)
### BUGGY CODE ###

# N = int(input())
# A = [0] * N
# B = []
# for n in range(N):
#     A[n] = int(input())
#     bn = []
#     for i in range(A[n]):
#         x, y = map(int, input().split())
#         bn.append((x-1, y))
#     B.append(bn)

# ans = 0
# # bit & (1 << n) で n 番目の 0,1
# for bit in range(1 << N):
#     ok = [False] * N
#     for n in range(N):
#         if ((bit >> n) & 1) == 1:
#             if all([((bit >> B[n][i][0]) & 1) == B[n][i][1] for i in range(A[n])]):
#                 ok[n] = True
#         else:
#             if all([((bit >> B[n][i][0]) & 1) != B[n][i][1] for i in range(A[n])]):
#                 ok[n] = True
#     if all(ok):
#         ans = max(ans, sum(list(map(int, format(bit, "b")))))

# print(ans)

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

MOD = 10 ** 9 + 7

ans = 0
for i in range(60):
    n = sum([(a >> i) & 1 for a in A])
    ans = (ans + n * (N - n) * (2 ** i)) % MOD

print(ans)

### FIXED CODE ###

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

MOD = 10 ** 9 + 7

ans = 0
for i in range(60):
    n = sum([(a >> i) & 1 for a in A])
    ans = (ans + n * (N - n) * (2 ** i)) % MOD

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

def main():
    N, Q = map(int, input().split())
    C = list(map(int, input().split()))
    E = []

    D = {C[i]: -1 for i in range(N)}
    for i in range(N):
        if D[C[i]] == -1:
            D[C[i]] = i
        else:
            E.append((D[C[i]], i, -1))
            D[C[i]] = i

    for i in range(Q):
        l, r = map(int, input().split())
        E.append((l - 1, r - 1, i))

    def f(tup):
        return tup[0]
    E.sort(key=f, reverse=True)

    ANS = [0] * Q
    y_list = [0] * (N + 1)
    for e in E:
        if e[2] == -1:
            y_list[e[1]] = 1
        else:
            ans = y_list[0:e[1] + 1].count(1)
            ANS[e[2]] = e[1] - e[0] + 1 - ans

    for i in range(Q):
        print(ANS[i])

if __name__ == '__main__':
    main()

### FIXED CODE ###

from collections import defaultdict
import sys
def read():
    return sys.stdin.readline().rstrip()
def main():
    N, Q = map(int, read().split())
    C = list(map(int, read().split()))
    E = defaultdict(list)

    D = [-1] * (N + 1)
    for i in range(N):
        D_i = D[C[i]]
        if D_i != -1:
            E[D_i].append((D_i, i))
        D[C[i]] = i

    F = defaultdict(list)
    for i in range(Q):
        l, r = map(int, input().split())
        F[l-1].append((r - 1, i))



    # Binary Indexed Tree (Fenwick Tree)
    class BIT:
        def __init__(self, n):
            self.n = n
            self.data = [0] * (n + 1)
            self.el = [0] * (n + 1)

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

        def add(self, i, x):
            # assert i > 0
            self.el[i] += x
            while i <= self.n:
                self.data[i] += x
                i += i & -i

        def get(self, i, j=None):
            if j is None:
                return self.el[i]
            return self.sum(j) - self.sum(i)

    ANS = [0] * Q
    d = BIT(N)
    for x in range(N - 1, -1, -1):
        for e in E[x]:
            d.add(e[1], 1)
        for f in F[x]:
            ANS[f[1]] = f[0] - x + 1 - d.sum(f[0])

    for i in range(Q):
        print(ANS[i])

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

n = int(input())
lst = [int(i) for i in input().split()]
dic = {}
for i in range(n):
  key = lst[i]
  if key not in dic:
    dic[key] = 0
  dic[key] += 1
#print(dic)
m = int(input())
for _ in range(m):
  sum = 0
  lst_s = list(map(int, input().split()))
  number = dic.get(lst_s[0])
  if number is not None:
    if lst_s[1] in dic:
      dic[lst_s[1]] += number
    else:
      dic[lst_s[1]] = number
    dic.pop(lst_s[0])
  for key, value in dic.items():
    sum += key * value
  print(sum)

### FIXED CODE ###

n = int(input())
lst = [int(i) for i in input().split()]
dic = {}
for i in range(n):
  key = lst[i]
  if key not in dic:
    dic[key] = 0
  dic[key] += 1
#print(dic)
sum = 0
for key, value in dic.items():
  sum += key * value

m = int(input())
for _ in range(m):
  lst_s = list(map(int, input().split()))
  number = dic.get(lst_s[0])
  if number is not None:
    if lst_s[1] in dic:
      dic[lst_s[1]] += number
    else:
      dic[lst_s[1]] = number
    sum += lst_s[1] * number
    sum -= lst_s[0] * number
    dic.pop(lst_s[0])
  print(sum)
### BUGGY CODE ###

n,m = map(int,input().split())
l = [-1]*(m)
r = [-1]*m
for i in range(m):
    a,b = map(int,input().split())
    l[i]=a
    r[i]=b

#print(r)
#print(l)
count = 0
k = 0
for i in range(1,n+1):
    k=0
    for j in range(m):
        if (l[j] <= i) and (i <= r[j]):
            k += 1

            
    #print(k)
    if k== m:
        count +=1


print(count)

### FIXED CODE ###

n,m = map(int,input().split())
l = [-1]*(m)
r = [-1]*m
for i in range(m):
    a,b = map(int,input().split())
    l[i]=a
    r[i]=b
right = n
left = 0 
#print(r)
#print(l)
count = 0
k = 0
for i in range(m):
    right = min(r[i],right)
    left = max(l[i],left)

ans = max(0,right -left +1)
print(ans)
### BUGGY CODE ###

N,K=map(int,input().split())
MOD=998244353
S=[0]*(N+1)
for _ in range(K):
    L,R=map(int,input().split())
    for i in range(L,R+1):
        S[i]=1
dp=[0]*(N+1)
dp[1]=1
for i in range(2,N+1):
    for j in range(i):
        if S[j]==1:
            dp[i]+=dp[i-j]
            dp[i]%=MOD
print(dp[N]%MOD)

### FIXED CODE ###

N,K=map(int,input().split())
MOD=998244353
S=[]
for _ in range(K):
    L,R=map(int,input().split())
    S.append((L,R))
S.sort()
dp=[0]*(N+1)
dp[1]=1
ans=[0]*(K+1)
for i in range(2,N+1):
    for j in range(K):
        L,R=S[j][0],S[j][1]
        if L>=i:
            break
        l=max(0,i-R)
        r=min(i-1,i-L)
        ans[j]+=dp[r]-dp[l-1]
    dp[i]+=sum(ans)
    dp[i]%=MOD
print(dp[N]%MOD)
### BUGGY CODE ###

#C
from collections import Counter
import itertools

N = int(input())
S = [None] * N
for i in range(N):
    Si = input()
    S[i] = Si

counter = Counter(S)
ret = [letter for letter,count in counter.most_common() if count == counter.most_common()[0][1]]

for i in (sorted(ret)):
    print(i)

### FIXED CODE ###

#C
N = int(input())
memo = {}
max_word = 1
for i in range(N):
    Si = input()
    try:
        memo[Si] += 1
        max_word = max(max_word, memo[Si])
    except:
        memo[Si] = 1
        
keys = [k for k, v in memo.items() if v == max_word]
keys.sort()
for item in keys:
  print(item)