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

# -*- coding: utf-8 -*-
import numpy as np
import sys
from collections import deque
from collections import defaultdict
import heapq
import collections
import itertools
import bisect
from itertools import accumulate
import copy


def zz():
    return list(map(int, sys.stdin.readline().split()))


def z():
    return int(sys.stdin.readline())


def S():
    return sys.stdin.readline()


def C(line):
    return [sys.stdin.readline()[:-1] for _ in range(line)]


N = z()
for n in range(1, N + 1):
    ans = 0
    for x in range(1, 45):
        for y in range(x, 45):
            for z in range(y, 45):
                if(x**2+y**2+z**2+x*y+y*z+x*z == n):
                    if(x == y == z):
                        ans += 1
                    elif ((x == y) or (x == z) or (y == z)):
                        ans += 3
                    else:
                        ans += 6
    print(ans)


### FIXED CODE ###

# -*- coding: utf-8 -*-
import numpy as np
import sys
from collections import deque
from collections import defaultdict
import heapq
import collections
import itertools
import bisect
from itertools import accumulate
import copy


def zz():
    return list(map(int, sys.stdin.readline().split()))


def z():
    return int(sys.stdin.readline())


def S():
    return sys.stdin.readline()


def C(line):
    return [sys.stdin.readline()[:-1] for _ in range(line)]


N = z()
ans = [0]*N
for x in range(1, 105):
    for y in range(1, 105):
        for z in range(1, 105):
            if(x**2+y**2+z**2+x*y+y*z+x*z <= N):
                ans[x**2+y**2+z**2+x*y+y*z+x*z - 1] += 1
for i in ans:
    print(i)
### BUGGY CODE ###

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

count = 0
for i in range(2 ** N):
    check = []
    for j in range(N):
        if ((i >> j) & 1):
            check.append(X[j])
    # print(check)
    if len(check) > 0 and (sum(check) / len(check)) == A:
        count += 1

print(count)


### FIXED CODE ###

N,A = map(int,input().split())
ls1 = [0] + list(map(int,input().split()))

dp = [[[0 for k in range(2600)] for j in range(51) ] for i in range(51)]
for i in range(51):
    dp[i][0][0] = 1
for j in range(1,N+1):
    for k in range(1,j+1):
        for s in range(2600):
            if s < ls1[j]:
                dp[j][k][s] = dp[j-1][k][s]
            elif s >= ls1[j]:
                dp[j][k][s] = dp[j-1][k-1][s-ls1[j]] + dp[j-1][k][s]
ans = 0
for k in range(1,N+1):
    ans += dp[N][k][k*A]
print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
"""
Created on Thu Jun  4 22:35:46 2020

@author: naoki
"""

import sys

N = int(input()) # ボタンの個数
a = [int(input()) for i in range(N)] #k番目のボタンに書いてある番号
a = [0] + a #配列の番号合わせ
count = 0 #ボタンを押す回数
light = 1 # 光っているボタンの番号
if 2 not in a: # 2と書かれたボタンがない場合は不可能なので-1を出力
    print(-1)
    sys.exit()
else: # 2と書かれたボタンがある場合
    while light != 2 or count >= N : # 光っているボタンが2になるか、ボタンを押した回数がNを超えてしまったら終了
        count += 1 
        light = a[light]#左から数えたときに光っているボタンの番号の順番にあるボタンに書かれている数字が次に光るボタンの番号である。

if light != 2:
    print(-1)
else:
    print(count)
    

### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Thu Jun  4 22:35:46 2020

