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

k=int(input())

def judge(s):
    flag = 1
    if len(s)<=1: return 1
    for i in range(len(s)-1):
        s1, s2 = int(s[i]),int(s[i+1])
        if abs(abs(s1)-abs(s2)) <= 1: continue
        else:
            flag = 0 
            break
    return flag


def bfs(k, cnt=1, now=1):
    while True:
        s=str(now)
        if judge(s) and k==cnt: return now
        elif judge(s):
            cnt+=1
            now+=1
        else: now+=1

print(bfs(k,1,1))


### FIXED CODE ###

from collections import deque
k=int(input())
stack = deque([1,2,3,4,5,6,7,8,9])

def lunlun():
    cnt=0
    while True:
        now = stack.popleft()
        cnt += 1
        if cnt == k: return now
        s = str(now)
        for i in range(-1,2):
            temp=int(s[-1]) + i 
            if temp>=0 and temp<10: 
                temp1=int(s + str(temp))
                stack.append(temp1)
print(lunlun())
### BUGGY CODE ###

import numpy as np


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

max = 0
for i in range(N-K+1):
    tmp = np.sum(p[i:i+K])
    if tmp>max:
        max = tmp

print((max+K)/2)


### FIXED CODE ###

import numpy as np

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

tmp = np.sum(p[:K])
max = tmp
for i in range(N-K):
    tmp = tmp-p[i]+p[i+K]
    if tmp>max:
        max = tmp

print((max+K)/2)
### BUGGY CODE ###

n=int(input())
a=sorted(map(int,input().split()))
data=[]
for i in range(n):
  judge=True
  for j in range(n):
    if i==j:
      continue
    if a[i]%a[j]==0:
      judge=False
  if judge:
    data.append(a[i])
print(len(data))

### FIXED CODE ###

import collections as c
n,a1=int(input()),[*map(int,input().split())]
a2,a3,b=set(a1),c.Counter(a1),[0]*(10**6+1)
for i in a2:
  for j in range(i,10**6+1,i):
    b[j]+=1
print(sum(b[i]==1 and a3[i]==1 for i in a2))
### BUGGY CODE ###

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

sapp = [[0] * n for _ in range(10)]

for idx, s in enumerate(S):
    si = int(s)
    sapp[si][idx] = 1

from itertools import accumulate
sacc = [list(accumulate(sa)) for sa in sapp]

pins = set()
for i in range(1, n-1):
    for lnum in range(10):
        lnumc = sacc[lnum][i-1]
        if lnumc == 0:
            continue
        for rnum in range(10):
            # i+1から最後までで出現するか
            rnumc = sacc[rnum][-1] - sacc[rnum][i]
            if rnumc > 0:
                pins.add(str(lnum) + S[i] + str(rnum))

print(len(pins))

### FIXED CODE ###

n = int(input())
S = input()
ans = 0
nums = list(map(str, range(10)))
for i in nums:
    s1 = S.find(i)
    if s1 < 0:
        continue
    for j in nums:
        s2 = S.find(j, s1+1)
        if s2 < 0:
            continue
        for k in nums:
            s3 = S.find(k, s2+1)
            if s3 > 0:
                ans += 1
print(ans)
### BUGGY CODE ###

def main():
    num_1 = input()
    lis = list(input().split())
    s = 1
    num_2 = int (num_1)
    if 0 in lis:
        return 0
    for x in range(num_2):
        s = s * int(lis[x])
    if s > 10**18:
        return -1
    return s

print(main())

### FIXED CODE ###

def main():
    num_1 = input()
    lis = list(map(int,input().split()))
    s = 1
    num_2 = int (num_1)
    num = 10 ** 18
    if 0 in lis:
        print(0)
        return
    for x in range(num_2):
        s = s * int(lis[x])
        if s > num:
            print(-1)
            return
    print(s)
    return

main()
### BUGGY CODE ###

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

for i in range(Q):
    B, C = map(int, input().split())
    A = [C if i == B else i for i in A]
    print(sum(A))



### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
s = [0] * (10**5+5)
Q = int(input())
total = sum(A)

for i in A:
    s[i] += 1

for _ in range(Q):
    B, C = map(int, input().split())
    d = s[B]
    s[B] = 0
    s[C] += d
    total += (C-B) * d
    print(total)
### BUGGY CODE ###

