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

N = int(input())
A = [int(input()) for _ in range(N)]
S = sum(A)
MOD = 998244353

dp1 = [[0] * (N + 1) for _ in range(S + 1)]
dp1[0][0] = 1

for t in range(1, N + 1):
    for r in range(S + 1):
        dp1[r][t] = dp1[r][t - 1] * 2 + (dp1[r - A[t - 1]][t - 1] if r - A[t - 1] >= 0 else 0)
        dp1[r][t] %= MOD

dp2 = [[0] * (N + 1) for _ in range(S + 1)]
dp2[0][0] = 1

for t in range(1, N + 1):
    for r in range(S + 1):
        dp2[r][t] = dp2[r][t - 1] + (dp2[r - A[t - 1]][t - 1] if r - A[t - 1] >= 0 else 0)
        dp2[r][t] %= MOD

cnt = 0
for r in range((S + 1) // 2, S + 1):
    cnt += dp1[r][N]

ans = 3 ** N - 3 * cnt + (3 * (dp2[S // 2][N]) if S % 2 == 0 else 0)
ans %= MOD

print(ans)


### FIXED CODE ###

N = int(input())
A = [int(input()) for _ in range(N)]
S = sum(A)
MOD = 998244353

# dp1 = [[0] * (N + 1) for _ in range(S + 1)]
dp1 = [[0] * (S + 1) for _ in range(N + 1)]
dp1[0][0] = 1

for t in range(1, N + 1):
    for r in range(S + 1):
        dp1[t][r] += dp1[t - 1][r] * 2
        dp1[t][r] += dp1[t - 1][r - A[t - 1]] if r - A[t - 1] >= 0 else 0
        dp1[t][r] %= MOD

dp2 = [[0] * (S + 1) for _ in range(N + 1)]
dp2[0][0] = 1

for t in range(1, N + 1):
    for r in range(S + 1):
        dp2[t][r] += dp2[t - 1][r]
        dp2[t][r] += dp2[t - 1][r - A[t - 1]] if r - A[t - 1] >= 0 else 0
        dp2[t][r] %= MOD

cnt = 0
for r in range((S + 1) // 2, S + 1):
    cnt += dp1[N][r]

ans = 3 ** N - 3 * cnt + (3 * (dp2[N][S // 2]) if S % 2 == 0 else 0)
ans %= MOD

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

N = int(input())
A = [input() for _ in range(N)]
already = []
for a in A:
  if a not in already:
    already.append(a)
print(len(already))

### FIXED CODE ###

N = int(input())
A = [input() for _ in range(N)]
print(len(list(set(A))))
### BUGGY CODE ###

n = int(input())
a = 1
l = input().split()
for i in range(n):
    a *= int(l[i])

if a > 1000000000000000000 :
    print(-1)
else :
    print(a)


### FIXED CODE ###

n = int(input())
a = 1
f1 = 0
f2 = 0
l = input().split()
for i in range(n):
    a *= int(l[i])
    if a > 1000000000000000000 :
        f1 = 1
        a = 1
    if a == 0:
        f2 = 1
    
if f2 == 1:
    print(0)
elif f1 == 1:
    print(-1)
else :
    print(a)
### BUGGY CODE ###

# 初期入力
import sys
from collections import defaultdict
input = sys.stdin.readline  #文字列では使わない
H,W,M = map(int, input().split())

bom_H ={i:0 for i in range(1,H+1)}
bom_W ={i:0 for i in range(1,W+1)}
posision =defaultdict(int)
for i in range(M):
    h,w = map(int, input().split())
    bom_H[h] +=1
    bom_W[w] +=1
    posision[(h,w)] =1
max_H = [kv for kv in bom_H.items() if kv[1] == max(bom_H.values())]
max_W = [kv for kv in bom_W.items() if kv[1] == max(bom_W.values())]


ans =0
for p_h,v_h in max_H:
    for p_w,v_w in max_W:
        if posision[(p_h,p_w)] ==1:
            ans =max(ans,v_h +v_w -1)
        else:
            ans =max(ans,v_h +v_w )
print(ans)

### FIXED CODE ###

import sys


H, W, M = map(int, input().split())
bomb = [tuple(map(lambda x: int(x) - 1, s.split())) for s in sys.stdin.readlines()]
X = [0] * H  # X:各行の爆破対象の個数
Y = [0] * W  # Y:各列の爆破対象の個数
for h, w in bomb:
    X[h] += 1
    Y[w] += 1
maxX = max(X)
maxY = max(Y)

R = [h for h, x in enumerate(X) if x == maxX]  # R:爆破対象の数が最大となる行の番号
C = [w for w, y in enumerate(Y) if y == maxY]  # C:爆破対象の数が最大となる列の番号

bomb = set(bomb)
for r in R:
    for c in C:
        # (r, c)に爆破対象が存在しないとき, maxX + maxY が答えとなることが確定するため, 
        # 即座に探索を終了する.
        if (r, c) not in bomb:
            print(maxX + maxY)
            exit()
print(maxX + maxY - 1)
### BUGGY CODE ###

import sys
import math

N = []
ns = sys.stdin.readlines()
for n in ns:
    N.append(int(n))
ml = max(N)
P = [2]
for x in range(3, ml+1):
    flag = True
    for d in [p for p in P if (p < int(math.sqrt(x))+1)]:
        flag = flag and (x % d != 0)
    if flag == True:
        P = P + [x]
for m in N:
    print(len([p for p in P if p<=m]))

### FIXED CODE ###

import sys
MAX = 1000000

A = tuple(range(2, MAX))
B = tuple()
while True:
    if (A[0])**2 > MAX:
        break
    B = B + (A[0],)
    A = tuple(x for x in A if x % A[0] != 0)
B = B + A

Lines = sys.stdin.readlines()
for line in Lines:
    print(len([x for x in B if x <= int(line)]))
### BUGGY CODE ###


import sys

sys.setrecursionlimit(10 ** 7)
# ----------

INF = float("inf")
MOD = 10 ** 9 + 7
# ----------

s = input().strip()
K = int(input())
N = len(s)

if N == 1:
    print(s)
    exit()
sub = set()
for i in range(N):
    for j in range(N):
        sub.add(s[i:j+1])

print(sorted(sub)[K])


### FIXED CODE ###


S = input().strip()
K = int(input())
L = len(S)
substr = set()

for i in range(L):
    for j in range(5):
        s = S[i:min(i+j+1, L)]
        if s:
            substr.add(s)

print(sorted(substr)[K-1])
### BUGGY CODE ###

def draft(A, K, N):
    for _ in range(1, K+1):# 2 * 10**5
        tmp = [0]*(N+1)
        for i in range(N):# 2 * 10**5
            L = max(0, i - A[i])
            R = min(N, i + A[i]+1)
            tmp[L] += 1
            tmp[R] -= 1
        f = True
        for i in range(N):
            tmp[i+1] += tmp[i]
            A[i] = tmp[i]
            if A[i] != N:
                f = False
        if f:
            break
    for i in range(N):
        print(A[i], end=" ")

def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    draft(A, K, N)

if __name__ == "__main__":
    main()

### FIXED CODE ###

def draft(A, K, N):
    for _ in range(1, K+1):# 2 * 10**5
        tmp = [0]*(N+1)
        for i in range(N):# 2 * 10**5
            L = max(0, i - A[i])
            R = min(N, i + A[i]+1)
            tmp[L] += 1
            tmp[R] -= 1
        f = True
        for i in range(N):
            tmp[i+1] += tmp[i]
            A[i] = tmp[i]
            if A[i] != N:
                f = False
        if f:
            break
    for i in range(N):
        print(A[i], end=" ")

def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    draft(A, K, N)

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

import collections

n = int(input())
a = [int(i) for i in input().split()]

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

list = []
for i in a:
    list.extend(make_divisors(i))

c = collections.Counter(list)
values, counts = zip(*c.most_common())

first = []
second = []
for value, count in zip(values,counts):
    if count == n:
        first.append(value)
    if count == n-1:
        second.append(value)
    if count < n-1:
        break

if len(second) == 0:
    print(max(first))

elif max(first) > max(second):
    print(max(first))

else:
    print(max(second))

### FIXED CODE ###

import copy
n = int(input())
x = [int(i) for i in input().split()]

#ユークリッド互除法の関数の定義
def gcd(a,b):
    if b==0:return a
    return gcd(b,a%b)


def gcd_multi(n,x):
    if n==1:
        return x[0]
    else:
        element = gcd(x[0], x[1])
        if n==2:
            return element
        else:
            for i in range(2,n):
                element=gcd(element,x[i])
            return element

X=[0 for i in range(n)]
Y=[0 for i in range(n)]

for i in range(1,n):
    X[i]=gcd(X[i-1],x[i-1])

for i in range(n-1)[::-1]:
    Y[i]=gcd(Y[i+1],x[i+1])

Z=[gcd(X[i],Y[i]) for i in range(n)]
print(max(Z))
### BUGGY CODE ###


n=int(input())
a=list(map(int,input().split()))
s=0
m={}
for i in set(a):
    c=a.count(i)
    m[i]=c
    s+=c*(c-1)//2
for i in a:
    print(s-m[i]+1)

### FIXED CODE ###

from collections import Counter

n=int(input())
a=list(map(int,input().split()))
s=0
m=Counter(a)
for i in m.values():
    s+=i*(i-1)//2
for i in a:
    print(s-m[i]+1)
### BUGGY CODE ###

def run():
  N, W = map(int, input().split())
  wv_li = [[0, 0]]+[list(map(int, input().split())) for n in range(N)]
  dp = [[0]*(N+1) for w in range(W+1)]
  #print(wv_li)
  #print(dp)
  for w in range(1, W+1):
    for n in range(1, N+1):
      wn, vn = wv_li[n]
      if w < wn:
        dp[w][n] = dp[w][n-1]
      else:
        dp[w][n] = max(dp[w][n-1], dp[w-wn][n-1]+vn)
  print(dp[W][N])
      
  
if __name__ == '__main__':
  run()

### FIXED CODE ###

def run():
  N, W = map(int, input().split())
  wv_li = [[0, 0]]+[list(map(int, input().split())) for n in range(N)]
  dp = [[0]*(N+1) for w in range(W+1)]
  #print(wv_li)
  #print(dp)
  for w in range(1, W+1):
    for n in range(1, N+1):
      wn, vn = wv_li[n]
      if w < wn:
        dp[w][n] = dp[w][n-1]
      else:
        dp[w][n] = max(dp[w][n-1], dp[w-wn][n-1]+vn)
  print(dp[W][N])
      
  
if __name__ == '__main__':
  run()
### BUGGY CODE ###

N = int(input())
X = input()
Xi = int(X, 2)

c0 = X.count('1')
for i, x in enumerate(X):
    if x == '1':
        y = Xi - (1 << (N - 1 - i))
        c = c0 - 1
    else:
        y = Xi + (1 << (N - 1 - i))
        c = c0 + 1

    if not y:
        print(0)
        continue
    y %= c
    ans = 1
    while y:
        y %= bin(y).count('1')
        ans += 1
    print(ans)


### FIXED CODE ###

N = int(input())
X = input()
Xi = int(X, 2)

c0 = X.count('1')
Xp = Xi % (c0 + 1)

if c0 != 1:
    Xm = Xi % (c0 - 1)

for i, x in enumerate(X):
    if x == '1':
        if c0 == 1:
            print(0)
            continue
        y = (Xm - pow(2, N - 1 - i, c0 - 1)) % (c0 - 1)
    else:
        y = (Xp + pow(2, N - 1 - i, c0 + 1)) % (c0 + 1)

    ans = 1
    while y:
        y %= bin(y).count('1')
        ans += 1
    print(ans)
### BUGGY CODE ###

from math import factorial

def power(a, b, p): #a^b (mod p)を求める #二分累乗法を使う
    if b == 0:
        return 1
    elif b % 2 == 0:
        return power(a, b//2, p) ** 2 % p
    else:
        return power(a, b//2, p) ** 2 * a % p

H, W, A, B = map(int, input().split())
C = H - A
D = W - B
p = 1000000007
b = power(factorial(B-1), p-2, p)
d = power(factorial(D-1), p-2, p)

x = 0
for i in range(C):
    k = factorial(i+B-1) % p
    l = factorial(D+H-i-2) % p
    x += (k * l * b * d * power(factorial(i), p-2, p) * power(factorial(H-i-1), p-2, p)) % p
print(x % p)


### FIXED CODE ###

H, W, A, B = map(int, input().split())
C = H - A
D = W - B
p = 1000000007

def power(a, b): #a^b (mod p)を求める #二分累乗法を使う
    if b == 0:
        return 1
    elif b % 2 == 0:
        return power(a, b//2) ** 2 % p
    else:
        return power(a, b//2) ** 2 * a % p

f = [1] #f[i] = i! % p
for i in range(H+W):
    f.append(f[i] * (i+1) % p)

I_f = [0] * (H+W+1) #I_f[i] = (i!)^(-1) % p
I_f[H+W] = power(f[H+W], p-2)
for i in reversed(range(H+W)):
    I_f[i] = I_f[i+1] * (i+1) % p

def combi(a, b): #(a+b)!/a!b! (mod p)を求める
    return f[a+b] * I_f[a] * I_f[b] % p

x = 0
for i in range(C):
    x = (x + combi(i, B-1) * combi(D-1, H-i-1)) % p
print(x)
### BUGGY CODE ###

k,s=map(int,input().split())
ans=0
for x in range(0,k+1):
            for y in range(0,k+1):
                        for z in range(0,k+1):
                                    if  x+y+z==s:
                                                #print('1','x',x,'y',y,'z',z)
                                                ans+=1
                                                
print(ans)


### FIXED CODE ###

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

import bisect
#import sys
#input = sys.stdin.readline
 
n = int(input())
l = [int(li) for li in input().split(' ')]
l.sort()

cnt = 0
for i in range(n):
  for j in range(n-i-1):
    cnt += bisect.bisect_left(l[j+i+2:], l[i] + l[j+i+1])
    
print(cnt)

### FIXED CODE ###

import bisect
import sys
input = sys.stdin.readline
 
n = int(input())
l = [int(li) for li in input().split(' ')]
l.sort()

cnt = 0
for i in range(n):
  for j in range(i+1, n):
    cnt += bisect.bisect_left(l, l[i]+l[j])-j-1
    
print(cnt)
### BUGGY CODE ###

N = int(input())
ans = 0
for i in range(1,N):
  ans += i % (i+1)
print(ans)

### FIXED CODE ###

N = int(input())
print(N*(N-1) // 2)
### BUGGY CODE ###

import sys
from bisect import bisect_left


class RangeUpdateTree:
    def __init__(self, n, initial=-1, sentinel=-2):
        n2 = 1 << n.bit_length()
        self.n = n2
        self.offset = n2
        self.data = [initial] * (n2 << 1)
        self.sentinel = sentinel

    def update(self, a, b, x):
        stack = [(1, 0, self.n)]
        while stack:
            i, l, r = stack.pop()
            if a <= l and r <= b:
                self.data[i] = x
                continue
            y = self.data[i]
            j = i << 1
            if y != self.sentinel:
                self.data[i] = self.sentinel
                self.data[j] = self.data[j + 1] = y
            m = (l + r) // 2
            if a < m:
                stack.append((j, l, m))
            if m < b:
                stack.append((j + 1, m, r))

    def aggregate(self):
        stack = [1]
        ans = 0
        while stack:
            i = stack.pop()
            if self.data[i] != self.sentinel:
                ans += self.data[i] * (self.n >> i.bit_length() - 1)
                continue
            i <<= 1
            stack.append(i)
            stack.append(i + 1)
        return ans

    def propagate(self):
        stack = [(1, 0, self.n)]
        while stack:
            i, l, r = stack.pop()
            if self.data[i] != self.sentinel:
                self.data[l + self.offset:r + self.offset] = [self.data[i]] * (r - l)
                continue
            i <<= 1
            m = (l + r) // 2
            stack.append((i, l, m))
            stack.append((i + 1, m, r))

    def debug_print(self):
        i = 1
        while i <= self.offset:
            print(self.data[i:2 * i])
            i <<= 1


n, q = list(map(int, input().split()))
lines = sys.stdin.readlines()
kkk = []
for line in lines[:n]:
    s, t, x = list(map(int, line.split()))
    kkk.append((x, s, t))
kkk.sort(reverse=True)
ddd = list(map(int, lines[n:]))
rut = RangeUpdateTree(q)
for x, s, t in kkk:
    ss = bisect_left(ddd, s - x)
    tt = bisect_left(ddd, t - x)
    if ss == tt:
        continue
    # print(x, s, t, s - x, t - x, ss, tt)
    rut.update(ss, tt, x)
rut.propagate()
# rut.debug_print()
print('\n'.join(map(str, rut.data[rut.offset:rut.offset + q])))


### FIXED CODE ###

import sys
from bisect import bisect_left

n, q = map(int, input().split())
lines = sys.stdin.readlines()
kkk = []
for line in lines[:n]:
    s, t, x = map(int, line.split())
    kkk.append((x, s, t))
kkk.sort()
ddd = list(map(int, lines[n:]))

ans = [-1] * q
skip = [-1] * q
for x, s, t in kkk:
    ss = bisect_left(ddd, s - x)
    tt = bisect_left(ddd, t - x)
    while ss < tt:
        if skip[ss] == -1:
            ans[ss] = x
            skip[ss] = tt
            ss += 1
        else:
            ss = skip[ss]
print('\n'.join(map(str, ans)))
### BUGGY CODE ###

def primes(n):
  l = [1 for i in range(n+1)]
  l[0] = l[1] = 0
  for i in range(2,int((n)**(1/2))+1):
    if l[i] == 1:
      for j in range(2,(n)//i+1):
        l[i*j] = 0
  l2 = [n for n in range(len(l)) if l[n]]
  return l2

l = primes(50000)

while True:
  n = int(input())
  if n == 0:
    break
  count = 0
  for i in range(1,n//2+1):
    if (i in l) and ((n-i) in l):
      count += 1
  print(count)

### FIXED CODE ###

def primes(n):
  l = [1 for i in range(n+1)]
  l[0] = l[1] = 0
  for i in range(2,int((n)**(1/2))+1):
    if l[i] == 1:
      for j in range(2,n//i+1):
        l[i*j] = 0
  return l

l = primes(50000)
while True:
  n = int(input())
  if n == 0:
    break
  count = 0
  if not(n%2):
    for i in range(3,n//2+1,2):
      if (l[i] and l[n-i]):
        count += 1
    if n == 4:
      count = 1
  else:
    if l[n-2]:
      count += 1
  print(count)
### BUGGY CODE ###

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

ans = 0

for i in range(len(A_int_list)):
    ans += A_int_list[i] * sum(A_int_list[i + 1:])

print(ans % (10 ** 9 + 7))


### FIXED CODE ###

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

ans = 0
sum_A = sum(A_int_list)

for i in range(len(A_int_list)):
    sum_A -= A_int_list[i]
    ans += A_int_list[i] * sum_A


print(ans % (10 ** 9 + 7))
### BUGGY CODE ###

N, K = map(int, input().split())
h = list(map(int, input().split()))
 
S = [0] * N
S[0] = 0
 
for i in range(1, N):
    value = S[i - 1] + abs(h[i] - h[i - 1])
    maxStep = min(K, i)
    for step in range(1, maxStep + 1):
        value = min(value, S[i - step] + abs(h[i] - h[i - step]))
    S[i] = value
print(S[N - 1])

### FIXED CODE ###

N,K=map(int,input().split())
h=list(map(int,input().split()))
dp=[0]*(N)
dp[1]=abs(h[0]-h[1])
for i in range(2,N):
    dp[i]=min(dp[j]+abs(h[j]-h[i]) for j in range(max(0,i-K),i))
print(dp[N-1])
### BUGGY CODE ###

import numpy as np

import sys
sys.setrecursionlimit(10**7)
n = int(input())

D = np.full((n+1, n+1, n+1), -1)
def dfs(a, b, c, d):
  if a == n:
    return 0
  if D[a, b, c] != -1:
    return D[a, b, c]
  rep = n
  if b != 0:
    rep += b * dfs(a+1, b-1, c, d)
  if c != 0:
    rep += c * dfs(a, b+1, c-1, d)
  if d != 0:
    rep += d * dfs(a, b, c+1, d-1)
  rep /= (n-a)
  D[a, b, c] = rep
  return rep

L = [0]*4
for a in map(int, input().split()):
  L[a] += 1
ans = dfs(*L)
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
n = int(input())
A = tuple(map(int, input().split()))
C = [0]*3
for a in A:
  C[a-1] += 1
dp = [[[-1]*(n+1) for i in range(n+1)] for j in range(n+1)]
dp[0][0][0] = 0
def f(i, j, k):
  if dp[i][j][k] != -1:
    return dp[i][j][k]
  res = 1
  if i:
    res += f(i-1, j, k)*(i/n)
  if j:
    res += f(i+1, j-1, k)*(j/n)
  if k:
    res += f(i, j+1, k-1)*(k/n)
  res /= (i+j+k)/n
  dp[i][j][k] = res
  return res
ans = f(C[0], C[1], C[2])
print(ans)
### BUGGY CODE ###

N=int(input())
s=input()
count=[]
for i in range(N):
    count.append(0)
    for k in range(i-1):
        if(s[k]=='W'):
            count[i]=count[i]+1
    for j in range(1,N-i):
        if(s[i+j]=='E'):
            count[i]=count[i]+1
print(min(count))

### FIXED CODE ###

import numpy as np
N=int(input())
s=input()
west=[]
east=[]
for i in range(N):
    west.append(0)
    east.append(0)
    if(s[i]=='W'):
        west[i]=1
    else:
        east[i]=1
eastsum=np.zeros(N)
westsum=np.zeros(N)
westsum[0]=west[0]
eastsum[N-1]=east[N-1]
for i in range(1,N):
    eastsum[N-1-i]=eastsum[N-i]+east[N-1-i]
    westsum[i]=westsum[i-1]+west[i]
print(int(np.min(eastsum+westsum))-1)
### BUGGY CODE ###

import itertools
import math


def resolve():
    n = int(input())
    A = list(map(int, input().split()))
    B = itertools.combinations(A, 2)
    C = list(map(lambda x: math.gcd(x[0], x[1]), B))

    if len(list(set(C))) == 1 and list(set(C))[0] == 1:
        print("pairwise coprime")
    elif len(list(set(C))) != 1:
        print("setwise coprime")
    elif len(list(set(C))) == 1:
        print("not coprime")

resolve()

### FIXED CODE ###

import math


def resolve():
    n = int(input())
    A = list(map(int, input().split()))
    M = max(A) + 1
    C = [0 for i in range(M)]
    for a in A:
        C[a] += 1

    pairwise = True
    for i in range(2, M):
        cnt = 0
        for j in range(i, M, i):
            cnt += C[j]

        if cnt > 1:
            pairwise = False

    if pairwise:
        print("pairwise coprime")
        return

    g = 0
    for i in range(n):
        g = math.gcd(g, A[i])

    if g == 1:
        print("setwise coprime")
        return

    print("not coprime")

resolve()
### BUGGY CODE ###

#!/usr/bin/env python3
#ABC65 D

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7

n = int(sys.stdin.readline())
par = [i for i in range(n)]
rank = [0]*n
def find(x):
    if par[x] == x:
        return x
    else:
        par[x] = find(par[x])
        return par[x]

def union(x,y):
    x = find(x)
    y = find(y)
    if rank[x] < rank[y]:
        par[x] = y
    else:
        par[y] = x
        if rank[x] == rank[y]:
            rank[x] += 1

x,y,c = [],[],[]
for i in range(n):
    a,b = map(int,sys.stdin.readline().split())
    x.append((a,i))
    y.append((b,i))
    c.append((a,b))
x.sort()
y.sort()
h = []
for i in range(n-1):
    x1, j1 = x[i]
    x2, j2 = x[i+1]
    y1, k1 = y[i]
    y2, k2 = y[i+1]
    heappush(h,(x2-x1, j1, j2))
    heappush(h,(y2-y1, k1, k2))
ans = 0
while h:
    w,s,t = heappop(h)
    if find(s) != find(t):
        union(s,t)
        ans += w
print(ans)


### FIXED CODE ###

#!/usr/bin/env python3
#ABC65 D

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heapify
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7

n = int(sys.stdin.readline())
par = [i for i in range(n)]
rank = [0]*n
def find(x):
    if par[x] == x:
        return x
    else:
        par[x] = find(par[x])
        return par[x]

def union(x,y):
    x = find(x)
    y = find(y)
    if rank[x] < rank[y]:
        par[x] = y
    else:
        par[y] = x
        if rank[x] == rank[y]:
            rank[x] += 1

x,y = [],[]
for i in range(n):
    a,b = map(int,sys.stdin.readline().split())
    x.append((a,i))
    y.append((b,i))
x.sort()
y.sort()
h = []
heapify(h)
for i in range(n-1):
    x1, j1 = x[i]
    x2, j2 = x[i+1]
    y1, k1 = y[i]
    y2, k2 = y[i+1]
    heappush(h,(x2-x1, j1, j2))
    heappush(h,(y2-y1, k1, k2))
ans = 0
x = 0
while h:
    w,s,t = heappop(h)
    if find(s) != find(t):
        x += 1
        union(s,t)
        ans += w
    if x == n-1:
        break
print(ans)
### BUGGY CODE ###

n = int(input())
ls = [x for x in map(int, input().split(' '))]
for x in range(0, n):
    dam = ls.copy()
    del dam[x]
    dam = sorted(dam)
    print(dam[int(len(dam)/ 2)])

### FIXED CODE ###

n = int(input())
ls = [x for x in map(int, input().split(' '))]
dam = sorted(ls.copy())

for x in range(0, n):
    if ls[x] < dam[n // 2]:
        print(dam[n // 2])
    else:
        print(dam[(n // 2) - 1])
### BUGGY CODE ###

LIM=200002
L=[0]*LIM

def bin_sum(Y):
    S=bin(Y)[2:]
    count=0
    for i in range(len(S)):
        count+=int(S[i])
    return count

def bin_sum2(Y):
    count=0
    for i in range(len(Y)):
        count+=int(Y[i])
    return count

for i in range(1,LIM):
    L[i]+=bin_sum(i)

def pop_num(N,b,L):
    if N==0:
        return 0
    v=N%b
    return pop_num(v,L[v],L)+1
    
M=[0]*200002
for i in range(1,200002):
    M[i]+=pop_num(i,L[i],L)
X=int(input())
Y=input()
d=bin_sum2(Y)+1
c=bin_sum2(Y)-1
e=int(Y,2)
for i in range(X):
    if Y[i]=="0":
        b=d
        f=e+2**(X-1-i)
    else:
        b=c
        f=e-2**(X-1-i)
    if f==0:
        print(0)
    else:
        print(M[f%b]+1)

### FIXED CODE ###

from collections import deque
LIM=200004
L=[0]*LIM

def bin_sum(Y):
    S=bin(Y)[2:]
    count=0
    for i in range(len(S)):
        count+=int(S[i])
    return count

def bin_sum2(Y):
    count=0
    for i in range(len(Y)):
        count+=int(Y[i])
    return count

for i in range(1,LIM):
    L[i]+=bin_sum(i)

def pop_num(N,b,L):
    if N==0:
        return 0
    v=N%b
    return pop_num(v,L[v],L)+1
    
M=[0]*200005
for i in range(1,200004):
    M[i]+=pop_num(i,L[i],L)
X=int(input())
Y=input()
d=bin_sum2(Y)
e=int(Y,2)%(d+1)
f=int(Y,2)%max(1,(d-1))
O=[1]*(X+2)
P=[1]*(X+2)
q=max(d-1,1)
for i in range(1,X+1):
    O[i]=O[i-1]*2%q
    P[i]=P[i-1]*2%(d+1)
for i in range(X):
    
    if int(Y[i])==1:
        b=max(d-1,1)
        flag=max(0,d-1)
        g=(f-O[X-1-i]+b)%b
    else:
        b=d+1
        flag=1
        g=(e+P[X-1-i])%b

    if flag==0:
        print(0)
    elif g==0:
        print(1)
    else:
        print(M[g]+1)