@author: naoki
"""

import sys

N = int(input()) # ボタンの個数
a = [int(input()) for i in range(N)] #k番目のボタンに書いてある番号
a = [0] + a #配列の番号合わせ
count = 0 #ボタンを押す回数
light = 1 # 光っているボタンの番号
if 2 not in a: # 2と書かれたボタンがない場合は不可能なので-1を出力
    print(-1)
    sys.exit()
else: # 2と書かれたボタンがある場合
    while light != 2 and count <= N : # 光っているボタンが2になるか、ボタンを押した回数がNを超えてしまったら終了
        count += 1 
        light = a[light]#左から数えたときに光っているボタンの番号の順番にあるボタンに書かれている数字が次に光るボタンの番号である。

if count <= N:        
        print(count)
else:
    print(-1)
### BUGGY CODE ###

N, M = list(map(int, input().split()))
A = list(map(int, input().split()))
cost = [None,2,5,5,4,5,6,3,7,6]

dp = [-1]*(N+20)
dp[0] = 0

min_cost = min([cost[a] for a in A])
max_cost = max([cost[a] for a in A])
r=0

l = 1
while min_cost*l<=N:
    dp_new = [-1]*(N+20)
    for i in range(min_cost*l, min(max_cost*l, N)+1):
        v = [dp[i-cost[a]] + a*10**(l-1) for a in A if dp[i-cost[a]]>=0]
        if v: dp_new[i] = max(v)
    dp = dp_new
    if dp[N]>0 : r=dp[N]
    l+=1

print(r)

### FIXED CODE ###

N, M = list(map(int, input().split()))
A = list(map(int, input().split()))
cost = [None,2,5,5,4,5,6,3,7,6]

Aset = {}
for a in A:
    c = cost[a]
    Aset[c] = max(Aset[c], a) if c in Aset else a
A = sorted([v for k,v in Aset.items()])

dp = [None]*(N+1)
dp[0] = (0,[0]*len(A))

for ia, a in enumerate(A):
    c = cost[a]
    for i in range(c, N+1):
        t = dp[i-c]
        if t and (dp[i]==None or t[0]+1>=dp[i][0]):
            dp[i] = (t[0]+1, t[1].copy())
            dp[i][1][ia] += 1
      	
l=[]
for i in range(len(A)):
    l += [A[len(A)-1-i]]*dp[N][1][len(A)-1-i]

print(*l, sep='')
### BUGGY CODE ###

n=input()

count=0
for j in range(1,int(n)+1):
    X=[]
    str_j=str(j)
    for k in range(len(str_j)):
        X.append(int(str_j[k]))
    if set(X)=={3,5,7}:
        count+=1
        
print(count)

### FIXED CODE ###

n=int(input())


L=[3,5,7]

def dfs(s):
    count=0
    for i in L:
        p=s*10+i
        if p<=n:
            if set([int(j) for j in str(p)])==set(L):
                count+=dfs(p)+1 #条件を満たしているので+1
            else:
                count+=dfs(p)
    return count

print(dfs(0))
### BUGGY CODE ###

#!/usr/bin/env python3
from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right

def main():
    H, W = map(int, input().split())
    A = [input() for _ in range(H)]
    adj = [[] for _ in range(W*H)]
    dx = [1,-1,0,0]
    dy = [0,0,1,-1]
    
    # 黒のマスからbfsする
    queue = deque()
    visit = [-1] * (W*H)

    for i in range(H):
        for j in range(W):
            if A[i][j] == '#':
                queue.append(W*i + j)
                visit[W*i + j] = 0
            for k in range(4):
                y = i + dy[k]
                x = j + dx[k]
                if 0 <= y < H and 0 <= x < W:
                    adj[W*i + j].append(W*y + x)
    
    while queue:
        now = queue.popleft()
        for u in adj[now]:
            if visit[u] < 0:
                queue.append(u)
                visit[u] = visit[now] + 1
    print(max(visit))

if __name__ == "__main__":
    main()


### FIXED CODE ###

#!/usr/bin/env python3
from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right

def main():
    H, W = map(int, input().split())
    A = [input() for _ in range(H)]
    adj = [[] for _ in range(W*H)]
    dx = [1,-1,0,0]
    dy = [0,0,1,-1]
    
    # 黒のマスからbfsする
    queue = deque()
    visit = [-1] * (W*H)

    for i in range(H):
        for j in range(W):
            if A[i][j] == '#':
                queue.append(W*i + j)
                visit[W*i + j] = 0
            for k in range(4):
                y = i + dy[k]
                x = j + dx[k]
                if 0 <= y < H and 0 <= x < W:
                    adj[W*i + j].append(W*y + x)
    
    while queue:
        now = queue.popleft()
        for u in adj[now]:
            if visit[u] < 0:
                queue.append(u)
                visit[u] = visit[now] + 1
    print(max(visit))

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

s = input();
l = len(s)
while ('01' in s) or ('10' in s): 
	s=s.replace('01', '').replace('10', '')
print(l - len(s))

### FIXED CODE ###

s=input();
l=len(s)
zero,one=0,0
for i in s:
	if i=='0': zero+=1
	else: one+=1
print(min(zero, one)*2)
### BUGGY CODE ###

x, y = map(int,input().split())
a = []
a.append(x)
for i in range(x+1,y+1):
    if i % x == 0:
        a.append(i)
        x = i
print(len(a))

### FIXED CODE ###

x, y = map(int,input().split())

a = x
count = 0
while a <= y:
    count += 1
    a = a*2
print(count)
### BUGGY CODE ###

N,M=list(map(int,input().split()))
l=[[] for i in range(N)]
l_c=[0 for i in range(N)]
for i in range(M):
   a,b=list(map(int,input().split()))
   a-=1;b-=1
   l[a].append(b)
   l[b].append(a)
from collections import deque
def search(start):
   que=deque([start])
   after=deque([])
   while que:
      A=que.popleft()
      after.append(A)
      l_c[A]=1
      for i in l[A]:
         if i not in que and i not in after:
            que.append(i)
   return len(after)
ans=0
for i in range(N):
   if l_c[i] ==0:
      ans=max(ans,search(i))
print(ans)

### FIXED CODE ###

N,M=list(map(int,input().split()))
l=[[] for i in range(N)]
l_c=[0 for i in range(N)]
for i in range(M):
   a,b=list(map(int,input().split()))
   a-=1;b-=1
   l[a].append(b)
   l[b].append(a)
from collections import deque
def search(start):
   cnt=1
   que=deque([start])
   l_c[start]=1
   while que:
      A=que.popleft()
      for i in l[A]:
         if l_c[i]==0:
            cnt+=1
            l_c[i]=1
            que.append(i)
   return cnt
ans=0
for i in range(N):
   if l_c[i] ==0:
      ans=max(ans,search(i))
print(ans)
### BUGGY CODE ###

n, k = map(int,input().split())
lrl = []
for _ in range(k):
    lrl.append(list(map(int,input().split())))

N = 2 * n
# N: 処理する区間の長さ

data0 = [0]*(N+1)
data1 = [0]*(N+1)

mod = 998244353
# 区間[l, r)に x を加算
def _add(data, k, x):
    while k <= N:
        x %= 998244353
        data[k] += x
        data[k] %= 998244353
        k += k & -k
def add(l, r, x):
    _add(data0, l, -x*(l-1))
    _add(data0, r, x*(r-1))
    _add(data1, l, x)
    _add(data1, r, -x)

# 区間[l, r)の和を求める
def _get(data, k):
    s = 0
    while k:
        s += data[k]
        s %= 998244353
        k -= k & -k
    return s
def query(l, r):
    return _get(data1, r-1) * (r-1) + _get(data0, r-1) - _get(data1, l-1) * (l-1) - _get(data0, l-1)

add(1, 2, 1)
for i in range(n):
    now = query(i+1, i+2) 
    for l, r in lrl:
        add(l+i+1, r+i+2, now % 998244353)

print(query(n, n+1) % 998244353)


### FIXED CODE ###

n, k = map(int,input().split())
lrl = []
for _ in range(k):
    lrl.append(list(map(int,input().split())))

N = 2 * n
# N: 処理する区間の長さ

data0 = [0]*(N+1)
data1 = [0]*(N+1)

mod = 998244353
# 区間[l, r)に x を加算
def _add(data, k, x):
    while k <= N:
        x %= mod
        data[k] += x
        data[k] %= mod
        k += k & -k
def add(l, r, x):
    _add(data0, l, -x*(l-1)%mod)
    _add(data0, r, x*(r-1)%mod)
    _add(data1, l, x)
    _add(data1, r, -x)

# 区間[l, r)の和を求める
def _get(data, k):
    s = 0
    while k:
        s += data[k]
        s %= mod
        k -= k & -k
    return s
def query(l, r):
    return _get(data1, r-1) * (r-1) + _get(data0, r-1) - _get(data1, l-1) * (l-1) - _get(data0, l-1)

add(1, 2, 1)
for i in range(n):
    now = query(i+1, i+2) 
    for l, r in lrl:
        add(l+i+1, r+i+2, now % mod)

print(query(n, n+1) % mod)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

n,m=map(int,input().split())
a=[int(input()) for i in range(m)]
F = [1]*(n+3)
for i in range(2,n+1):
    F[i]=(F[i-1]%(10**9+7)+F[i-2]%(10**9+7))%(10**9+7)


if n==1:
    print(1)
elif n==2:
    if m==1:
        print(1)
    elif m==0:
        print(2)
else:
    for i in range(m):
        if a[i]+1 in a or a[i]-1 in a:
            print(0)
            exit()
    if m==0:
        print(F[n])
    else:
        x=F[min(a)-1]
        a.append(n+1)
        for i in range(1,len(a)):
            x=(x*F[a[i]-a[i-1]-2])%(10**9+7)
        print(x)


### FIXED CODE ###

n,m=map(int,input().split())
a=set(int(input()) for _ in range(m))
dp=[0]*(n+1)
dp[0]=1
for i in range(1,n+1):
    dp[i]=(dp[i-1]+dp[i-2])%(10**9+7)
    if i in a:
        dp[i]=0
print(dp[n])
### BUGGY CODE ###

N, K = map(int, input().split())
H = [int(input()) for i in range(N)]

H.sort()
ans = float("inf")
for i in range(len(H)-K+1):
	ans = min(ans, max(H[i:i+K])- min(H[i:i+K]))

print(ans)

### FIXED CODE ###

N, K = map(int, input().split())
H = [int(input()) for i in range(N)]

H.sort()
ans = float("inf")
for i in range(N-K+1):
	ans = min(ans, H[i+K-1]-H[i])

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

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

for i in range(K):
    B=[0]*(N+1)
    for j in range(N):
        l=max(0,j-A[j])
        r=min(N-1,j+A[j])
        B[l]+=1
        B[r+1]-=1
    for j in range(1,N):
        B[j]=B[j]+B[j-1]
    ok=True
    for j in range(N):
        if B[j]!=N:
            ok=False
            break
    if ok:
        print(*B[:N])
        exit()
        
    A=B.copy()
print(*A[:N])

### FIXED CODE ###

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

for i in range(K):
    B=[0]*(N+1)
    for j in range(N):
        l=max(0,j-A[j])
        r=min(N-1,j+A[j])
        B[l]+=1
        B[r+1]-=1
    for j in range(1,N):
        B[j]=B[j]+B[j-1]
    ok=True
    for j in range(N):
        if B[j]!=N:
            ok=False
            break
    if ok:
        print(*B[:N])
        exit()
        
    A=B.copy()
print(*A[:N])
### BUGGY CODE ###

from sys import maxsize
from itertools import product

n, k = map(int, input().split())
p = list(map(lambda x: int(x)-1, input().split()))
c = list(map(int, input().split()))

used = [0] * n
ss = []
for i in range(n):
    if used[i]:
        continue
    now = i
    s = []
    while not used[now]:
        used[now] = 1
        s.append(c[now])
        now = p[now]
    ss.append(s)

res = -maxsize
for s in ss:
    s_len = len(s)
    cumsum = [0]
    # 2周分の累積和
    for i in range(2*s_len):
        cumsum.append(cumsum[-1] + s[i%s_len])

    max_sum = [-maxsize] * s_len
    for i, j in product(range(s_len), repeat=2):
        max_sum[j] = max(max_sum[j], cumsum[i+j] - cumsum[i])

    for i in range(s_len):
        if i > k:
            continue
        v = (k - i) // s_len
        if i == 0 and v == 0:
            continue
        if cumsum[s_len] > 0:
            res = max(res, max_sum[i] + cumsum[s_len] * v)
        elif i > 0:
            res = max(res, max_sum[i])
print(res)


### FIXED CODE ###

from sys import maxsize
from itertools import product

n, k = map(int, input().split())
p = list(map(lambda x: int(x)-1, input().split()))
c = list(map(int, input().split()))

used = [0] * n
ss = []
for i in range(n):
    if used[i]:
        continue
    now = i
    s = []
    while not used[now]:
        used[now] = 1
        s.append(c[now])
        now = p[now]
    ss.append(s)

res = -maxsize
for s in ss:
    s_len = len(s)
    cumsum = [0]
    # 2周分の累積和
    for i in range(2*s_len):
        cumsum.append(cumsum[-1] + s[i%s_len])

    max_sum = [-maxsize] * s_len
    for i, j in product(range(s_len), repeat=2):
        max_sum[j] = max(max_sum[j], cumsum[i+j] - cumsum[i])

    for i in range(s_len):
        if i > k:
            continue
        v = (k - i) // s_len
        if i == 0 and v == 0:
            continue
        if cumsum[s_len] > 0:
            res = max(res, max_sum[i] + cumsum[s_len] * v)
        elif i > 0:
            res = max(res, max_sum[i])
print(res)
### BUGGY CODE ###

# ANSHUL GAUTAM
# IIIT-D

'''

'''

def solve(grid):
	H,W = len(grid),len(grid[0])
	q = []
	dist = [0]*H
	for i in range(H):
		dist[i] = []
	for i in range(H):
		for j in range(W):
			if(grid[i][j] == '#'):
				q.append([i,j])
				grid[i][j] = 0
	maxx = 0
	while(q):
		qq = []
		for i,j in q:
			for r,c in [[i+1,j],[i-1,j],[i,j+1],[i,j-1]]:
				if(0 <= r < H and 0 <= c < W and grid[r][c] == '.'):
					grid[r][c] = grid[i][j] + 1
					maxx = max(maxx,grid[r][c])
					qq.append([r,c])
		q = qq
	return maxx

H,W = map(int, raw_input().split())
grid = []
for h in range(H):
	s = list(raw_input())
	grid.append(s)
ans = solve(grid)
print(ans)



### FIXED CODE ###

# ANSHUL GAUTAM
# IIIT-D

'''

'''

def solve(grid):
	H,W = len(grid),len(grid[0])
	q = []
	dist = [0]*H
	for i in range(H):
		dist[i] = []
	for i in range(H):
		for j in range(W):
			if(grid[i][j] == '#'):
				q.append([i,j])
				grid[i][j] = 0
	maxx = 0
	while(q):
		qq = []
		for i,j in q:
			for r,c in [[i+1,j],[i-1,j],[i,j+1],[i,j-1]]:
				if(0 <= r < H and 0 <= c < W and grid[r][c] == '.'):
					grid[r][c] = grid[i][j] + 1
					maxx = max(maxx,grid[r][c])
					qq.append([r,c])
		q = qq
	return maxx

H,W = map(int, raw_input().split())
grid = []
for h in range(H):
	s = list(raw_input())
	grid.append(s)
ans = solve(grid)
print(ans)
### BUGGY CODE ###

import sys
n = int(input())
S = input()

i = S.find('#')
if i < 0:
    print(0)
    sys.exit()

a = 0
Min = 200000
for j in range(i, n):
    if S[j:j+1] == '#':
        b = S[j:n].count('.')
        Min = min(Min, a+b)
        a += 1
        
print(Min)

### FIXED CODE ###

n = int(input())
S = input()

c = S.count('.')
Min = c


for j in range(n):
    if S[j] == '#':
        c += 1
    else:
        c -= 1
    Min = min(Min, c)
        
print(Min)
### BUGGY CODE ###

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

b = []
for i, a_i in enumerate(a):
    if i % 2 == 0:
        b = b + [a_i]
    else:
        b = [a_i] + b
        
if n % 2 == 1:
    b = b[::-1]
        
for b_i in b[:-1]:
    print ("%d "%(b_i), end="")
print("%d"%b[-1])

### FIXED CODE ###

n = int(input())
A = list(map(int, input().split(" ")))
      
if n % 2 == 0:
    print(*(A[1::2][::-1]+A[0::2]))
else:
    print(*(A[0::2][::-1]+A[1::2]))
### BUGGY CODE ###

sList, tList = input(), input()

dp = [[""] * (len(tList) + 1) for _ in range(2)]
index = 0

# 横方向で回す
for i, s in enumerate(sList, start=1):
    index = i % 2
    for j, t in enumerate(tList, start=1):
        dp[index][j] = max([dp[index][j - 1], dp[index-1][j],
                            dp[index-1][j-1] + s if s == t else ""], key=len)


print(dp[index][-1])


### FIXED CODE ###


sList, tList = input(), input()

dp = [[0] * (len(tList) + 1) for _ in range(len(sList)+1)]


# 横方向で回す
for i, s in enumerate(sList, start=1):
    for j, t in enumerate(tList, start=1):
        dp[i][j] = max([dp[i][j - 1], dp[i-1][j],
                        dp[i-1][j-1] + 1 if s == t else 0])
m = dp[i][j]
ans = ""
# traceback
cnt = 0
while i + j != 0:
    if dp[i - 1][j - 1] == m - 1 and tList[j-1] == sList[i-1]:
        ans = tList[j-1] + ans
        i -= 1
        j -= 1
        m -= 1
    else:
        if dp[i - 1][j] == m:
            i -= 1
        elif dp[i][j-1] == m:
            j -= 1
    cnt += 1
print(ans)
### BUGGY CODE ###

N,M=map(int,input().split())
A=[int(x) for x in input().split()]
for i in range(M):
  A.sort()
  A[-1]=A[-1]/2
for i in range(N):
  A[i]=int(A[i])
print(sum(A))

### FIXED CODE ###

import heapq
N,M =map(int,input().split())
A=[-int(x) for x in input().split()]#大きい順で扱う為にマイナスを付ける

heapq.heapify(A)#Aを優先度付キューへ変換

for i in range(M):
  saitakane = heapq.heappop(A)#最高値を取り出す
  heapq.heappush(A,-(-saitakane//2))#切り捨ての為に正の数にしてから半分にして戻す（追加）
print(-sum(A))
### BUGGY CODE ###

import copy
n = int(input())
al = []
for _ in range(n):
    al.append(int(input()))

alcopy = copy.deepcopy(al)
alcopy.sort()
for a in al:
    if a != max(al):
        print(max(al))
    else:
        print(alcopy[-2])

### FIXED CODE ###

import copy
n = int(input())
lst =[]
for i in range(n):
    x = int(input())
    lst.append(x)

lst2 = copy.deepcopy(lst)
lst2.sort()
max = max(lst2)
for x in lst:
    if x == max:
        print(lst2[-2])
    else:
        print(max)
### BUGGY CODE ###

from functools import reduce
import sys


def input():
    return sys.stdin.readline()[:-1]

def gcd(a, b):
    if a < b:
        a, b = b, a
    if b == 0:
        return a
    return gcd(b, a%b)

def lcm(a, b):
	return a * b // gcd(a, b)

def main():
	mod = 10**9 + 7
	N = int(input())
	A = tuple(map(int, input().split()))

	ans = reduce(lcm, A) 
	
	B = (ans//i for i in A)
	print(sum(B) % mod)

if __name__ == "__main__":
	main()


### FIXED CODE ###

#from math import gcd
from fractions import gcd
from functools import reduce

mod = 10**9 + 7

def lcm(a, b):
	return a * b // gcd(a, b)


N = int(input())
A = [i for i in map(int, input().split())]

ans = reduce(lcm, A)

#print(ans)
B = [ans//i for i in A]

print(sum(B) % mod)
### BUGGY CODE ###

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

count = 0
slist = []

for i in range(0,n):
    slist.append(list[i])
    if min(slist) == list[i]:
        count += 1
    else:
        pass

print(count)

### FIXED CODE ###

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

count = 0
minn = xlist[0]

for i in range(0,n):
    if minn >= xlist[i]:
        count += 1
        minn = xlist[i]
    else:
        pass

print(count)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
"""
Created on Thu Sep 20 21:40:30 2018
ABC065D
@author: maezawa
i=0...n (0-origin)
"""
import heapq

n = int(input())
a = []
b = []
for i in range(n): # i is a name of the city (0-origin)
    xy = list(map(int, input().split()))
    a.append([i,xy[0]])
    b.append([i,xy[1]])

a.sort(key=lambda x: x[1])
b.sort(key=lambda x: x[1])
#print(a) 
#print(b)

# making adj list
adj = [[] for _ in range(n)]
for i, [j, x] in enumerate(a[:-1]):
    adj[j].append([a[i+1][1]-x, a[i+1][0]])
    adj[a[i+1][0]].append([a[i+1][1]-x, j])
for i, [j, y] in enumerate(b[:-1]):
    adj[j].append([b[i+1][1]-y, b[i+1][0]])
    adj[b[i+1][0]].append([b[i+1][1]-y, j])

#print(adj)
    
# Prim's algorithm
d = [10**10]*n
visited = [False]*n
h = []
s = 0
heapq.heappush(h, [0, s])
cnt = 0
while h:
    cost, node = heapq.heappop(h)
    #if visited[node] != True and cost < d[node]:
    if visited[node] != True:        
        d[node] = cost
        visited[node] = True
        cnt += 1
        if cnt == n:
            break
        for edge in adj[node]:
            if visited[edge[1]] == True:
                continue
            heapq.heappush(h, edge)
            
#print(d)
print(sum(d))
        


### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Thu Sep 20 21:40:30 2018
ABC065D
@author: maezawa
i=0...n (0-origin)
"""
import heapq
import sys
input = sys.stdin.readline