n=int(input())
s=input()
k=[i for i in range(0,n)]
from itertools import combinations
c=list(combinations(k,3))
ans=0
for i in range(len(c)):
  p=c[i][0]
  q=c[i][1]
  r=c[i][2]
  if s[p]!=s[q] and s[q]!=s[r] and s[p]!=s[r] and q-p!=r-q:
    ans=ans+1
print(ans)  

### FIXED CODE ###

n=int(input())
s=list(input())
a=s.count("R")
b=s.count("G")
c=s.count("B")
ans=0
for i in range(n-2):
  for j in range(i+1,n-1):
    k=2*j-i
    if n-1>=k and (s[i]!=s[j] and s[i]!=s[k] and s[j]!=s[k]): 
      ans=ans+1
print(a*b*c-ans)
### BUGGY CODE ###

n = int(input())
numlist = list(map(int,input().split()))
numcount = [0]*10**6
for num in numlist:
    numcount[num] += 1
n = int(input())
anslist = []
for i in range(n):
    b,c = map(int,input().split())
    numcount[c] += numcount[b]
    numcount[b] = 0
    result = 0
    for i,num in enumerate(numcount):
        result += i*num
    anslist.append(result)

for ans in anslist:
    print(ans)


### FIXED CODE ###

n = int(input())
numlist = list(map(int,input().split()))
numcount = [0]*10**6

numset = set()
for num in numlist:
    numcount[num] += 1
    numset.add(num)
n = int(input())
anslist = []
result = 0
for num in list(numset):
    result += numcount[num]*num
    
for i in range(n):
    b,c = map(int,input().split())
    numcount[c] += numcount[b]
    result += (c-b)*numcount[b]
    anslist.append(result)

    numcount[b] = 0
    numset.add(c)
    numset.discard(b)

for ans in anslist:
    print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()
from bisect import bisect_left

def main():
    H, W = LI()
    hs = [[-1] for _ in range(H)]
    ws = [[-1] for _ in range(W)]
    for h in range(H):
        s = SI()
        for w, ss in enumerate(s):
            if ss == '#':
                hs[h].append(w)
                ws[w].append(h)
    for h in range(H):
        hs[h].append(W)
    for w in range(W):
        ws[w].append(H)
    ah = [[0] * W for _ in range(H)]
    aw = [[0] * H for _ in range(W)]
    for hh, h in enumerate(hs):
        for wi in range(len(h) - 1):
            l, u = h[wi] + 1, h[wi + 1]
            cnt = u - l
            for i in range(l, u):
                ah[hh][i] = cnt
    for ww, w in enumerate(ws):
        for hi in range(len(w) - 1):
            l, u = w[hi] + 1, w[hi + 1]
            cnt = u - l
            for i in range(l, u):
                aw[ww][i] = cnt
    ans = 0
    for h in range(H):
        for w in range(W):
            ans = max(ans, aw[w][h] + ah[h][w] - 1)
    return ans

print(main())

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()
import numpy

def main():
    H, W = LI()
    S = []
    for i in range(H):
        S.append(list(SI()))
    S = (numpy.array(S) == '.')
    L = numpy.zeros((H, W), dtype=int)
    R = numpy.zeros((H, W), dtype=int)
    T = numpy.zeros((H, W), dtype=int)
    B = numpy.zeros((H, W), dtype=int)
    for i in range(H):
        L[i] = (L[i - 1] + 1) * S[i]
        R[-1 - i] = (R[-i] + 1) * S[-1 - i]
    for i in range(W):
        T[:, i] = (T[:, i - 1] + 1) * S[:, i]
        B[:, -1 - i] = (B[:, -i] + 1) * S[:, -1 - i]
    ans = numpy.max(L + R + T + B) - 3
    return ans

print(main())
### BUGGY CODE ###

in_n, in_cond = map(int, input().split())
def hoge(n, cond):
    for k in range(n+1):
        for j in range(n+1):
            for i in range(n+1):
                if((i + j + k == n) & (10000 * i + 5000 * j + 1000 * k == cond)):
                    return [str(i), str(j), str(k)]
    return ["-1","-1","-1"]
print(" ".join(hoge(in_n, in_cond)))


### FIXED CODE ###

in_n, in_cond = map(int, input().split())
def hoge(n, cond):
    for i in range(n+1):
        for j in range(n + 1 -i):
            if(10000 * i + 5000 * j + 1000 * (n - i - j) == cond):
                return [str(i), str(j), str(n - i - j)]
    return ["-1","-1","-1"]
print(" ".join(hoge(in_n, in_cond)))
### BUGGY CODE ###

from collections import defaultdict
from heapq import heappop, heappush
import sys
input=sys.stdin.readline 

class Graph:
 
    def __init__(self):
        self.graph = defaultdict(list)
        self.vertices = set()
        self.edges = []
 
    def add_edge(self, a, b, weight=1):
        self.graph[a].append((b, weight))
        self.vertices |= {a, b}
        self.edges.append((a, b, weight))
 
    def get_vertices(self):
        return sorted(list(self.vertices))
 
    def num_of_vertices(self):
        return len(self.vertices)
 
    def get_edges(self):
        return self.edges
 
    def num_of_edges(self):
        return len(self.edges)
 
class Dijkstra:
 
    def __init__(self, graph, start):
        self.g = graph.graph
 
        self.dist = defaultdict(lambda: float("inf"))
        self.dist[start] = 0
 
        self.prev = defaultdict(lambda: None)
 
        self.Q = []
        heappush(self.Q, (0, start))
 
        while self.Q:
            dist_u, u = heappop(self.Q)
 
            if self.dist[u] < dist_u:
                continue
 
            for v, weight in self.g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q, (alt, v))
 
 
    def shortest_distance(self, goal):
 
        return self.dist[goal]
 
    def shortest_path(self, goal):
 
        path = []
        vertice = goal
        while vertice is not None:
            path.append(vertice)
            vertice = self.prev[vertice]
 
        return path[::-1]

N, M = map(int, input().split())
G = Graph()
T = []
C = defaultdict(int)
for _ in range(M):
    a, b, c = map(int, input().split())
    G.add_edge(a, b, c)
    G.add_edge(b, a, c)
    T.append(tuple(sorted([a, b])))

for i in range(1, N+1):
    for j in range(1, N+1):
        D = Dijkstra(G, i)
        P = D.shortest_path(j)
        for k in range(len(P)-1):
            a, b = P[k], P[k+1]
            C[tuple(sorted([a, b]))] = 1

ans = 0
for a, b in T:
    if C[(a, b)] == 0:
        ans += 1

print(ans)

### FIXED CODE ###

N, M = map(int, input().split())
inf = float("inf")
dist = [[inf for _ in range(N)] for _ in range(N)]
for i in range(N):
    dist[i][i] = 0

T = []
for i in range(M):
    a, b, c = map(int, input().split())
    a, b = a-1, b-1
    T.append((a, b, c))
    dist[a][b] = min(dist[a][b], c)
    dist[b][a] = min(dist[b][a], c)

for k in range(N):
    for i in range(N):
        for j in range(N):
            dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j])

ans = M
for a, b, c in T:
    check = False
    for i in range(N):
        if dist[i][a] + c == dist[i][b]:
            check = True
    if check:
        ans -= 1
print(ans)
### BUGGY CODE ###