n = int(input())
a = [[] for _ in range(n)]
b = [[] for _ in range(n)]
for i in range(n): # i is a name of the city (0-origin)
    xy = list(map(int, input().split()))
    a[i]=[xy[0],i]
    b[i]=[xy[1],i]

a.sort()
b.sort()
#print(a) 
#print(b)

# making adj list
adj = [[] for _ in range(n)]
for [x0, j0], [x1, j1]  in zip(a, a[1:]):
    adj[j0].append([x1-x0, j1])
    adj[j1].append([x1-x0, j0])
for [y0, j0], [y1, j1] in zip(b, b[1:]):
    adj[j0].append([y1-y0, j1])
    adj[j1].append([y1-y0, j0])

#print(adj)
    
# Prim's algorithm
#d = [10**10]*n
visited = [False]*n
h = []
s = 0
heapq.heappush(h, [0, s])
cnt = 0
totalcost = 0 
while h:
    cost, node = heapq.heappop(h)
    #if visited[node] != True and cost < d[node]:
    if visited[node] != True:        
        #d[node] = cost
        visited[node] = True
        totalcost += cost
        cnt += 1
        if cnt == n:
            break
        for edge in adj[node]:
            if visited[edge[1]]:
                continue
            heapq.heappush(h, edge)
            
#print(d)
print(totalcost)
### BUGGY CODE ###

n = int(input())
s_list = [input() for i in range(n)]
s_set = set(s_list)
max = 0
max_elements = []
for i in s_set:
    c = s_list.count(i)
    if c > max:
        max = c
        max_elements = [i]
    if c == max and i not in max_elements:
        max_elements.append(i)

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


### FIXED CODE ###

n = int(input())
a = dict()

for i in range(n):
    s = input()
    a.setdefault(s, 0)
    a[s] += 1

ans = []
mx = 0
for key, value in a.items():
    if mx < value:
        mx = value
        ans = [key]
    elif mx == value: ans.append(key)

ans.sort()
for i in ans: print(i)