from collections import deque
n, m = map(int, input().split())
route = [[0] * n for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    route[a-1][b-1] = 1
    route[b-1][a-1] = 1

q = deque()
visited = [0] * n
pre = [-1] * n
q.append(0)
visited[0] = 1
while q:
    # visitした
    v = q.popleft()
    for i in range(n):
        if visited[i] == 1 or route[v][i] == 0: continue
        visited[i] = 1
        pre[i] = v
        q.append(i)
print("Yes")
for p in pre[1:]:
    p += 1
    print(p)

### FIXED CODE ###

from collections import deque
n, m = map(int, input().split())
to = [[] for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    a -= 1; b -= 1
    to[a].append(b)
    to[b].append(a)
q = deque()
visited = [0 for _ in range(n)]
pre = [-1 for _ in range(n)]
q.append(0)
visited[0] = 1
while q:
    # visitした
    v = q.popleft()
    for u in to[v]:
        if visited[u] == 1: continue
        visited[u] = 1
        pre[u] = v
        q.append(u)
print("Yes")
for p in pre[1:]:
    p += 1
    print(p)
### BUGGY CODE ###

N,K=map(int,input().split())
t=list(map(int,input().split()))
g=[1]
for i in range(N):
  if g.count(t[g[i]-1])!=0:
    h=g.index(t[g[i]-1])
    s=i+1-h
    break
  g.append(t[g[i]-1])
if K>h:
  K=(K-h)%s+h
print(g[K])

### FIXED CODE ###

N, K = map(int, input().split())
T_list = list(map(int, input().split()))
T_list = [T_list[i]-1 for i in range(N)]
point = 0
syuuki = 0

if K < N:
  i = 0
  while i < K:
    point = T_list[point]
    i += 1  

else:
  i = 0
  while i < N:
    point = T_list[point]
    if point == 0:
      syuuki = i+1
      break
    i += 1
  second_point = point
  
  if syuuki != 0:
    L = K % syuuki

  else:
    j = 0
    while j < N:
      point = T_list[point]
      if point == second_point:
        syuuki = j+1
        break
      j += 1
    L = (K-i) % syuuki

  k = 0
  while k < L:
    point = T_list[point]
    k += 1
  
print(point+1)
### BUGGY CODE ###

#!/usr/bin/env python3
import math
def cmb(n, a, p):
    ans = 1
    for i in range(a):
        ans *= (n-i)
    return (ans // math.factorial(a)) % p

p = 10 ** 9 + 7
n,a,b = map(int,input().split())
#print(cmb(n,a,p),cmb(n,b,p))
print((2**n - 1 - cmb(n,a,p) - cmb(n,b,p))%p)

### FIXED CODE ###

#!/usr/bin/env python3
def fac(n,a):
  ans = 1
  for i in range(n,n-a,-1):
    ans *= i
    ans %= mod
  return ans
def cmb(n, a, mod):
    ans = fac(n,a)
    inv = fac(a,a-1)
    return (ans*pow(inv,mod-2,mod)) % mod

n,a,b = map(int,input().split())
mod = 10**9 + 7
#他人のコードパクったけど高速化の理由不明
"""
def pow(n,b,mod):
  if n == 0: return 1
  if n % 2: return 2 * pow(n//2,b,mod)**2 % mod
  else: return pow(n//2,b,mod)**2 % mod"""
print((pow(2,n,mod) - 1 - cmb(n,a,mod) - cmb(n,b,mod))%mod)
### BUGGY CODE ###

# s = open(0).read().rstrip()
from sys import stdin
s = stdin.readline().rstrip()

state = [1]*len(s)

# from collections import defaultdict

# d = defaultdict(int)
d = set()
i = 0

def transit(l, s):
    tmp = [0]*len(l)
    for i in range(len(l)):
        if s[i] == 'R':
            tmp[i+1] += l[i]
        else:
            tmp[i-1] += l[i]
    return tmp

d.add(tuple(state))

while 1:
    state = transit(state, s)
    i += 1
    tup = tuple(state)
    if tup in d:
        break
    d.add(tup)

if i%2:
    state = transit(state, s)

print(*state)

### FIXED CODE ###

s = input().rstrip() + 'X'

r_cnt = l_cnt = 0
is_r = True
begin_l = None
ans = [0] * (len(s)-1)
for i in range(len(s)):
    if is_r and s[i] == 'R':
#         print(f'{i}: R')
        r_cnt += 1
    elif not is_r and s[i] == 'L':
#         print(f'{i}: L')
        l_cnt += 1
    elif s[i] == 'L':
#         print(f'{i}: R>L')
        is_r = False
        l_cnt = 1
        begin_l = i
    else:
#         print(f'{i}: L>?')
        is_r = True
#         print(l_cnt, r_cnt)
        tot = l_cnt + r_cnt
        small = tot//2
        large = tot - small
        if r_cnt%2:
            ans[begin_l-1] = large 
            ans[begin_l] = small
        else:
            ans[begin_l-1] = small
            ans[begin_l] = large
        r_cnt = 1
        l_cnt = 0

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

def resolve():
	s = input()
	ans = 0
	for i in range(0, len(s)):
		for j in range(3, len(s)):
			if i + j >= len(s):
				break
			if not int(s[i:i + j + 1]) % 2019:
				ans += 1
	print(ans)
resolve()

### FIXED CODE ###

def resolve():
    s = input()
    s = s[::-1]
    c = [0]*2019
    # why?
    c[0] = 1
    r = 0
    d = 1
    for i in s:
        num = int(i) * d % 2019 + r
        num %= 2019
        c[num] += 1
        r = num
        d *= 10
        d %= 2019
    ans = 0
    for i in c:
        ans += i*(i-1)//2
    print(ans)
resolve()
### BUGGY CODE ###

import sys, math
from collections import deque
sys.setrecursionlimit(500000)
MOD = 10**9+7

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

def mi():
    return map(int, input().split())

def ii():
    return int(input())

def i2(n):
    tmp = [list(mi()) for i in range(n)]
    return [list(i) for i in zip(*tmp)]

def f(x):
    if x < 0:
        return False
    if x in [100, 101, 102, 103, 104, 105]:
        return True
    return f(x-100) or f(x-101) or f(x-102) \
            or f(x-103) or f(x-104) or f(x-105)

def main():
    X = ii()
    print(1 if f(X) else 0)


if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys, math
from functools import lru_cache
from collections import deque
sys.setrecursionlimit(500000)
MOD = 10**9+7

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

def mi():
    return map(int, input().split())

def ii():
    return int(input())

def i2(n):
    tmp = [list(mi()) for i in range(n)]
    return [list(i) for i in zip(*tmp)]

@lru_cache(maxsize=None)
def f(x):
    if x < 0:
        return False
    if (x%100==0) or (x%101==0) or (x%102==0) \
            or (x%103==0) or (x%104==0) or (x%105==0):
        return True
    return f(x-100) or f(x-101) or f(x-102) \
            or f(x-103) or f(x-104) or f(x-105)

def main():
    X = ii()
    print(1 if f(X) else 0)


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

import sys
from itertools import islice
from collections import deque
read = map(int, sys.stdin.read().split())

N = next(read)
A = [deque()] + [deque(islice(read, N - 1)) for _ in range(N)]
day = 0

while True:
    done = set()
    for i in range(1, N + 1):
        if i not in done and A[i]:
            if A[A[i][0]][0] == i and A[i][0] not in done:
                done.add(A[A[i][0]].popleft())
                done.add(A[i].popleft())

    if len(done) == 0:
        for i in A:
            if len(i) > 0:
                print(-1)
                exit()
        else:
            print(day)
            exit()
    
    day += 1

### FIXED CODE ###

import sys
from itertools import islice
from collections import deque
read = map(int, sys.stdin.read().split())

N = next(read)
A = [deque()] + [deque(islice(read, N - 1)) for _ in range(N)]
days = 1
available_players = deque(range(1, N + 1))
next_opponent = [0] * (N + 1)
played = set()

while available_players:
    player = available_players.popleft()
    if not A[player]:
        continue

    opponent = A[player].popleft()
    if next_opponent[opponent] == player:
        available_players.append(player)
        available_players.append(opponent)
        next_opponent[player] = 0
        next_opponent[opponent] = 0
        if player in played:
            days += 1
            played = set()
        played.add(player)
        played.add(opponent)
    else:
        next_opponent[player] = opponent

for i in A:
    if len(i) > 0:
        print(-1)
        exit()
else:
    print(days)
### BUGGY CODE ###

S = input()
T = input()
# S = "abracadabra"
# T = "avadakedavra"
dp = [[[] for i in range(len(T)+1)] for j in range(len(S)+1)]
for i in range(1,len(S)+1):
    for j in range(1,len(T)+1):
        if i == 0 or j == 0: continue
        if S[i-1] == T[j-1]:
            dp[i][j].append("".join(dp[i-1][j-1]) + S[i-1])
        else:
            if len("".join(dp[i-1][j])) >= len("".join(dp[i][j-1])): 
                dp[i][j].append("".join(dp[i-1][j]))
            else:
                dp[i][j].append("".join(dp[i][j-1]))

print("".join(dp[len(S)][len(T)]))

### FIXED CODE ###

S = input()
T = input()
dp = [[0 for i in range(len(T)+1)] for j in range(len(S)+1)]
for i in range(1,len(S)+1):
    for j in range(1,len(T)+1):
        if S[i-1] == T[j-1]:
            dp[i][j] = 1 + dp[i-1][j-1]
        else:
            dp[i][j] = max(dp[i-1][j],dp[i][j-1]) 

length = dp[len(S)][len(T)]
LCS = [0]*length
i = len(S)
j = len(T)
while i > 0 and j > 0: 
    if S[i-1] == T[j-1]: 
        LCS[length-1] = S[i-1]
        i-=1
        j-=1
        length-=1
    elif dp[i-1][j] > dp[i][j-1]: 
        i-=1
    else: 
        j-=1
print("".join(LCS))
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
mod = 10**9+7
C = [0] * 60
for a in A:
    for i in range(60):
        if a>>i&1:
            C[i] += 1
ans = 0
for i, c in enumerate(C):
    ans += (1<<i) * c * (N-c) % mod
print(ans % mod)


### FIXED CODE ###

import os
import sys
import numpy as np

def solve(A, N):
    mod = 10**9+7
    C = [0] * 60
    for a in A:
        for i in range(60):
            if a>>i&1:
                C[i] += 1
    ans = 0
    for i, c in enumerate(C):
        ans += (1<<i) % mod * c % mod * (N-c) % mod
    return ans % mod

# >>> numba compile >>>
numba_config = [
    [solve, "i8(i8[:],i8)"],
]
if sys.argv[-1] == "ONLINE_JUDGE":
    from numba import njit
    from numba.pycc import CC
    cc = CC("my_module")
    for func, signature in numba_config:
        vars()[func.__name__] = njit(signature)(func)
        cc.export(func.__name__, signature)(func)
    cc.compile()
    exit()
elif os.name == "posix":
    exec(f"from my_module import {','.join(func.__name__ for func, _ in numba_config)}")
else:
    from numba import njit
    for func, signature in numba_config:
        vars()[func.__name__] = njit(signature, cache=True)(func)
    print("compiled!", file=sys.stderr)
# <<< numba compile <<<

N = int(input())
A = np.array(input().split(), dtype=np.int64)
print(solve(A, N))
### BUGGY CODE ###

n = int(input())
num = list(map(int,input().strip().split()))
q = int(input())
for i in range(q):
  b,c = map(int,input().strip().split())
  for x in range(n):
    if num[x] == b:
      num[x] = c
  print(sum(num))

### FIXED CODE ###

n = int(input())
num = list(map(int,input().strip().split()))
s = sum(num)
num_dict = {}
for i in num:
  if i in num_dict:
    num_dict[i] += 1
  else:
    num_dict[i] = 1
q = int(input())
for i in range(q):
  b,c = map(int,input().strip().split())
  if c in num_dict:
    if b in num_dict:
      k = num_dict[b]
      num_dict[c] += num_dict[b]
      del num_dict[b]
      if b > c:
        s = s - (b-c)*k
        print(s)
      else:
        s = s + (c-b)*k
        print(s)
    else:
      print(s)
  else:
    if b in num_dict:
      k = num_dict[b]
      num_dict[c] = num_dict[b]
      del num_dict[b]
      if b > c:
        s = s - (b-c)*k
        print(s)
      else:
        s = s + (c-b)*k
        print(s)
    else:
      print(s)
### BUGGY CODE ###

N = int(input())
Cx = [[0, 0] for i in range(N)]
Cy = [[0, 0] for i in range(N)]
for i in range(N):
  x, y = map(int, input().split())
  Cx[i] = [x, i]
  Cy[i] = [y, i]
Cx.sort()
Cy.sort()
Qx = sorted([[Cx[i + 1][0] - Cx[i][0], Cx[i][1], Cx[i + 1][1]] for i in range(N - 1)])
Qy = sorted([[Cy[i + 1][0] - Cy[i][0], Cy[i][1], Cy[i + 1][1]] for i in range(N - 1)])
R = [i for i in range(N)]
def root(n):
  if R[n] == n:
    return n
  else:
    R[n] = root(R[n])
    return R[n]
cnt = 0
cost = 0
x = 0
y = 0
while cnt < N - 1:
  if Qx[x][0] <= Qy[y][0]:
    q = Qx[x]
    x += 1
  else:
    q = Qy[y]
    y += 1
  r1 = root(q[1])
  r2 = root(q[2])
  if r1 != r2:
    R[r2] = q[1]
    cost += q[0]
    cnt += 1
print(cost)

### FIXED CODE ###

N = int(input())
Cx = [[0, 0] for i in range(N)]
Cy = [[0, 0] for i in range(N)]
for i in range(N):
  x, y = map(int, input().split())
  Cx[i] = [x, i]
  Cy[i] = [y, i]
Cx.sort()
Cy.sort()
Qx = sorted([[Cx[i + 1][0] - Cx[i][0], Cx[i][1], Cx[i + 1][1]] for i in range(N - 1)])
Qy = sorted([[Cy[i + 1][0] - Cy[i][0], Cy[i][1], Cy[i + 1][1]] for i in range(N - 1)])
R = [i for i in range(N)]
def root(n):
  if R[n] == n:
    return n
  else:
    R[n] = root(R[n])
    return R[n]
cnt = 0
cost = 0
x = 0
y = 0
while cnt < N - 1:
  if Qx[x][0] <= Qy[y][0]:
    q = Qx[x]
    x += 1
  else:
    q = Qy[y]
    y += 1
  r1 = root(q[1])
  r2 = root(q[2])
  if r1 != r2:
    R[r2] = q[1]
    cost += q[0]
    cnt += 1
print(cost)